1
$\begingroup$

Let $G=(V,E)$ be an undirected graph in which $V = \{v_1,v_2,\dots,v_n\}$.

I need to describe a reduction from the 2-coloring problem to the 2-SAT problem (in polynomial time).

I thought of splitting each vertex $v_i$ into $v_i^*$ and $v_i^{**}$, one for each color. Then I was thinking about making for each edge $(u,v)\in E$, two correspond literals: $(u^* \lor v^*)$ and $(u^{**} \lor v^{**})$.

I know I'm on the right track but I can't prove it.

any ideas?

$\endgroup$
2
$\begingroup$

If all you require is a polynomial-time reduction, then test in polynomial time if $G$ is $2$-colourable. If it is, map it to the formula $X$; if it isn't, map it to $X\land\lnot X$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Consider a graph $G=(V,E)$.

Given a node $v_i \in V$ as you did, you can split into 2 variables $v_{i,1}$ and $v_{i,2}$ representing the 2 colors.

Now you just need 3 kind of clauses:

  • each node cannot have more than one color
  • Each node must have assigned a color
  • $\forall$ edge $(u,v) \in E$, $u$ and $v$ cannot have the same color.

Then you just have to write it as a conjunction of clauses, where each clause is a disjunction of 2 literals.

G admits a 2-coloring $\iff$ there exists a truth assignment that satisfy the formula.

| cite | improve this answer | |
$\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.