Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable
| Autor: | Lokshtanov, Daniel, Surianarayanan, Vaishali |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: | |
| DOI: | 10.4230/lipics.fsttcs.2021.29 |
| Popis: | 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. LIPIcs, Vol. 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), pages 29:1-29:17 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|