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).
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.
Item Type: | Book chapter |
---|---|
Full text: | Full text not available from this repository. |
Publisher Web site: | http://dx.doi.org/10.1007/978-3-642-34611-8_32 |
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
Export: | |
Look up in GoogleScholar |