On parameterized independent feedback vertex set

DOI10.1016/j.tcs.2012.02.012zbMath1253.68181OpenAlexW2020889718MaRDI QIDQ690464

Geevarghese Philip, Saket Saurabh, Neeldhara Misra, Venkatesh Raman

Publication date: 27 November 2012

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

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

zbMATH Keywords

polynomial kernelsfeedback vertex set problemsfixed-parameter tractable algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Circular convex bipartite graphs: feedback vertex sets ⋮ A polynomial kernel for block graph deletion ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ Independent feedback vertex sets for graphs of bounded diameter ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Unnamed Item ⋮ Circumventing connectivity for kernelization ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ 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 ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Independent Feedback Vertex Set for P_5-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Improved algorithms for feedback vertex set problems
• Solving connected dominating set faster than \(2^n\)
• Approximation algorithms for connected dominating sets
• Parametrized complexity theory.
• A 4 k ² kernel for feedback vertex set
• Treewidth reduction for constrained separation and bipartization problems
• A fixed-parameter algorithm for the directed feedback vertex set problem
• On Feedback Vertex Set New Measure and New Structures
• Linear Kernel for Planar Connected Dominating Set
• Kernelization: New Upper and Lower Bound Techniques
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time