Back to Search
Start Over
Modifying a Graph Using Vertex Elimination.
- Source :
-
Algorithmica . May2015, Vol. 72 Issue 1, p99-125. 27p. - Publication Year :
- 2015
-
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 $\mathsf {W[1]} $-hard when parameterized by | V( H)|, even if both input graphs are split graphs, and $\mathsf {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 $\mathsf {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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 72
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 101949371
- Full Text :
- https://doi.org/10.1007/s00453-013-9848-2