Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments

DOI10.1007/s00453-015-0038-2zbMath1350.68126OpenAlexW1048071008MaRDI QIDQ329279

Alessandro Maddaloni, Saket Saurabh, Jörgen Bang-Jensen

Publication date: 21 October 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0038-2

zbMATH Keywords

kernelsfeedback vertex setparameterized complexitylocally semicomplete digraphfeedback arc setquasi-transitive digraphbounded independence numberdecomposable digraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (7)

On the Complexity of Singly Connected Vertex Deletion ⋮ A polynomial kernel for funnel arc deletion set ⋮ A Polynomial Kernel for Funnel Arc Deletion Set. ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ Locally Semicomplete Digraphs and Generalizations ⋮ On the complexity of singly connected vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
• Infeasibility of instance compression and succinct PCPs for NP
• Kernels for feedback arc set in tournaments
• Tournament immersion and cutwidth
• Parameterized algorithms for feedback set problems and their duals in tournaments
• A kernelization algorithm for \(d\)-hitting set
• On problems without polynomial kernels
• Approximating minimum feedback sets and multicuts in directed graphs
• On the structure of local tournaments
• Faster deterministic \textsc{Feedback Vertex Set}
• Fixed-parameter tractability results for feedback set problems in tournaments
• Parametrized complexity theory.
• Fully dynamic recognition algorithm and certificate for directed cographs
• Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
• Kernelization – Preprocessing with a Guarantee
• A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments
• Arc-Disjoint Paths in Decomposable Digraphs
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments
• Intersection Theorems for Systems of Sets
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Locally semicomplete digraphs: A generalization of tournaments
• Fast FAST
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Quasi‐transitive digraphs
• Reducibility among Combinatorial Problems
• Ranking Tournaments
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Digraphs
• Jungles, bundles, and fixed-parameter tractability
• Aggregating inconsistent information

This page was built for publication: Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments