Subset Feedback Vertex Set Is Fixed-Parameter Tractable

From MaRDI portal
Publication:3012825

DOI10.1007/978-3-642-22006-7_38zbMath1334.68096arXiv1004.2972OpenAlexW1776142702MaRDI QIDQ3012825

Marcin Pilipczuk, Jakub Onufry Wojtaszczyk, Michał Pilipczuk, Marek Cygan

Publication date: 6 July 2011

Published in: SIAM Journal on Discrete Mathematics, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.2972




Related Items

Linear Time Parameterized Algorithms for Subset Feedback Vertex SetBackdoors to SatisfactionDesigning FPT Algorithms for Cut Problems Using Randomized ContractionsComputing a minimum subset feedback vertex set on chordal graphs parameterized by leafageTowards a polynomial kernel for directed feedback vertex setA polynomial kernel for block graph deletionKernels for deletion to classes of acyclic digraphsClique Cover and Graph SeparationInapproximability of $H$-Transversal/PackingHitting Selected (Odd) CyclesOn the lossy kernelization for connected treedepth deletion setA parameterized algorithm for subset feedback vertex set in tournamentsOn Weighted Graph Separation Problems and Flow AugmentationA randomized polynomial kernel for subset feedback vertex setFixed parameterized algorithms for generalized feedback vertex set problemsUnnamed ItemFixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problemPacking cycles through prescribed vertices under modularity constraintsSubset feedback vertex sets in chordal graphsEnumerating minimal subset feedback vertex setsFinding temporal paths under waiting time constraintsImproved FPT Algorithms for Deletion to Forest-Like Structures.An improved FPT algorithm for almost forest deletion problemHalf-integral packing of odd cycles through prescribed verticesFaster deterministic \textsc{Feedback Vertex Set}Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafageDisjoint cycles intersecting a set of verticesPolynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphsAn improved FPT algorithm for independent feedback vertex setComputing subset transversals in \(H\)-free graphsUnnamed ItemUnnamed ItemSubset feedback vertex set in chordal and split graphsHalf-integrality, LP-branching, and FPT AlgorithmsSubset feedback vertex set on graphs of bounded independent set sizeAn FPT algorithm for edge subset feedback edge setUnnamed ItemParameterised algorithms for deletion to classes of DAGsGraphs without two vertex-disjoint \(S\)-cyclesBackdoors to tractable answer set programmingUnnamed ItemNode multiway cut and subset feedback vertex set on graphs of bounded mim-widthFixed-parameter tractability for subset feedback set problems with parity constraintsFPT algorithms for generalized feedback vertex set problemsOn group feedback vertex set parameterized by the size of the cutset



Cites Work