Planar Exact Cover by even-size sets 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). 


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