Exact localisations of feedback sets

DOI10.1007/S00224-017-9777-6MaRDI QIDQ722200zbMATH OpenOpenAlexWikidataFDO

Authors Michael Hecht

Publication date 23 July 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1702.07612

zbMATH Keywords

linear ordering problemsimple cycleacyclic subgraph problemelementary cyclefeedback set problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The feedback arc (vertex) set problem, shortened FASP (FVSP), is to transform a given multi digraph $G=(V,E)$ into an acyclic graph by deleting as few arcs (vertices) as possible. Due to the results of Richard M. Karp in 1972 it is one of the classic NP-complete problems. An important contribution of this paper is that the subgraphs $G_{mathrmel}(e)$, $G_{mathrmsi}(e)$ of all elementary cycles or simple cycles running through some arc $einE$, can be computed in $$ and $mathcalO(|E{|}^4)$, respectively. We use this fact and introduce the notion of the essential minor and isolated cycles, which yield a priori problem size reductions and in the special case of so called resolvable graphs an exact solution in $mathcalO(|V||E{|}^3)$. We show that weighted versions of the FASP and FVSP possess a Bellman decomposition, which yields exact solutions using a dynamic programming technique in times $$ and $$, where $mleq|E|-|V|+1$, $nleq(Delta(G)-1)|V|-|E|+1$, respectively. The parameters $m,n$ can be computed in $mathcalO(|E{|}^3)$, $mathcalO(Delta(G{)}^3|V{|}^3)$, respectively and denote the maximal dimension of the cycle space of all appearing meta graphs, decoding the intersection behavior of the cycles. Consequently, $m,n$ equal zero if all meta graphs are trees. Moreover, we deliver several heuristics and discuss how to control their variation from the optimum. Summarizing, the presented results allow us to suggest a strategy for an implementation of a fast and accurate FASP/FVSP-SOLVER.

Recommendations

• Tight localizations of feedback sets
• An exact method for the minimum feedback arc set problem
• A fast and effective heuristic for the feedback arc set problem
• scientific article; zbMATH DE number 219267
• Finding a minimum feedback arc set in reducible flow graphs

Cites work

• scientific article; zbMATH DE number 432770 (Why is no real title available?)
• scientific article; zbMATH DE number 3742601 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1033414 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A Minimax Theorem for Directed Graphs
• A fast and effective algorithm for the feedback arc set problem
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Approximating minimum feedback sets and multicuts in directed graphs
• Computational Complexity
• Enumeration of the Elementary Circuits of a Directed Graph
• Estimating the Number of s-t Paths in a Graph
• Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
• Finding All the Elementary Circuits of a Directed Graph
• Finding a minimum feedback arc set in reducible flow graphs
• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• On Algorithms for Enumerating All Circuits of a Graph
• On the acyclic subgraph polytope
• On the approximability of the maximum common subgraph problem
• On the hardness of approximating minimum vertex cover
• Ranking Tournaments
• Reducibility among combinatorial problems
• Retiming synchronous circuitry
• The directed subgraph homeomorphism problem
• The ellipsoid method and its consequences in combinatorial optimization
• The theory of graphs. Translated from the 1958 French edition by Alison Doig.

Cited in

(13)

• Spin Glass approach to the feedback vertex set problem
• scientific article; zbMATH DE number 219267 (Why is no real title available?)
• Tight localizations of feedback sets
• scientific article; zbMATH DE number 139781 (Why is no real title available?)
• Feedback arc set. A history of the problem and algorithms
• Efficient heuristics to compute minimal and stable feedback arc sets
• Combinatorial algorithms for feedback problems in directed graphs
• On the complexity of feedback set problems in signed digraphs
• Complexity of counting feedback vertex sets
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• A spin glass approach to the directed feedback vertex set problem
• DTCPP - A heuristic program for testing decyclization in directed graphs and its isomorphic image by using combinatorial approach
• An exact method for the minimum feedback arc set problem

This page was built for publication: Exact localisations of feedback sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722200)