Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Blocking independent sets for H-free graphs via edge contractions and vertex deletions
Paulusma, D.; Picouleau, C.; Ries, B.
Authors
C. Picouleau
B. Ries
Contributors
T. Gopal
Editor
G. Jäger
Editor
S. Steila
Editor
Abstract
Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be co-NP-hard even if S consists of either an edge contraction or a vertex deletion. We further investigate its computational complexity under these two settings: we give a sufficient condition on a graph class for the vertex deletion variant to be co-NP-hard even if d=k=1d=k=1 ; in addition we prove that the vertex deletion variant is co-NP-hard for triangle-free graphs even if d=k=1d=k=1 ; we prove that the edge contraction variant is NP-hard for bipartite graphs but linear-time solvable for trees. By combining our new results with known ones we are able to give full complexity classifications for both variants restricted to H-free graphs. D. Paulusma received support from EPSRC (EP/K025090/1).
Citation
Paulusma, D., Picouleau, C., & Ries, B. (2017). Blocking independent sets for H-free graphs via edge contractions and vertex deletions. In T. Gopal, G. Jäger, & S. Steila (Eds.), Theory and Applications of Models of Computation, 14th Annual Conference (TAMC 2017) : Bern, Switzerland, April 20-22, 2017 ; proceedings (470-483). https://doi.org/10.1007/978-3-319-55911-7_34
Conference Name | Theory and applications of models of computation, 14th Annual Conference, TAMC 2017 |
---|---|
Conference Location | Bern, Switzerland |
Start Date | Apr 20, 2017 |
End Date | Apr 22, 2017 |
Acceptance Date | Mar 1, 2017 |
Online Publication Date | Mar 21, 2017 |
Publication Date | Mar 21, 2017 |
Deposit Date | May 1, 2017 |
Publicly Available Date | Mar 21, 2018 |
Pages | 470-483 |
Series Title | Lecture Notes in Computer Science |
Series Number | 10185 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Theory and Applications of Models of Computation, 14th Annual Conference (TAMC 2017) : Bern, Switzerland, April 20-22, 2017 ; proceedings. |
ISBN | 9783319559100 |
DOI | https://doi.org/10.1007/978-3-319-55911-7_34 |
Public URL | https://durham-repository.worktribe.com/output/1147088 |
Files
Accepted Conference Proceeding
(297 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/978-3-319-55911-7_34
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
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