P.A. Golovach
Modifying a Graph Using Vertex Elimination
Golovach, P.A.; Heggernes, P.; Hof, van 't P.; Manne, F.; Paulusma, D.; Pilipczuk, M.
Authors
P. Heggernes
van 't P. Hof
F. Manne
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
M. Pilipczuk
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.
Journal Article Type | Article |
---|---|
Acceptance Date | Oct 26, 2013 |
Online Publication Date | Nov 8, 2013 |
Publication Date | May 1, 2015 |
Deposit Date | Dec 20, 2014 |
Publicly Available Date | Jan 6, 2015 |
Journal | Algorithmica |
Print ISSN | 0178-4617 |
Electronic ISSN | 1432-0541 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 72 |
Issue | 1 |
Pages | 99-125 |
DOI | https://doi.org/10.1007/s00453-013-9848-2 |
Keywords | Graph modification problems, Vertex elimination, Parameterized complexity, Linear kernel |
Public URL | https://durham-repository.worktribe.com/output/1417598 |
Files
Accepted Journal Article
(457 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-013-9848-2
You might also like
Classifying Subset Feedback Vertex Set for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
An algorithmic framework for locally constrained homomorphisms
(2022)
Presentation / Conference Contribution
The Complexity of L(p,q)-Edge-Labelling
(2022)
Presentation / Conference Contribution
Computing Balanced Solutions for Large International Kidney Exchange Schemes
(2022)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search