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

DOI10.1016/J.TCS.2015.02.004zbMATH Open1312.68104OpenAlexW2043048396MaRDI QIDQ2344735FDOQ2344735

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

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

zbMATH Keywords

fixed-parameter algorithmparity constraintsgraph minor theorysubset feedback set problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Packing and covering immersion models of planar subcubic 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
• Packing and covering immersion-expansions of planar sub-cubic graphs
• 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
• Recent techniques and results on the Erdős-Pósa property
• Odd multiway cut in directed acyclic graphs

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)