Modifying a Graph Using Vertex Elimination

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

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