The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
From MaRDI portal
Publication:3429737
DOI10.1017/S0963548306007887zbMath1120.05038MaRDI QIDQ3429737
Anders Yeo, Pierre Charbit, Steéphan Thomassé
Publication date: 20 March 2007
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20: Directed graphs (digraphs), tournaments
Related Items
MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS, Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, On the computation of median linear orders, of median complete preorders and of median weak orders, Comparing multiagent systems research in combinatorial auctions and voting, Kernels for feedback arc set in tournaments, Boolean-width of graphs, Feedback arc set in bipartite tournaments is NP-complete, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, Computing the minimal covering set, A tournament of order 14 with disjoint Banks and Slater sets, An updated survey on the linear ordering problem for weighted or unweighted tournaments, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, A survey on the complexity of tournament solutions, On the complexity of Slater's problems, Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs, Models for concurrent product and process design, Quasi-hamiltonian paths in semicomplete multipartite digraphs, A quadratic vertex kernel for feedback arc set in bipartite tournaments, Fixed-parameter tractability results for feedback set problems in tournaments, NP-hardness results for the aggregation of linear orders into median orders, On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments, Bounds on the disparity and separation of tournament solutions, Complexity results for extensions of median orders to different types of remoteness, Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs, Feedback arc set problem in bipartite tournaments, Hardness of fully dense problems, A survey on the linear ordering problem for weighted or unweighted tournaments, Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds, Directed Graphs Without Short Cycles
