2021/11/11 by Gadekar, Ameet
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2111.06338
The Set Packing problem is, given a collection of sets 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 r ∈ \mathbb N, is there a collection S' ⊆ S: |S'| = r such that the sets in S' are pairwise disjoint? Unfortunately, the problem is not fixed parameter tractable unless W[1] = FPT, and, in fact, an "enumeration" running time of |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,S) is "compact" if |U| = f(r)⋅Θ(\textsfpoly( log |S|)), for some f(r) ≥ r. In the Compact Set Packing problem, we are given a compact instance of PSP. In this direction, we present a "dichotomy" result of PSP: When |U| = f(r)⋅ o(log |S|), PSP is in \textsfFPT, while for |U| = r⋅Θ(log (|S|)), the problem is W[1]-hard; moreover, assuming ETH, Compact PSP does not even admit |S|o(r/log r) time algorithm. Although certain results in the literature imply hardness of compact versions of related problems such as Set r-Covering and Exact r-Covering, these constructions fail to extend to Compact PSP. A novel contribution of our work is the identification and construction of a gadget, which we call Compatible Intersecting Set System pair, that is crucial in obtaining the hardness result for Compact PSP.