During research, I hit the following problem

Exact Cover Variant (ECV)

Input: Three set systems $S_1, S_2, S_3$ over a universe $U$, each closed with respect to $\cap$ and $\cup$.

Question: Is there an exact cover for $U$ consisting of sets in $S_1,S_2,S_3$?

This is easy. An important observation is that if there is an exact cover, then there is one consisting of at most one set of each set system (this is due to the closedness regarding $\cap$ and $\cup$). It hence suffices to iterate over all (polynomially many) possible solutions. So I will make the problem harder again. Instead of giving $S_1,S_2,S_3$ explicitly, it will be encoded in a multi-terminal network as follows:

Network Exact Cover (NEC)

Input: A 4-terminal network $N$ with node set $V$ and terminals $T=\{t_1,t_2,t_3,t_4\} \subseteq V$.

Question: Let $S_1,S_2,S_3$ be the source sides of all min-cuts separating $\{t_1,t_2\}, \{t_1,t_3\}, \{t_1,t_4\}$, respectively, from the remaining terminals. Is there an exact cover of $V-T$ using sets of $S_1,S_2,S_3$?

Due to the submodularity of min-cuts, the sets $S_1,S_2,S_3$ are closed with respect to $\cap$ and $\cup$ as well.

I cannot come up with a polynomial algorithm for NEC, neither can I proof NP-hardness (it clearly is in NP). Question: Do you have any ideas concerning NEC's complexity?

The reason NEC appears to be harder than ECV is that the number of elements of each set system may be exponential in $|V|$. Iterating over all possible solutions is not possible anymore. At the same time, these exponentially many min-cuts are given in a data structure (a network) that may make it easier to find a solution.

Also note that not for every three sets closed with respect to $\cap$ and $\cup$, there is a 4-terminal network encoding these sets in the above described way. This interdependency may be exploited (and at the same time makes it hard to find a reduction...).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.