License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.29
URN: urn:nbn:de:0030-drops-155404
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15540/
Lokshtanov, Daniel ;
Surianarayanan, Vaishali
Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable
Abstract
In the Dominating Set problem the input is a graph G and an integer k, the task is to determine whether there exists a vertex set S of size at most k so that every vertex not in S has at least one neighbor in S. We consider the parameterized complexity of the Dominating Set problem, parameterized by the solution size k, and the weak closure of the input graph G. Weak closure of graphs was recently introduced by Fox et al. [SIAM J. Comp. 2020 ] and captures sparseness and triadic closure properties found in real world graphs. A graph G is weakly c-closed if for every induced subgraph G' of G, there exists a vertex v ∈ V(G') such that every vertex u in V(G') which is non-adjacent to v has less than c common neighbors with v. The weak closure of G is the smallest integer γ such that G is weakly γ-closed. We give an algorithm for Dominating Set with running time k^O(γ² k³) n^O(1), resolving an open problem of Koana et al. [ISAAC 2020].
One of the ingredients of our algorithm is a proof that the VC-dimension of (the set system defined by the closed neighborhoods of the vertices of) a weakly γ-closed graph is upper bounded by 6γ. This result may find further applications in the study of weakly closed graphs.
BibTeX - Entry
@InProceedings{lokshtanov_et_al:LIPIcs.FSTTCS.2021.29,
author = {Lokshtanov, Daniel and Surianarayanan, Vaishali},
title = {{Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {29:1--29:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-215-0},
ISSN = {1868-8969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15540},
URN = {urn:nbn:de:0030-drops-155404},
doi = {10.4230/LIPIcs.FSTTCS.2021.29},
annote = {Keywords: Dominating Set, Weakly Closed Graphs, FPT, Domination Cores, VC-dimension}
}
|
Keywords: |
|
Dominating Set, Weakly Closed Graphs, FPT, Domination Cores, VC-dimension |
|
Collection: |
|
41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
29.11.2021 |
