<p>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 <span class="math-container">$2k$</span> 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:</p>

<p><a href="https://photos.app.goo.gl/TMc49pfeT6RZA9Vb8" rel="nofollow noreferrer">https://photos.app.goo.gl/TMc49pfeT6RZA9Vb8</a></p>

<p>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.</p>

CC BY-SA 4.0
2019-07-01T05:09:40.420Z
Thanks a lot! I guess we cannot (easily) avoid 2-sets, right?
Yota Otachi
CC BY-SA 4.0
2019-07-01T05:26:47.603Z
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!
domotorp
CC BY-SA 4.0
2019-07-01T06:12:19.410Z
Wow, the memory has flashed back. It was a very good dinner :-)
Yota Otachi
CC BY-SA 4.0
2019-06-30T20:14:58.537Z
2019-06-30T20:14:58.537Z
domotorp
<p><strong>Major edit on June 6, 2019:</strong> Replaced the target problem with a simpler (but equivalent) one.</p>

<p>Is the following problem NP-complete?</p>

<blockquote>
  <p><strong>Planar Exact Cover by even-size sets</strong>  </p>
  
  <p><strong>Input:</strong> A set <span class="math-container">$U$</span>, a subset family <span class="math-container">$\mathcal{F} = \{F_1, \dots, F_{m}\} \subseteq 2^{U}$</span> with the two restrictions below.
  <strong>Question:</strong> Is there <span class="math-container">$\mathcal{F}' \subseteq \mathcal{F}$</span> such that each element of <span class="math-container">$U$</span> is included in exactly one set in <span class="math-container">$\mathcal{F}'$</span>?  </p>
  
  <p><strong>Restriction 1:</strong> The bipartite graph <span class="math-container">$B = (U, \mathcal{F}; \{\{u, F_{i}\} \mid u \in F_{i}\})$</span> is planar.<br>
  <strong>Restriction 2:</strong> <span class="math-container">$|F_{i}|$</span> is even for every <span class="math-container">$i$</span>.</p>
</blockquote>

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

<ol>
<li>Martin E. Dyer, Alan M. Frieze.
Planar 3DM is NP-Complete. Journal of Algorithms 7(2) 174-184 (1986).
<a href="https://doi.org/10.1016/0196-6774(86)90002-7" rel="nofollow noreferrer">doi:10.1016/0196-6774(86)90002-7</a></li>
</ol>

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

<hr />

<p>The old version of the problem is as follows:</p>

<blockquote>
  <p><strong>Planar Exact Cover by 2- and 4-sets (with at most three occurrences)</strong>  </p>
  
  <p><strong>Input:</strong> A set <span class="math-container">$U$</span>, a subset family <span class="math-container">$\mathcal{F} = \{F_1, \dots, F_{m}\} \subseteq 2^{U}$</span> with all three restrictions below.
  <strong>Question:</strong> Is there <span class="math-container">$\mathcal{F}' \subseteq \mathcal{F}$</span> such that each element of <span class="math-container">$U$</span> is included in exactly one set in <span class="math-container">$\mathcal{F}'$</span>?  </p>
  
  <p><strong>Restriction 1:</strong> The bipartite graph <span class="math-container">$B = (U, \mathcal{F}; \{\{u, F_{i}\} \mid u \in F_{i}\})$</span> is planar.<br>
  <strong>Old restriction 2:</strong> Each element of <span class="math-container">$U$</span> appears in at most three sets in <span class="math-container">$\mathcal{F}$</span>.<br>
  <strong>Old restriction 3:</strong> <span class="math-container">$|F_{i}| \in \{2,4\}$</span> for every <span class="math-container">$i$</span>.  </p>
</blockquote>

<p>The new problem can be reduced to the old one as follows.</p>

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

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

<p><strong>Correctness:</strong> The reductions preserve the answer and the planarity. See the figure below.</p>

<p><a href="https://i.sstatic.net/DMdcB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DMdcB.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2019-06-26T06:32:52.593Z
@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."
domotorp
CC BY-SA 4.0
2019-06-24T15:08:11.697Z
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$.
Marzio De Biasi
CC BY-SA 4.0
2019-06-25T02:49:42.253Z
@MarzioDeBiasi I think your reduction doesn't preserve the planarity.
Yota Otachi
CC BY-SA 4.0
2019-06-25T07:45:30.703Z
you're right ... we should examine the details of the planar X3C reduction if the doubling could work.
Marzio De Biasi
<cc.complexity-theory><np-hardness>
Planar Exact Cover by even-size sets
Yota Otachi
# Planar Exact Cover by even-size sets

(Asked by: username_0 on 2019-06-02)

**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](https://doi.org/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](https://i.sstatic.net/DMdcB.png)](https://i.sstatic.net/DMdcB.png)

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_2**: 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$.  
> **username_0**: @MarzioDeBiasi I think your reduction doesn't preserve the planarity.  
> **username_2**: you're right ... we should examine the details of the planar X3C reduction if the doubling could work.  
> **username_1**: @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."  

---

## 1 answers

### Answer by username_1 on 2019-06-30. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks a lot! I guess we cannot (easily) avoid 2-sets, right?  
> **username_1**: 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!  
> **username_0**: Wow, the memory has flashed back. It was a very good dinner :-)  

---

