Linear Time Parameterized Algorithms for Subset Feedback Vertex Set

DOI10.1007/978-3-662-47672-7_76zbMath1440.68138OpenAlexW2397439386MaRDI QIDQ3448850

Saket Saurabh, M. S. Ramanujan, Daniel Lokshtanov

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/101481/1/WRAP-linear-time-parameterized-algorithms-Lokshtanov-2018.pdf

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Hitting Selected (Odd) Cycles ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Unnamed Item ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Unnamed Item ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Parameterized graph separation problems
• Improved algorithms for feedback vertex set problems
• Almost 2-SAT is fixed-parameter tractable
• Which problems have strongly exponential complexity?
• Graph minors. XIII: The disjoint paths problem
• Faster deterministic \textsc{Feedback Vertex Set}
• An improved parameterized algorithm for the minimum node multiway cut problem
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Half-integrality, LP-branching, and FPT Algorithms
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Parameterized Tractability of Multiway Cut with Parity Constraints
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Planar Subgraph Isomorphism Revisited
• On Feedback Vertex Set New Measure and New Structures
• Dividing a Graph into Triconnected Components
• Planarity Allowing Few Error Vertices in Linear Time
• Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
• Linear-Time FPT Algorithms via Network Flow
• Half-integrality, LP-branching and FPT Algorithms
• A Near-Optimal Planarization Algorithm
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–

This page was built for publication: Linear Time Parameterized Algorithms for Subset Feedback Vertex Set