Linear time parameterized algorithms for \textsc{Subset Feedback Vertex Set}

DOI10.1145/3155299MaRDI QIDQ4554952zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh

Publication date 12 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3155299

zbMATH Keywords

feedback vertex setgraph separation problemslinear-time FPT algorithms

Mathematics Subject Classification ID

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

Recommendations

• Linear time parameterized algorithms for subset feedback vertex set
• Directed subset feedback vertex set is fixed-parameter tractable
• Directed Subset Feedback Vertex Set is fixed-parameter tractable

Cited in

(16)

• Linear time parameterized algorithms for subset feedback vertex set
• Directed subset feedback vertex set is fixed-parameter tractable
• Linear-time FPT algorithms via network flow
• An improved FPT algorithm for independent feedback vertex set
• Improved FPT Algorithms for Deletion to Forest-Like Structures.
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
• Improved FPT Algorithms for Deletion to Forest-Like Structures
• When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices
• Parameterized complexity classification for interval constraints
• Roman cycle hitting set
• A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs
• Subset feedback vertex set parameterized by multiway cut is FPT
• Parameterized complexity of feedback vertex set with connectivity constraints
• An FPT algorithm for edge subset feedback edge set
• Multi-budgeted directed cuts
• A parameterized complexity view on collapsing \(k\)-cores

This page was built for publication: Linear time parameterized algorithms for \textsc{Subset Feedback Vertex Set}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554952)