Skip to main content

Research Repository

Advanced Search

Modifying a Graph Using Vertex Elimination

Golovach, P.A.; Heggernes, P.; Hof, van 't P.; Manne, F.; Paulusma, D.; Pilipczuk, M.

Modifying a Graph Using Vertex Elimination Thumbnail


Authors

P.A. Golovach

P. Heggernes

van 't P. Hof

F. Manne

M. Pilipczuk



Abstract

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the Elimination problem as follows: given two graphs G and H, decide whether H can be obtained from G by |V(G)|−|V(H)| vertex eliminations. We show that Elimination is W[1]-hard when parameterized by |V(H)|, even if both input graphs are split graphs, and W[2]-hard when parameterized by |V(G)|−|V(H)|, even if H is a complete graph. On the positive side, we show that Elimination admits a kernel with at most 5|V(H)| vertices in the case when G is connected and H is a complete graph, which is in sharp contrast to the W[1]-hardness of the related Clique problem. We also study the case when either G or H is tree. The computational complexity of the problem depends on which graph is assumed to be a tree: we show that Elimination can be solved in polynomial time when H is a tree, whereas it remains NP-complete when G is a tree.

Citation

Golovach, P., Heggernes, P., Hof, V. '. P., Manne, F., Paulusma, D., & Pilipczuk, M. (2015). Modifying a Graph Using Vertex Elimination. Algorithmica, 72(1), 99-125. https://doi.org/10.1007/s00453-013-9848-2

Journal Article Type Article
Acceptance Date Oct 26, 2013
Online Publication Date Nov 8, 2013
Publication Date May 1, 2015
Deposit Date Dec 20, 2014
Publicly Available Date Jan 6, 2015
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 72
Issue 1
Pages 99-125
DOI https://doi.org/10.1007/s00453-013-9848-2
Keywords Graph modification problems, Vertex elimination, Parameterized complexity, Linear kernel
Public URL https://durham-repository.worktribe.com/output/1417598

Files





You might also like



Downloadable Citations