Modifying a Graph Using Vertex Elimination

Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniël Paulusma, Michal Pilipczuk

Research output: Contribution to journalArticleAcademicpeer-review

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.
Original languageEnglish
Pages (from-to)99-125
JournalAlgorithmica
Volume72
Issue number1
DOIs
Publication statusPublished - 2015
Externally publishedYes

Fingerprint Dive into the research topics of 'Modifying a Graph Using Vertex Elimination'. Together they form a unique fingerprint.

  • Cite this

    Golovach, P. A., Heggernes, P., van 't Hof, 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