Fixed-parameter tractability for subset feedback set problems with parity constraints

DOI10.1016/j.tcs.2015.02.004zbMath1312.68104OpenAlexW2043048396MaRDI QIDQ2344735

Naonori Kakimura, Ken-ichi Kawarabayashi

Publication date: 18 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.004

zbMATH Keywords

fixed-parameter algorithmparity constraintsgraph minor theorysubset feedback set problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Packing and Covering Immersion Models of Planar Subcubic Graphs ⋮ Packing and covering immersion-expansions of planar sub-cubic graphs ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ Erdös-Pósa Property of Obstructions to Interval Graphs ⋮ Erdős–Pósa property of obstructions to interval graphs ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Finding odd cycle transversals.
• Matching theory
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Mangoes and blueberries
• Disjoint paths in graphs
• 2-linked graphs
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Graph minors. XIII: The disjoint paths problem
• Packing cycles through prescribed vertices
• On the odd-minor variant of Hadwiger's conjecture
• Parameterized Tractability of Multiway Cut with Parity Constraints
• Odd cycle packing
• A 4 k ² kernel for feedback vertex set
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• On the presence of disjoint subgraphs of a specified type
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• The Complexity of Multiterminal Cuts
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• A polyhedral approach to the feedback vertex set problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Faster Parameterized Algorithms Using Linear Programming
• Reducibility among Combinatorial Problems
• Parameterized Algorithms for Even Cycle Transversal
• Linear-Time FPT Algorithms via Network Flow
• Half-integrality, LP-branching and FPT Algorithms
• Algorithms and Data Structures
• The Graph Minor Algorithm with Parity Conditions
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• A Min-Max Theorem on Feedback Vertex Sets
• Totally odd \(K_4\)-subdivisions in 4-chromatic graphs

This page was built for publication: Fixed-parameter tractability for subset feedback set problems with parity constraints