English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For a graph class Π, the Π-Vertex Deletion problem has as input an undirected graph G = (V,E) and an integer k and asks whether there is a set of at most k vertices that can be deleted from G such that the resulting graph is a member of Π. By a classic result of Lewis and Yannakakis [17], Π-Vertex Deletion is NP-hard for all hereditary properties Π. We adapt the original NP-hardness construction to show that under the exponential time hypothesis (ETH), tight complexity results can be obtained. We show that Π-Vertex Deletion does not admit a 2o(n)-time algorithm where n is the number of vertices in G. We also obtain a dichotomy for running time bounds that include the number m of edges in the input graph. On the one hand, if Π contains all edgeless graphs, then there is no 2o(n+m)-time algorithm for Π-Vertex Deletion. On the other hand, if there is a fixed edgeless graph that is not contained in Π and containment in Π can be determined in 2O(n) time or 2o(m) time, then Π-Vertex Deletion can be solved in 2O(&sqrt;m)+O(n) or 2o(m)+O(n) time, respectively. We also consider restrictions on the domain of the input graph G. For example, we obtain that Π-Vertex Deletion cannot be solved in 2o(&sqrt;n) time if G is planar and Π is hereditary and contains and excludes infinitely many planar graphs. Finally, we provide similar results for the problem variant where the deleted vertex set has to induce a connected graph.

Tight Running Time Lower Bounds for Vertex Deletion Problems