On the parameterized complexity of Compact Set Packing

11/11/2021
โˆ™
by   Ameet Gadekar, et al.
โˆ™
0
โˆ™

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

Please sign up or login with your details

Forgot password? Click here to reset