Name
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00453-013-9848-2 | Algorithmica |
Keywords | Field | DocType |
Graph modification problems,Vertex elimination,Parameterized complexity,Linear kernel | Discrete mathematics,Combinatorics,Bound graph,Graph power,Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Vertex separator,Degree (graph theory),Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
72 | 1 | 0178-4617 |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr A. Golovach | 1 | 766 | 83.25 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Pim van 't Hof | 3 | 209 | 20.75 |
| Fredrik Manne | 4 | 549 | 49.60 |
| Daniël Paulusma | 5 | 712 | 78.49 |
| michal pilipczuk | 6 | 403 | 51.93 |