Planar Exact Cover by even-size sets

Question

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.

Answer 1

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.