K. K. Dabrowski
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
Dabrowski, K. K.; Johnson, M.; Paesani, G.; Paulusma, D.; Zamaraev, V.
Authors
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
G. Paesani
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
V. Zamaraev
Contributors
Igor Potapov
Editor
Paul Spirakis
Editor
James Worrell
Editor
Abstract
Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if we require that they are independent; that is, what is the price of independence? If G has a vertex cover, feedback vertex set or odd cycle transversal that is an independent set, then we let, respectively, ivc(G), ifvs(G) or ioct(G) denote the minimum size of such a set. We investigate for which graphs H the values of ivc(G), ifvs(G) and ioct(G) are bounded in terms of vc(G), fvs(G) and oct(G), respectively, when the graph G belongs to the class of H-free graphs. We find complete classifications for vertex cover and feedback vertex set and an almost complete classification for odd cycle transversal (subject to three non-equivalent open cases).
Citation
Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2018). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (63:1-63:15). https://doi.org/10.4230/lipics.mfcs.2018.63
Conference Name | 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). |
---|---|
Conference Location | Liverpool, UK |
Start Date | Aug 27, 2018 |
End Date | Aug 31, 2018 |
Acceptance Date | Jun 25, 2018 |
Publication Date | Jan 1, 2018 |
Deposit Date | Jul 30, 2018 |
Publicly Available Date | Mar 29, 2024 |
Pages | 63:1-63:15 |
Series Title | Leibniz International Proceedings in Informatics |
Series Number | 117 |
Series ISSN | 1868-8969 |
Book Title | 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). |
DOI | https://doi.org/10.4230/lipics.mfcs.2018.63 |
Public URL | https://durham-repository.worktribe.com/output/1145032 |
Files
Published Conference Proceeding
(452 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Accepted Conference Proceeding
(452 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Viktor Zamaraev; licensed under Creative Commons License CC-BY
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
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