Reducing 3-coloring problem to trio representatives

Question

A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each trio. Is such assignment possible?

My goal is to use polynomial-time reductions to transform 3-coloring of a graph into this problem. However, I'm stuck on the correct representation.

• If each vertex is a different student and edges represent being in the same trio, how do I separate trios?

• If each node represents a trio, what could be a sensible meaning of the edges?

I suspect that since a 4-clique has no adequate 3-coloring (which could also mean that 4 trios with the same three members have no possible representative assignment), the latter option could be more sensible, but I'm not sure on how to proceed with this reduction proof.

Answer 1

Let $G = (V,E)$ be an instance of $3$ coloring. Construct an instance $\phi$ of 3-SAT as follows.

• For each vertex $v \in V$ create $3$ variables $v_a, v_b, v_c$ representing the $3$ possible ways to color of $v$.
• For each vertex $v \in V$ create the clauses $(v_a \vee v_b \vee v_c) \wedge (\overline{v_a} \vee \overline {v_b}) \wedge (\overline{v_b} \vee \overline {v_c}) \wedge (\overline{v_c} \vee \overline {v_a})$. This encodes the fact that $v$ must be colored by exactly one color.
• For each edge $(u,v) \in E$ create the clauses $( \overline{v_a} \vee \overline{u_a} ) \wedge ( \overline{v_b} \vee \overline{u_b} ) \wedge ( \overline{v_c} \vee \overline{u_c} )$. This ensures that $u$ and $v$ cannot be given the same color.

Clearly the above reduction can be performed in poylnomial-time and ensures that there is a satisfying assignment to $\phi$ iff there is a 3-Coloring for $G$.

Now transform the instance $\phi$ of 3-SAT into an equivalent of instance $\phi'$ of 1-in-3 SAT (see here for the definition of 1-in-3 sat and the reduction from 3-SAT).

We have hence shown that 3-Coloring is polynomial-time reducible to 1-in-3 SAT. It turns out that 1-in-3 SAT is exactly your problem: the set of students is the set of variables and, for each clause $\{x_i, x_j, x_k\}$ you create a group containing students $x_i$, $x_j$, and $x_k$. Setting a variable to true corresponds to selecting the corresponding student as a leader.