**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Abstract

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnection denotes the maximum number of colors that can be used in a vertex coloring such that after deletion of the monochromatic arcs the graph is acyclic. Figueroa et al. generalized the definitions of a feedback arc set and the acyclic disconnection to undirected graphs. They proposed a connection between the two parameters in the undirected setting. To be more precise, they showed that in wheel graphs and grid graphs the sum of the two parameters equals the number of vertices and claimed it to be true for outerplanar graphs. We extend their results by giving a characterization of graph classes for which the directed version of the proposed relation holds, answering an open question of Figueroa et al. We apply our characterization to almost trees (3) and wheel graphs. Moreover, we show that the proposed relation does not hold for outerplanar graphs neither in the directed nor in the undirected version. This proves Theorem 15 of Figueroa et al. to be wrong. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (49)

Related MOOCs (11)

Ontological neighbourhood

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Related publications (290)

Analyse I

Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond

Analyse I (partie 1) : Prélude, notions de base, les nombres réels

Concepts de base de l'analyse réelle et introduction aux nombres réels.

Analyse I (partie 2) : Introduction aux nombres complexes

Introduction aux nombres complexes

This article proposes an exploration technique for multiagent reinforcement learning (MARL) with graph-based communication among agents. We assume that the individual rewards received by the agents are independent of the actions by the other agents, while ...

Maximilien Claude Robert Dreveton

This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all tem ...

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...