Fixed-parameter tractability results for feedback set problems in tournaments

DOI10.1016/j.jda.2009.08.001zbMath1191.68349MaRDI QIDQ2266940

Anke Truss, Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier

Publication date: 26 February 2010

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2009.08.001

zbMATH Keywords

tournament; bipartite tournament; feedback vertex set; fixed-parameter tractability; feedback arc set; iterative compression

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

Related Items

Improved bounds for minimal feedback vertex sets in tournaments, Unnamed Item, Unnamed Item, Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number, Efficient algorithms for measuring the funnel-likeness of DAGs, Conflict free version of covering problems on graphs: classical and parameterized, A parameterized algorithm for subset feedback vertex set in tournaments, Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number, A survey of parameterized algorithms and the complexity of edge modification, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Exploiting a hypergraph model for finding Golomb rulers, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, Kernels for deletion to classes of acyclic digraphs, Polynomial kernels for deletion to classes of acyclic digraphs, A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs, A quadratic vertex kernel for feedback arc set in bipartite tournaments, Parameterised algorithms for deletion to classes of DAGs, Tractability of König edge deletion problems, Possible winner problems on partial tournaments: a parameterized study, The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders, A multivariate framework for weighted FPT algorithms, An improved parameterized algorithm for the independent feedback vertex set problem, Algorithms for deletion problems on split graphs, Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs, COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Feedback arc set in bipartite tournaments is NP-complete
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• An efficient fixed-parameter algorithm for 3-hitting set
• Improved algorithms for feedback vertex set problems
• Improved approximation algorithm for the feedback set problem in a bipartite tournament
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• On enumerating all minimal solutions of feedback problems
• Improved FPT algorithm for feedback vertex set problem in bipartite tournament
• Feedback arc set problem in bipartite tournaments
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Open problems around exact algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Parametrized complexity theory.
• A survey on the linear ordering problem for weighted or unweighted tournaments
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Kernels: Annotated, Proper and Induced
• Iterative Compression and Exact Algorithms
• Kernelization Algorithms for d-Hitting Set Problems
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Fast FAST
• A fast algorithm for computing longest common subsequences
• Fixed-Parameter Algorithms for Cluster Vertex Deletion
• Ranking Tournaments
• On maximal transitive subtournaments
• A Min-Max Theorem on Feedback Vertex Sets
• Improved Parameterized Upper Bounds for Vertex Cover
• Aggregating inconsistent information