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)
Full work available at URL: https://doi.org/10.1017/s0963548306007887
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, Unnamed Item, The Network HHD: Quantifying Cyclic Competition in Trait-Performance Models of Tournaments, Robust Learning of Consumer Preferences, An Exact Method for the Minimum Feedback Arc Set Problem, Voting Procedures, Complexity of, Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number, Packing Arc-Disjoint Cycles in Tournaments, Triangle packing in (sparse) tournaments: approximation and kernelization, Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs, Efficient algorithms for measuring the funnel-likeness of DAGs, Ranking chain sum orders, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, Approaches for solving the container stacking problem with route distance minimization and stack rearrangement considerations, 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, The minimum feedback arc set problem and the acyclic disconnection for graphs, 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, Cycle reversions and dichromatic number in tournaments, Monocular extraction of 2.1D sketch using constrained convex optimization, Quasi-hamiltonian paths in semicomplete multipartite digraphs, Polynomial time algorithms for tracking path problems, 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, Ranking tournaments with no errors. I: Structural description, \(k\)-majority digraphs and the hardness of voting with a constant number of voters, 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, Binets: fundamental building blocks for phylogenetic networks, Feedback arc set problem in bipartite tournaments, Hardness of fully dense problems, A survey on the linear ordering problem for weighted or unweighted tournaments, Packing arc-disjoint cycles in tournaments, Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds, Tournaments and Semicomplete Digraphs, Directed Graphs Without Short Cycles
