Tight localizations of feedback sets

DOI10.1145/3447652MaRDI QIDQ5102049zbMATH OpenOpenAlexFDO

Authors Michael Hecht, Krzysztof Gonciarz, Szabolcs Horvát

Publication date 6 September 2022

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmminimum feedback arc set problemminimum feedback vertex set problemmaximum linear ordering problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: The classical NP-hard feedback arc set problem (FASP) and feedback vertex set problem (FVSP) ask for a minimum set of arcs $varepsilonsubseteqE$ or vertices $usubseteqV$ whose removal $Gsetminusvarepsilon$, $Gsetminusu$ makes a given multi-digraph $G=(V,E)$ acyclic, respectively. Though both problems are known to be APX-hard, approximation algorithms or proofs of inapproximability are unknown. We propose a new $mathcalO(|V||E{|}^4)$-heuristic for the directed FASP. While a ratio of $rapprox1.3606$ is known to be a lower bound for the APX-hardness, at least by empirical validation we achieve an approximation of $rleq2$. The most relevant applications, such as circuit testing, ask for solving the FASP on large sparse graphs, which can be done efficiently within tight error bounds due to our approach.

Recommendations

• Exact localisations of feedback sets
• A fast and effective heuristic for the feedback arc set problem
• scientific article; zbMATH DE number 139781
• scientific article; zbMATH DE number 219267
• An exact method for the minimum feedback arc set problem

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A Faster Deterministic Maximum Flow Algorithm
• A Minimax Theorem for Directed Graphs
• A fast and effective algorithm for the feedback arc set problem
• A fast and effective heuristic for the feedback arc set problem
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A new approach to the maximum-flow problem
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximations for the maximum acyclic subgraph problem
• Collective dynamics of `small-world' networks
• Computational Complexity
• Depth-First Search and Linear Graph Algorithms
• Edge-disjoint spanning trees and depth-first search
• Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
• Exact localisations of feedback sets
• Improved deterministic algorithms for decremental reachability and strongly connected components
• Introduction to algorithms
• Max flows in O(nm) time, or better
• On the acyclic subgraph polytope
• On the hardness of approximating minimum vertex cover
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Ranking tournaments, local search and a new algorithm
• Reducibility among combinatorial problems
• Retiming synchronous circuitry
• Structure preserving reductions among convex optimization problems
• The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
• Topological sorting of large networks
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(8)

• A fast and effective heuristic for the feedback arc set problem
• A spin glass approach to the directed feedback vertex set problem
• Finding small feedback arc sets on large graphs
• Exact localisations of feedback sets
• Efficient heuristics to compute minimal and stable feedback arc sets
• Minimal and stable feedback arc sets and graph centrality measures
• scientific article; zbMATH DE number 825126 (Why is no real title available?)
• scientific article; zbMATH DE number 701192 (Why is no real title available?)

This page was built for publication: Tight localizations of feedback sets

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