Advertisement
Published in:
2017 | OriginalPaper | Chapter
The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments
Authors : Arindam Biswas, Varunkumar Jayapaul, Venkatesh Raman, Srinivasa Rao Satti
Published in: Frontiers in Algorithmics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
A tournament is an orientation of a complete graph. For a positive integer d, a distance-d dominating set in a tournament is a subset S of vertices such that every vertex in \(V{\setminus }S\) is reachable by a path of length at most d from one of the vertices in S. When \(d=1\), the set is simply called a dominating set. While the complexity of finding a k-sized dominating set is complete for the complexity class LOGSNP and the parameterized complexity class W[2], it is well-known that every tournament on n vertices has a dominating set of size \(g(n) = \lg n - \lg \lg n + 2\) that can be found in \({{\mathrm{O}}}\left( n^2 \right) \) time. We first show that for any k, one can find a dominating set of size at most \( k + g(n)\) in \({{\mathrm{O}}}\left( n^2/k \right) \) time, and prove an (unconditional) lower bound of \(\varOmega (n^2/k)\) for any \(k > \epsilon \lg n\) for any \(\epsilon >0\). Hence in particular, we can find a \((1+\epsilon ) \lg n\) sized dominating set in the optimal \(\varTheta ({n^2/\lg n})\) time.
For distance-d dominating sets, it is known that any tournament has a distance-2 dominating set consisting of a single vertex. Such a vertex is called a king or a 2-king and can be found in \({{\mathrm{O}}}\left( n \sqrt{n} \right) \) time. It follows that there is a vertex, from which every other vertex is reachable by a path of length at most d for any \(d \ge 2\) and such a vertex is called a d-king. A d-king can be found in \({{\mathrm{O}}}\left( n^{1+1/2^{d-1}} \right) \) for any \(d \ge 2\) [3]. We generalize our result for dominating set to show that for \(d \ge 2\),
-
we can find a k-sized distance-d dominating set in a tournament in \({{\mathrm{O}}}\left( k(n/k)^{1+1/2^{d-1}} \right) \) time for any \(k \ge 1\), and
-
we can find a \((g(n) + k)\)-sized distance-d dominating set in a tournament using \({{\mathrm{O}}}\left( k(n/k)^{1+1/(2^d-1)} \right) \) time for any \(k \ge 1\).
The second algorithm provides a faster runtime for finding distance-d dominating sets that are larger than g(n). We also show that the second algorithm is optimal whenever \(k \ge \epsilon \lg n\) for any \(\epsilon > 0\).
Thus our algorithms provide tradeoffs between the (additive) approximation factor and the complexity of finding distance-d dominating sets in tournaments. For the problem of finding a d-king, we show some additional results.