Feedback arc set in bipartite tournaments is NP-complete

DOI10.1016/J.IPL.2006.11.016MaRDI QIDQ845963zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Falk Hüffner, Hannes Moser

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.11.016

zbMATH Keywords

computational complexitybipartite tournamentscombinatorial problemsfeedback set problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Feedback Arc Set Problem in Bipartite Tournaments
• Feedback arc set problem in bipartite tournaments
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Fixed-parameter complexity of feedback vertex set in bipartite tournaments
• A polynomial kernel for Feedback Arc Set on bipartite tournaments
• A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• Improved approximation algorithm for the feedback set problem in a bipartite tournament
• Fixed-parameter tractability results for feedback set problems in tournaments

Cites work

• scientific article; zbMATH DE number 219267 (Why is no real title available?)
• A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
• A Min-Max Theorem on Feedback Vertex Sets
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Aggregating inconsistent information
• Feedback vertex sets and cyclically reducible graphs
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Ranking Tournaments
• Structure preserving reductions among convex optimization problems
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments

Cited in

(15)

• Tight upper bounds for minimum feedback arc sets of regular graphs
• Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
• Feedback arc set problem in bipartite tournaments
• Solving subgraph isomorphism problems with constraint programming
• Feedback arc set. A history of the problem and algorithms
• A better LP rounding for feedback arc set on tournaments
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
• Complexity of counting feedback vertex sets
• Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
• Computing the EHZ capacity is \(\operatorname{NP}\)-hard
• On the complexity of compressing two dimensional routing tables with order
• Forbidden tournaments and the orientation completion problem
• Fixed-parameter tractability results for feedback set problems in tournaments
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments

This page was built for publication: Feedback arc set in bipartite tournaments is NP-complete

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