Riduzione da una colorazione M a una M-partition

Question

Definisci una partizione M come: Dato un grafico non rilevato G= (V, E) e un intero J.Esistono una partizione dei vertici in M Parks {V1, V2, ..., VM} tale che almeno J dei bordi ha i loro endpoint in diverse parti della partizione?

Ho iniziato partizionando il grafico in parti K: ogni partizione rappresenta 1 colorazione del grafico.Da lì, ho pensato di ritornare tutti i bordi: quindi convertire tutti i bordi in non bordi e viceversa.Sono bloccato qui.Sono sulla strada giusta?Grazie.

Answer 1

per definizione, una classe $ m $ -Coloring è una funzione $ f: v \ to \ {1, \ punti, m \} $ in modo tale che $ \ forall u, v \ in v \; f (u)= f (v) \ implica (u, v) \ non \ in e $ . Ciò significa che almeno $ | e | $ i bordi hanno i loro endpoint in diversi set della partizione $ \ {v_1, \ punti, v_m \} $ di $ V $ con $ v_i={v \ in V: f (v)= I \} $ .

Al contrario, se c'è una partizione $ \ {v_1, \ dots, v_m \} $ di $ V $ tale che almeno $ | e | $ i bordi hanno i loro endpoint in diversi set, quindi la funzione $ f: v \ to \ \ \ \ \ {1, \ Dots, k \} $ , dove $ f (u) $ è l'esclusivo indice $ i_u \ in \ {1, \ dots, m \} $ in modo tale che $ u \ in a_ {i_u} $ , soddisfa $ \ forall u, v \ in v \; f (u)= f (v) \ implica (u, v) \ non \ in e $ .

Quanto sopra mostra che l'istanza $ g= (v, e) $ di $ m $ -Coloring può essere ridotto (riduzioni di KRT KARP) all'istanza $ \ Langle G, | e | \ Rangle $ di $ m $ -partition.