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")