3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – j_random_hacker May 19 '18 at 15:17
  • $\begingroup$ 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. $\endgroup$ – Ron Tubman May 21 '18 at 3:41
  • $\begingroup$ 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 $\endgroup$ – Ron Tubman May 21 '18 at 3:44
1
$\begingroup$

There's no pseudopolynomial algorithm for exact cover (unless P=NP), so it is easy to show that this implies there is no pseudopolynomial algorithm for twice-exact-cover, either.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.