We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

How to eliminate a graph.

Golovach, P.A. and Heggernes, P. and van 't Hof, P. and Manne, F. and Paulusma, Daniel and Pilipczuk, M. (2012) 'How to eliminate a graph.', in Graph-theoretic concepts in computer science: 38th international workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, revised selected papers. Berlin ; Heidelberg: Springer, 320-331 . Lecture notes in computer science. (7551).


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.

Item Type:Book chapter
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar