• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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érence
External document link
https://arxiv.org/abs/1709.02180v4
Date
2018
Conference title
44th International Workshop, WG 2018
Conference date
2018-06
Conference city
Cottbus
Conference country
Germany
Book title
Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Proceedings
Book author
Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus
Publisher
Springer International Publishing
Published in
Cham
ISBN
978-3-030-00255-8
Number of pages
384
Pages
292-305
Publication identifier
10.1007/978-3-030-00256-5_24
Metadata
Show full item record
Author(s)
Katsikarelis, Ioannis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael cc
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 set

Related items

Showing items related by title and author.

  • Thumbnail
    Structurally parameterized d -scattered set 
    Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2022) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Complexity of Safe Set 
    Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
  • Thumbnail
    Parameterized Complexity of Safe Set 
    Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Article accepté pour publication ou publié
  • Thumbnail
    Structural parameters, tight bounds, and approximation for (k,r)-center 
    Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2019) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Orientable Deletion 
    Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2020) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo