On the parameterized complexity of Compact Set Packing
The Set Packing problem is, given a collection of sets ๐ฎ over a ground set ๐ฐ, 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 โโ, is there a collection ๐ฎ' โ๐ฎ: |๐ฎ'| = r such that the sets in ๐ฎ' are pairwise disjoint? Unfortunately, the problem is not fixed parameter tractable unless ๐ถ[1] = ๐ฅ๐ฏ๐ณ, and, in fact, an "enumeration" running time of |๐ฎ|^ฮฉ(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 (๐ฐ,๐ฎ) is "compact" if |๐ฐ| = f(r)ยทฮ(( log |๐ฎ|)), 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 |๐ฐ| = f(r)ยท o(log |๐ฎ|), PSP is in , while for |๐ฐ| = rยทฮ(log (|๐ฎ|)), the problem is W[1]-hard; moreover, assuming ETH, Compact PSP does not even admit |๐ฎ|^o(r/log r) time algorithm.
READ FULL TEXT