Cookies

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:

Modifying a graph using vertex elimination.

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.

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.

Item Type:Article
Keywords:Graph modification problems, Vertex elimination, Parameterized complexity, Linear kernel
Full text:(AM) Accepted Manuscript
Download PDF
(447Kb)
Status:Peer-reviewed
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

Export:
Export
Look up in GoogleScholar