A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

DOI10.1145/1944857.1944860zbMath1322.68101OpenAlexW2052227003MaRDI QIDQ5892184

Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraph algorithmsparameterized complexityvertex deletion problemsiterative compressionhereditary graph properties

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) 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)

Related Items

An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ Another disjoint compression algorithm for odd cycle transversal ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem

This page was built for publication: A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems