# Solving a variant of the Exact cover problem

I am trying to solve a variant of the Exact cover problem where every element has to be covered exactly twice instead of once ( i.e. has to be in exactly two sets that are part of the cover).

Now, it is clear to me that this is an NP-complete problem, but I wish to know if there is any hope for some pseudo-polynomial time algorithm to solve this problem.

If relevant, the context arose from trying to recreate polyhedra from their edges: given a set of edges, decide if they constitute some polyhedron, and if they do, give a set of its faces. Thus the set I wish to cover is the set of edges, and the collection of subsets I have is that of objects that can possibly be faces (each containing the edges of the corresponding "face")

• Maybe there are some useful constraints on your sets (faces) that can be exploited: E.g., is it true that no two faces share 2 or more edges? Is every induced cycle a face, and every face an induced cycle? I actually don't see how an edge from a polyhedron could belong to anything other than exactly 2 faces, which if true, at least gives you an easy-to-test necessary condition. May 19 '18 at 15:17
• 1) no, the input is given such that edges are segments in 3D Euclidean space, so anything that might be a face has to be an induced cycle that has all its edges lying in a single plane. May 21 '18 at 3:41
• 2) this is exactly what the problem involves: checking which objects that are such cycles as in 1) are the faces of the polyhedron, hence the twice exact cover May 21 '18 at 3:44

For instance, here's an easy reduction. Given an instance $(S,X)$ of exact cover (where $S$ is a collection of subsets of $X$), let $X' = X \cup \{a\}$ where $a \notin X$ is a new symbol, and $S' = S \cup \{X', \{a\}\}$. Now there is a twice-exact-cover for $(S',X')$ iff there is an exact cover for $(S,X)$. So, if you could solve twice-exact-cover in pseudopolynomial time, you could solve exact cover in pseudopolynomial time, too.