6
$\begingroup$

According to a conjecture:

Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.

Equivalent statement here

Main question:

Given a bridgeless cubic graph $G$, can one find in polynomial or subexponential time three perfect matchings with no edge in common or answer no solution?


Partial results.

I encoded the problem in SAT.

The encoding of PM to SAT boils down to ONE-IN-K SAT with exactly two occurrences of a variable and the inverse encoding is possible too (there are papers on this).

To encode to SAT I work with three copies of $G$: $A,B,C$.

For each edge $e \in E(G)$ introduce three boolean variables $A_e,B_e,C_e$ and encode perfect matchings in $A,B,C$.

For empty intersection, for all edges $e \in E(G)$ add the clauses:

$$ \lnot A_e \lor \lnot B_e \lor \lnot C_e \qquad (1) $$

Experimentally good SAT solvers solve this encoding fast.

Is there some gadget that encodes the constraints (1) as matching problem, so the full solution of (1) and PMs in $A,B,C$ is a PM or maximum weighted matching?

I suspect such gadget doesn't exist.

$\endgroup$
  • $\begingroup$ The proposed gadget appears wrong. The problem is A_e shares vertices in A and choosing an $n$ edge kills more than wanted edges in $A$. $\endgroup$ – joro Dec 17 '13 at 8:09

Your Answer

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

Browse other questions tagged or ask your own question.