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

DOI10.1016/J.TCS.2015.02.004MaRDI QIDQ2344735zbMATH OpenOpenAlexFDO

Authors 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 algorithmgraph minor theoryparity constraintssubset feedback set problem

Mathematics Subject Classification ID

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

Recommendations

• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Directed Subset Feedback Vertex Set is fixed-parameter tractable

Cites work

• 2-linked graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A 4k^2 kernel for feedback vertex set
• A Min-Max Theorem on Feedback Vertex Sets
• A polyhedral approach to the feedback vertex set problem
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Algorithms and Data Structures
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Disjoint paths in graphs
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Faster parameterized algorithms using linear programming
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• Finding odd cycle transversals.
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Half-integrality, LP-branching and FPT algorithms
• scientific article; zbMATH DE number 6118220 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 6297714 (Why is no real title available?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Linear-time FPT algorithms via network flow
• Mangoes and blueberries
• Matching theory
• Odd cycle packing
• On the odd-minor variant of Hadwiger's conjecture
• On the presence of disjoint subgraphs of a specified type
• Packing cycles through prescribed vertices
• Parameterized algorithms for even cycle transversal
• Parameterized tractability of multiway cut with parity constraints
• Reducibility among combinatorial problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The Complexity of Multiterminal Cuts
• The disjoint paths problem in quadratic time
• The Graph Minor Algorithm with Parity Conditions
• Totally odd K₄-subdivisions in 4-chromatic graphs

Cited in

(9)

• Packing and covering immersion-expansions of planar sub-cubic graphs
• Recent techniques and results on the Erdős-Pósa property
• Packing and covering immersion models of planar subcubic graphs
• Odd multiway cut in directed acyclic graphs
• Erdös-Pósa Property of Obstructions to Interval Graphs
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Erdős–Pósa property of obstructions to interval graphs
• Decremental sensitivity oracles for covering and packing minors

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344735)