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

DOI10.1007/978-3-642-29344-3_47zbMATH Open1353.68303arXiv1111.4299OpenAlexW2161379920MaRDI QIDQ2894497FDOQ2894497

Authors: Monaldo Mastrolilli 

Publication date: 29 June 2012

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

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.

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

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

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)

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)