• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Structurally Parameterized d-Scattered Set

Thumbnail
Date
2018
Notes
LNCS n°11159
Link to item file
https://arxiv.org/abs/1709.02180v4
Dewey
Programmation, logiciels, organisation des données
Sujet
Independent set; scattered set
DOI
http://dx.doi.org/10.1007/978-3-030-00256-5_24
Conference name
44th International Workshop, WG 2018
Conference date
06-2018
Conference city
Cottbus
Conference country
Germany
Book title
Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Proceedings
Author
Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus
Publisher
Springer International Publishing
Publisher city
Cham
Year
2018
Pages number
384
ISBN
978-3-030-00255-8
Book URL
10.1007/978-3-030-00256-5
URI
https://basepub.dauphine.fr/handle/123456789/19041
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Katsikarelis, Ioannis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
292-305
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.