FPT algorithms for connected feedback vertex set

DOI10.1007/s10878-011-9394-2zbMath1258.05060OpenAlexW2007985221MaRDI QIDQ695322

Saket Saurabh, Venkatesh Raman, Somnath Sikdar, Geevarghese Philip, Neeldhara Misra

Publication date: 21 December 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-011-9394-2

zbMATH Keywords

Steiner treefeedback vertex setparameterized algorithmsgroup Steiner treeFPT algorithmsconnected feedback vertex setdirected Steiner out-treedynamic programming over tree decompositionsH-minor-free graphshardness of polynomial kernelizationsubexponential FPT algorithms

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (19)

Finding good 2-partitions of digraphs. I. Hereditary properties ⋮ Finding good 2-partitions of digraphs. II. Enumerable properties ⋮ A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Improved Parameterized Algorithms for Network Query Problems ⋮ Improved parameterized algorithms for network query problems ⋮ Degree-constrained 2-partitions of graphs ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Circumventing connectivity for kernelization ⋮ On the parameterized complexity of 2-partitions ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Minimization and parameterized variants of vertex partition problems on graphs ⋮ Unnamed Item ⋮ Dynamic parameterized problems ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ The price of connectivity for cycle transversals ⋮ A complete parameterized complexity analysis of bounded planning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Linearity of grid minors in treewidth with applications through bidimensionality
• Solving connected dominating set faster than \(2^n\)
• On Problems without Polynomial Kernels (Extended Abstract)
• On Feedback Vertex Set New Measure and New Structures
• Incompressibility through Colors and IDs
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Bidimensionality and Geometric Graphs
• Digraphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computing and Combinatorics
• Connected Feedback Vertex Set in Planar Graphs

This page was built for publication: FPT algorithms for connected feedback vertex set