## Modifying a graph using vertex elimination

*Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniël Paulusma and Michał Pilipczuk*

*Algorithmica*, vol. 72, no. 1, pp.99-125, 2015.

[__DOI__][__Preprint__]

A preliminary version of this paper has appeared in the proceedings of WG 2012, the 38th International Workshop on Graph-Theoretic Concepts in Computer Science (held on June 26-28, 2012 in Jerusalem, Israel), *Lecture Notes in Computer Science*, vol. 7551, pp. 320-331, 2012.

[__DOI__]

### 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 surprisingly remains NP-complete when *G* is a tree.