Parameterized Max Min Feedback Vertex Set
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00370181" target="_blank" >RIV/68407700:21240/23:00370181 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.MFCS.2023.62" target="_blank" >https://doi.org/10.4230/LIPIcs.MFCS.2023.62</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2023.62" target="_blank" >10.4230/LIPIcs.MFCS.2023.62</a>
Alternative languages
Result language
angličtina
Original language name
Parameterized Max Min Feedback Vertex Set
Original language description
Given a graph G and an integer k, Max Min FVS asks whether there exists a minimal set of vertices of size at least k whose deletion destroys all cycles. We present several results that improve upon the state of the art of the parameterized complexity of this problem with respect to both structural and natural parameters. Using standard DP techniques, we first present an algorithm of time tw^O(tw) n^O(1), significantly generalizing a recent algorithm of Gaikwad et al. of time vc^O(vc) n^O(1), where tw, vc denote the input graph’s treewidth and vertex cover respectively. Subsequently, we show that both of these algorithms are essentially optimal, since a vc^o(vc) n^O(1) algorithm would refute the ETH. With respect to the natural parameter k, the aforementioned recent work by Gaikwad et al. claimed an FPT branching algorithm with complexity 10^k n^O(1). We point out that this algorithm is incorrect and present a branching algorithm of complexity 9.34^k n^O(1).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science
ISBN
978-3-95977-292-1
ISSN
1868-8969
e-ISSN
—
Number of pages
15
Pages from-to
"62:1"-"62:15"
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl
Event location
Bordeaux
Event date
Aug 28, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—