Back to Search
Start Over
Parameterized Complexity of d-Hitting Set with Quotas
- Source :
- SOFSEM 2021: Theory and Practice of Computer Science ISBN: 9783030677305, SOFSEM
- Publication Year :
- 2021
- Publisher :
- Springer International Publishing, 2021.
-
Abstract
- In this paper we study a variant of the classic d -Hitting Set problem with lower and upper capacity constraints, say A and B, respectively. The input to the problem consists of a universe U, a set family, \(\mathscr {S} \), of sets over U, where each set in the family is of size at most d, a non-negative integer k; and additionally two functions \(\alpha :\mathscr {S} \rightarrow \{1,\ldots ,A\}\) and \(\beta :\mathscr {S} \rightarrow \{1,\ldots ,B\}\). The goal is to decide if there exists a hitting set of size at most k such that for every set S in the family \(\mathscr {S} \), the solution contains at least \(\alpha (S)\) elements and at most \(\beta (S)\) elements from S. We call this the \((A, B)\)-Multi d-Hitting Set problem. We study the problem in the realm of parameterized complexity. We show that \((A, B)\)-Multi d-Hitting Set can be solved in \(\mathcal {O}^{\star }(d^{k}) \) time. For the special case when \(d=3\) and \(d=4\), we have an improved bound of \(\mathcal {O}^\star (2.2738^k)\) and \(\mathcal {O}^\star (3.562^{k})\), respectively. The former matches the running time of the classical 3-Hitting Set problem. Furthermore, we show that if we do not have an upper bound constraint and the lower bound constraint is same for all the sets in the family, say \(A>1\), then the problem can be solved even faster than d-Hitting Set.
- Subjects :
- Physics
Star (game theory)
Parameterized complexity
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Upper and lower bounds
Running time
Set (abstract data type)
Combinatorics
Integer
010201 computation theory & mathematics
Kernelization
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Universe (mathematics)
Subjects
Details
- ISBN :
- 978-3-030-67730-5
- ISBNs :
- 9783030677305
- Database :
- OpenAIRE
- Journal :
- SOFSEM 2021: Theory and Practice of Computer Science ISBN: 9783030677305, SOFSEM
- Accession number :
- edsair.doi...........a49dbafe31c9e54e2b028bbf02d896db