Skip to main content

Research Repository

Advanced Search

How to eliminate a graph

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

Authors

P.A. Golovach

P. Heggernes

P. van 't Hof

F. Manne

M. Pilipczuk



Contributors

Martin Charles Golumbic
Editor

Michal Stern
Editor

Avivit Levy
Editor

Gila Morgenstern
Editor

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 study the parameterized complexity of the Elimination problem. 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., van 't Hof, P., Manne, F., Paulusma, D., & Pilipczuk, M. (2012). How to eliminate a graph. In M. C. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science: 38th international workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, revised selected papers (320-331). https://doi.org/10.1007/978-3-642-34611-8_32

Publication Date 2012
Deposit Date Mar 11, 2013
Pages 320-331
Series Title Lecture notes in computer science
Series Number 7551
Series ISSN 0302-9743,1611-3349
Book Title Graph-theoretic concepts in computer science: 38th international workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, revised selected papers.
ISBN 9783642346101
DOI https://doi.org/10.1007/978-3-642-34611-8_32
Public URL https://durham-repository.worktribe.com/output/1156186
Additional Information Series: Lecture Notes in Computer Science, Volume 7551