On the Parameterized Complexity of Compact Set Packing
Ameet Gadekar · Algorithmica · 2024
Abstract The Set Packing problem is, given a collection of sets $$\mathcal {S}$$ S over a ground set U, to find a maximum collection of sets that are pairwise disjoint. The problem is among the most fundamental NP-hard optimization problems that have been studied extensively in various computational regimes. The focus of this work is on parameterized complexity, Parameterized Set Packing (PSP): Given parameter $$r \in {\mathbb N}$$ r ∈ N , is there a collection $$ \mathcal {S}' \subseteq \mathcal {S}: |\mathcal {S}'| = r$$ S ′ ⊆ S : | S ′ | = r such that the sets in $$\mathcal {S}'$$ S ′ are pairwise disjoint? Unfortunately, the problem is not fixed parameter tractable unless $$\textsf {W[1]} = \textsf {FPT} $$ W [ 1 ] = FPT , and, in fact, an “enumerative” running time of $$|\mathcal {S}|^{\Omega (r)}$$ | S | Ω ( r ) is required unless the exponential time hypothesis (ETH) fails. This paper is a quest for tractable instances of Set Packing from parameterized complexity perspectives. We say that the input $$({U},\mathcal {S})$$ ( U , S ) is “compact” if $$|{U}| = f(r)\cdot \textsf {poly} ( \log |\mathcal {S}|)$$ | U | = f ( r ) · poly ( log | S | ) , for some $$f(r) \ge r$$ f ( r ) ≥ r . In the Compact PSP problem, we are given a compact instance of PSP. In this direction, we present a “dichotomy” result of PSP: When $$|{U}| = f(r)\cdot o(\log |\mathcal {S}|)$$ | U | = f ( r ) · o ( log | S | ) , PSP is in , while for $$|{U}| = r\cdot \Theta (\log (|\mathcal {S}|))$$ | U | = r · Θ ( log ( | S | ) ) , the problem is -hard; moreover, assuming ETH, Compact PSP does not admit $$|\mathcal {S}|^{o(r/\log r)}$$ | S | o ( r / log r ) time algorithm even when $$|{U}| = r\cdot \Theta (\log (|\mathcal {S}|))$$ | U | = r · Θ ( log ( | S | )<