7
$\begingroup$

Major edit on June 6, 2019: Replaced the target problem with a simpler (but equivalent) one.

Is the following problem NP-complete?

Planar Exact Cover by even-size sets

Input: A set $U$, a subset family $\mathcal{F} = \{F_1, \dots, F_{m}\} \subseteq 2^{U}$ with the two restrictions below. Question: Is there $\mathcal{F}' \subseteq \mathcal{F}$ such that each element of $U$ is included in exactly one set in $\mathcal{F}'$?

Restriction 1: The bipartite graph $B = (U, \mathcal{F}; \{\{u, F_{i}\} \mid u \in F_{i}\})$ is planar.
Restriction 2: $|F_{i}|$ is even for every $i$.

If we forget the 1st restriction, then the problem is NP-complete because of 4-dimensional matching. If we replace the 2nd restriction with "$|F_{i}| = 3$ for every $i$", then the problem is NP-complete as Planar Exact Cover by 3-sets is NP-complete (1).

  1. Martin E. Dyer, Alan M. Frieze. Planar 3DM is NP-Complete. Journal of Algorithms 7(2) 174-184 (1986). doi:10.1016/0196-6774(86)90002-7

Motivation: Such a restriction would be useful when subset gadgets can have only an even number of connections to the rest.


The old version of the problem is as follows:

Planar Exact Cover by 2- and 4-sets (with at most three occurrences)

Input: A set $U$, a subset family $\mathcal{F} = \{F_1, \dots, F_{m}\} \subseteq 2^{U}$ with all three restrictions below. Question: Is there $\mathcal{F}' \subseteq \mathcal{F}$ such that each element of $U$ is included in exactly one set in $\mathcal{F}'$?

Restriction 1: The bipartite graph $B = (U, \mathcal{F}; \{\{u, F_{i}\} \mid u \in F_{i}\})$ is planar.
Old restriction 2: Each element of $U$ appears in at most three sets in $\mathcal{F}$.
Old restriction 3: $|F_{i}| \in \{2,4\}$ for every $i$.

The new problem can be reduced to the old one as follows.

Reducing the number of occurrences: Assume that there is an element $u$ that appears in sets $F_{1}, F_{2}, \dots, F_{k}$ with $k \ge 4$. We replace $u$ with three new element $x, u_{1}, u_{2}$ and then replace $F_{1}, \dots, F_{k}$ with $D_{1} = \{u_{1}, x\}$, $D_{2} = \{x, u_{2}\}$, and $F_{i}'$ for $1 \le i \le k$ such that $F_{i}' = F_{i} \cup \{u_{1}\} \setminus \{u\}$ for $1 \le i \le 2$ and $F_{i}' = F_{i} \cup \{u_{2}\} \setminus \{u\}$ for $3 \le i \le k$. We can see that $u_{2}$ appears in $k-1$ sets.

Reducing set size: Assume that there is a set $F_{i} = \{u_{1}, u_{2}, \dots, u_{2k}\}$ with $k \ge 3$. We add two new elements $x, y$ to $U$ and then replace $F_{i}$ with three sets $F_{i}^{(1)} = \{u_{1}, u_{2}, u_{3}\} \cup \{x\}$, $F_{i}^{(2)} = \{x,y\}$, and $F_{i}^{(3)} = \{u_{4}, \dots, u_{2k}\} \cup \{y\}$. Observe that $|F_{i}^{(3)}| = 2k-2$.

Correctness: The reductions preserve the answer and the planarity. See the figure below.

enter image description here

$\endgroup$
  • $\begingroup$ You can simply double the problem: $U' = \{ x_1,..., x_n, x'_1,...,x'_n \}$ $F'_i = \{x_{i_1}, x_{i_2}, x_{i_3}\} \cup \{x'_{i_1}, x'_{i_2}, x'_{i_3}\}$ And you get a planar instance of X3C in which each $|F'_i| = 6$. $\endgroup$ – Marzio De Biasi Jun 24 at 15:08
  • 1
    $\begingroup$ @MarzioDeBiasi I think your reduction doesn't preserve the planarity. $\endgroup$ – Yota Otachi Jun 25 at 2:49
  • $\begingroup$ you're right ... we should examine the details of the planar X3C reduction if the doubling could work. $\endgroup$ – Marzio De Biasi Jun 25 at 7:45
  • 1
    $\begingroup$ @Marzio probably this won't follow from their method, as they write in the paper "We have proved the NP-completeness of Planar 3DM. However it must be stressed that this does not imply NP-completeness for k-dimensional matching (k DM) for k > 3 by the simple argument used in the general (i.e., nonplanar) case of this problem. This is due to the fact that this argument involves an essentially nonplanar construction. Thus we cannot conclude that Planar k DM is NP-complete for any k > 3, although we conjecture that this is the case." $\endgroup$ – domotorp Jun 26 at 6:32
3
+50
$\begingroup$

The problem seems to be NP-complete. My reduction is from Planar 1-in-3-SAT, just like in their paper. For each variable, take $2k$ vertices. Each of these is covered by two 4-sets and each 4-set covers two consecutive vertices. Thus, we need to take every second of the 4-sets for each variable, this corresponds to TRUE/FALSE. The other two vertices of the 4-sets are from the clauses. (If the number of negated and unnegated occurrences of some variable differs, then convert some of the 4-sets into 2-sets.) Each clause has 4 vertices; one in the center and the other three in a triangle. Any two vertices of the triangle are contained in a 4-set that belongs to its appropriate literal. The central vertex is in three 2-sets, one for each vertex of the triangle. Not sure how clear this was, so I've made a sketch:

https://photos.app.goo.gl/TMc49pfeT6RZA9Vb8

It is easy to see that this hypergraph is indeed planar. The proof of the reduction is also quite straight-forward. Let me know if you have any questions.

$\endgroup$
  • $\begingroup$ Thanks a lot! I guess we cannot (easily) avoid 2-sets, right? $\endgroup$ – Yota Otachi Jul 1 at 5:09
  • $\begingroup$ Don't mention it - I owed you after you were kind enough to stay for another beer with me after the WG 2015 dinner ;) I don't see how to get rid of 2-sets, it's a good question! $\endgroup$ – domotorp Jul 1 at 5:26
  • $\begingroup$ Wow, the memory has flashed back. It was a very good dinner :-) $\endgroup$ – Yota Otachi Jul 1 at 6:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.