Tight Running Time Lower Bounds for Vertex Deletion Problems

DOI10.1145/3186589zbMath1427.68245arXiv1511.05449OpenAlexW2964157158WikidataQ129980865 ScholiaQ129980865MaRDI QIDQ4973874

Christian Komusiewicz

Publication date: 6 December 2019

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

Full work available at URL: https://arxiv.org/abs/1511.05449

zbMATH Keywords

graph propertiesexponential time hypothesisfine-grain complexity analysis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ Unnamed Item ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants.

This page was built for publication: Tight Running Time Lower Bounds for Vertex Deletion Problems