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%2F25%3A00389716" target="_blank" >RIV/68407700:21240/25:00389716 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1137/23M1605247" target="_blank" >https://doi.org/10.1137/23M1605247</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/23M1605247" target="_blank" >10.1137/23M1605247</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 dynamic programming techniques, we first present an algorithm of time twO(tw)nO(1), significantly generalizing a recent algorithm of Gaikwad et al. of time vcO(vc)nO(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 vco(vc)nO (1) algorithm would refute the Exponential Time Hypothesis. With respect to the natural parameter k, the aforementioned recent work by Gaikwad et al. claimed a fixed-parameter tractable branching algorithm with complexity 10knO(1). We point out that this algorithm is incorrect and present a branching algorithm of complexity 9.34knO(1).
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
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
2025
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
Name of the periodical
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
1095-7146
Volume of the periodical
39
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
34
Pages from-to
1587-1620
UT code for WoS article
001565641100002
EID of the result in the Scopus database
2-s2.0-105014200398