Structurally Parameterized d-Scattered Set
Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2018), Structurally Parameterized d-Scattered Set, in Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus, Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Proceedings, Springer International Publishing : Cham, p. 292-305. 10.1007/978-3-030-00256-5_24
Type
Communication / ConférenceExternal document link
https://arxiv.org/abs/1709.02180v4Date
2018Conference title
44th International Workshop, WG 2018Conference date
2018-06Conference city
CottbusConference country
GermanyBook title
Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, ProceedingsBook author
Brandstädt, Andreas; Köhler, Ekkehard; Meer, KlausPublisher
Springer International Publishing
Published in
Cham
ISBN
978-3-030-00255-8
Number of pages
384Pages
292-305
Publication identifier
Metadata
Show full item recordAuthor(s)
Katsikarelis, IoannisLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In d -Scattered Set we are given an (edge-weighted) graph and are asked to select at least k vertices, so that the distance between any pair is at least d, thus generalizing Independent Set. We provide upper and lower bounds on the complexity of this problem with respect to various standard graph parameters. In particular, we show the following:For any d≥2, an O∗(dtw) -time algorithm, where tw is the treewidth of the input graph and a tight SETH-based lower bound matching this algorithm’s performance. These generalize known results for Independent Set.d -Scattered Set is W[1]-hard parameterized by vertex cover (for edge-weighted graphs), or feedback vertex set (for unweighted graphs), even if k is an additional parameter. A single-exponential algorithm parameterized by vertex cover for unweighted graphs, complementing the above-mentioned hardness.A 2O(td2) -time algorithm parameterized by tree-depth ( td ), as well as a matching ETH-based lower bound, both for unweighted graphs.We complement these mostly negative results by providing an FPT approximation scheme parameterized by treewidth. In particular, we give an algorithm which, for any error parameter ϵ>0 , runs in time O∗((tw/ϵ)O(tw)) and returns a d/(1+ϵ) -scattered set of size k, if a d-scattered set of the same size exists.Subjects / Keywords
Independent set; scattered setRelated items
Showing items related by title and author.
-
Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2022) Article accepté pour publication ou publié
-
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
-
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Article accepté pour publication ou publié
-
Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2019) Article accepté pour publication ou publié
-
Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2020) Article accepté pour publication ou publié