The feedback arc set problem with triangle inequality is a vertex cover problem

DOI10.1007/978-3-642-29344-3_47MaRDI QIDQ2894497zbMATH OpenOpenAlexFDO

Authors Monaldo Mastrolilli

Publication date 29 June 2012

Published in LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We consider the (precedence constrained) Minimum Feedback Arc Set problem with triangle inequalities on the weights, which finds important applications in problems of ranking with inconsistent information. We present a surprising structural insight showing that the problem is a special case of the minimum vertex cover in hypergraphs with edges of size at most 3. This result leads to combinatorial approximation algorithms for the problem and opens the road to studying the problem as a vertex cover problem.

Recommendations

• The feedback arc set problem with triangle inequality is a vertex cover problem
• A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
• Combinatorial algorithms for feedback problems in directed graphs
• scientific article; zbMATH DE number 1003266
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference

Cited in

(1)

• The feedback arc set problem with triangle inequality is a vertex cover problem

This page was built for publication: The feedback arc set problem with triangle inequality is a vertex cover problem

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