Ridurre il problema di 3 colori per i rappresentanti del trio

Question

.

Un gruppo di studenti è suddiviso in trios - gruppi di 3 membri.Ogni studente può essere assegnato a più di più trio.Vogliamo assegnare i loro rappresentanti, scegliendo Esattamente uno membro di ciascun trio.È possibile un incarico di questo tipo?

Il mio obiettivo è utilizzare riduzioni di tempo polinomiale per trasformare 3-colorazione di un grafico in questo problema.Tuttavia, sono bloccato sulla rappresentazione corretta.

.

• Se ogni vertice è un diverso studente e bordi rappresentano essere nello stesso trio, come faccio a separare i trii?

• Se ogni nodo rappresenta un trio, quale potrebbe essere un significato ragionevole dei bordi?

Sospetto che dal momento che un 4-clique non abbia un adeguato 3 colorante (che potrebbe anche significare che 4 trii con gli stessi tre membri non hanno alcuna possibile assegnazione rappresentativa), quest'ultima opzione potrebbe essere più sensibile, ma non lo sonosicuro su come procedere con questa prova di riduzione.

Answer 1

Let $ g= (v, e) $ essere un'istanza di $ 3 $ colorazione. Costruisci un'istanza $ \ phi $ di 3-SAT come segue.

.
• per ogni vertice $ v \ in V $ Crea $ 3 $ variabili $ v_a, v_b, v_c $ che rappresenta la $ 3 $ possibili modi per il colore della $ V $ .
• per ogni vertice $ v \ in V $ Creare le clausole $ (v_a \ vee v_b \ vee v_c) \ cuneo (\ overline {v_a} \ vee \ overline {v_b}) \ wedge (\ overline {v_b} \ vee \ overline {v_c}) \ wedge (\ overline {v_c} \ vee \ overline {v_a}) $ . Questo codifica il fatto che $ V $ deve essere colorato da esattamente un colore.
• per ogni bordo $ (u, v) \ in e $ Creare le clausole $ (\ overline {v_a} \ Vee \ Overline {u_a}) \ wedge (\ overline {v_b} \ vee \ overline {u_b}) \ wedge (\ overline {v_c} \ Vee \ overline {u_c}) $ . Ciò garantisce che $ U $ e $ V $ non può essere somministrato lo stesso colore.

chiaramente la suddetta riduzione può essere eseguita in polienomial-time e garantisce che vi sia un incarico soddisfacente a $ \ phi $ IFC c'è un 3-coloring per < Span Class="Math-Container"> $ G $ .

Ora trasforma l'istanza $ \ PHI $ di 3-SAT in un equivalente di istanza $ \ PHI '$ < / span> di 1-in-3 sat (vedere qui per La definizione di 1-in-3 seduta e la riduzione da 3-SAT).

Abbiamo quindi mostrato che 3-colorazione è il tempo di polinomiale riducibile a 1-in-3 sat. Si scopre che 1-in-3 SAT è esattamente il tuo problema: il set di studenti è il set di variabili e, per ogni clausola $ \ {x_i, x_j, x_k \} $ Si crea un gruppo contenente studenti $ x_i $ , $ x_j $ e $ x_k $ . Impostazione di una variabile per true corrisponde a selezionare lo studente corrispondente come leader.