Fixed-parameter tractability results for feedback set problems in tournaments

DOI10.1016/j.jda.2009.08.001zbMath1191.68349OpenAlexW2165662279MaRDI 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

tournamentbipartite tournamentfeedback vertex setfixed-parameter tractabilityfeedback arc setiterative compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (27)

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

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

This page was built for publication: Fixed-parameter tractability results for feedback set problems in tournaments