Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs

Mark T. de Berg; Sándor Kisfaludi-Bak

doi:10.1007/978-3-030-42071-0_5

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs

Mark T. de Berg, Sándor Kisfaludi-Bak

Algorithms, Geometry and Applications

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

1 Citation (Scopus)

Abstract

Recently it was shown that many classic graph problems—Independent Set, Dominating Set, Hamiltonian Cycle, and more—can be solved in subexponential time on unit-ball graphs. More precisely, these problems can be solved in 2O(n1−1/d) time on unit-ball graphs in Rd , which is tight under ETH. The result can be generalized to intersection graphs of similarly-sized fat objects.

For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove that
there is no algorithm with running time 2o(n) for Dominating Set on (non-unit) ball graphs in R3 ;

there is no algorithm with running time 2o(n) for Weighted Dominating Set on unit-ball graphs in R3 ;

there is no algorithm with running time 2o(n) for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.

Original language	English
Title of host publication	Treewidth, Kernels, and Algorithms
Editors	F. Fomin, S. Kratsch, E. van Leeuwen
Pages	31-48
Number of pages	18
ISBN (Electronic)	978-3-030-42071-0
DOIs	https://doi.org/10.1007/978-3-030-42071-0_5
Publication status	Published - 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12160 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-030-42071-0_5

Cite this

de Berg, M. T., & Kisfaludi-Bak, S. (2020). Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs. In F. Fomin, S. Kratsch, & E. van Leeuwen (Eds.), Treewidth, Kernels, and Algorithms (pp. 31-48). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12160 LNCS). https://doi.org/10.1007/978-3-030-42071-0_5

de Berg, Mark T. ; Kisfaludi-Bak, Sándor. / Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs. Treewidth, Kernels, and Algorithms. editor / F. Fomin ; S. Kratsch ; E. van Leeuwen. 2020. pp. 31-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{b36aa7c66b8341029659878d2c81bb26,

title = "Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs",

abstract = "Recently it was shown that many classic graph problems—Independent Set, Dominating Set, Hamiltonian Cycle, and more—can be solved in subexponential time on unit-ball graphs. More precisely, these problems can be solved in 2O(n1−1/d) time on unit-ball graphs in Rd , which is tight under ETH. The result can be generalized to intersection graphs of similarly-sized fat objects.For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove thatthere is no algorithm with running time 2o(n) for Dominating Set on (non-unit) ball graphs in R3 ;there is no algorithm with running time 2o(n) for Weighted Dominating Set on unit-ball graphs in R3 ;there is no algorithm with running time 2o(n) for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.",

author = "{de Berg}, {Mark T.} and S{\'a}ndor Kisfaludi-Bak",

year = "2020",

doi = "10.1007/978-3-030-42071-0_5",

language = "English",

isbn = "978-3-030-42070-3",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "31--48",

editor = "F. Fomin and S. Kratsch and {van Leeuwen}, E.",

booktitle = "Treewidth, Kernels, and Algorithms",

}

de Berg, MT & Kisfaludi-Bak, S 2020, Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs. in F Fomin, S Kratsch & E van Leeuwen (eds), Treewidth, Kernels, and Algorithms. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12160 LNCS, pp. 31-48. https://doi.org/10.1007/978-3-030-42071-0_5

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs. / de Berg, Mark T.; Kisfaludi-Bak, Sándor.

Treewidth, Kernels, and Algorithms. ed. / F. Fomin; S. Kratsch; E. van Leeuwen. 2020. p. 31-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12160 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs

AU - de Berg, Mark T.

AU - Kisfaludi-Bak, Sándor

PY - 2020

Y1 - 2020

N2 - Recently it was shown that many classic graph problems—Independent Set, Dominating Set, Hamiltonian Cycle, and more—can be solved in subexponential time on unit-ball graphs. More precisely, these problems can be solved in 2O(n1−1/d) time on unit-ball graphs in Rd , which is tight under ETH. The result can be generalized to intersection graphs of similarly-sized fat objects.For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove thatthere is no algorithm with running time 2o(n) for Dominating Set on (non-unit) ball graphs in R3 ;there is no algorithm with running time 2o(n) for Weighted Dominating Set on unit-ball graphs in R3 ;there is no algorithm with running time 2o(n) for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.

AB - Recently it was shown that many classic graph problems—Independent Set, Dominating Set, Hamiltonian Cycle, and more—can be solved in subexponential time on unit-ball graphs. More precisely, these problems can be solved in 2O(n1−1/d) time on unit-ball graphs in Rd , which is tight under ETH. The result can be generalized to intersection graphs of similarly-sized fat objects.For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove thatthere is no algorithm with running time 2o(n) for Dominating Set on (non-unit) ball graphs in R3 ;there is no algorithm with running time 2o(n) for Weighted Dominating Set on unit-ball graphs in R3 ;there is no algorithm with running time 2o(n) for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.

UR - http://www.scopus.com/inward/record.url?scp=85090021915&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-42071-0_5

DO - 10.1007/978-3-030-42071-0_5

M3 - Chapter

SN - 978-3-030-42070-3

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 31

EP - 48

BT - Treewidth, Kernels, and Algorithms

A2 - Fomin, F.

A2 - Kratsch, S.

A2 - van Leeuwen, E.

ER -

de Berg MT, Kisfaludi-Bak S. Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs. In Fomin F, Kratsch S, van Leeuwen E, editors, Treewidth, Kernels, and Algorithms. 2020. p. 31-48. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-42071-0_5

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this