The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
From MaRDI portal
Publication:3429737
DOI10.1017/S0963548306007887zbMath1120.05038OpenAlexW2082806890MaRDI QIDQ3429737
Anders Yeo, Pierre Charbit, Steéphan Thomassé
Publication date: 20 March 2007
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548306007887
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20)
Related Items
Binets: fundamental building blocks for phylogenetic networks, Ranking chain sum orders, Feedback arc set in bipartite tournaments is NP-complete, Polynomial time algorithms for tracking path problems, Feedback arc set problem in bipartite tournaments, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, Hardness of fully dense problems, Approaches for solving the container stacking problem with route distance minimization and stack rearrangement considerations, A survey on the linear ordering problem for weighted or unweighted tournaments, The Network HHD: Quantifying Cyclic Competition in Trait-Performance Models of Tournaments, Robust Learning of Consumer Preferences, Packing arc-disjoint cycles in tournaments, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds, Comparing multiagent systems research in combinatorial auctions and voting, An Exact Method for the Minimum Feedback Arc Set Problem, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number, Extremal results on feedback arc sets in digraphs, Invertibility of Digraphs and Tournaments, Quasi-hamiltonian paths in semicomplete multipartite digraphs, On the computation of median linear orders, of median complete preorders and of median weak orders, Cycle reversions and dichromatic number in tournaments, Kernels for feedback arc set in tournaments, Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs, Voting Procedures, Complexity of, Computing the minimal covering set, MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS, Directed Graphs Without Short Cycles, The minimum feedback arc set problem and the acyclic disconnection for graphs, A quadratic vertex kernel for feedback arc set in bipartite tournaments, A tournament of order 14 with disjoint Banks and Slater sets, Unnamed Item, 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, Fixed-parameter tractability results for feedback set problems in tournaments, NP-hardness results for the aggregation of linear orders into median orders, Boolean-width of graphs, Efficient algorithms for measuring the funnel-likeness of DAGs, Ranking tournaments with no errors. I: Structural description, Monocular extraction of 2.1D sketch using constrained convex optimization, Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number, Packing Arc-Disjoint Cycles in Tournaments, \(k\)-majority digraphs and the hardness of voting with a constant number of voters, A survey on the complexity of tournament solutions, On the complexity of Slater's problems, Triangle packing in (sparse) tournaments: approximation and kernelization, Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs, Models for concurrent product and process design, Tournaments and Semicomplete Digraphs, 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
