Golovach, P.A. and Heggernes, P. and Hof, van 't P. and Manne, F. and Paulusma, D. and Pilipczuk, M. (2015) 'Modifying a graph using vertex elimination.', Algorithmica., 72 (1). pp. 99-125.
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-hard when parameterized by |V(H)|, even if both input graphs are split graphs, and W-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-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.
|Keywords:||Graph modification problems, Vertex elimination, Parameterized complexity, Linear kernel|
|Full text:||(AM) Accepted Manuscript|
Download PDF (447Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/s00453-013-9848-2|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-013-9848-2|
|Date accepted:||26 October 2013|
|Date deposited:||06 January 2015|
|Date of first online publication:||08 November 2013|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|