Complessità delle cricche colorate

Question

Dato:

1. grafico con bordi colorati;

2. Elenco di $ alpha $ colori;

3. Elenco di $ Epsilon $ Colors;

4. cricca taglia $ k $.

Problema:

1. Tutti i bordi colorati in uno dei colori $ alpha $ sono membri di cricche con taglia $ k $?

2. Non c'è un vantaggio di un colore $ epsilon $ che non è contenuto in cricca di dimensioni $ k $?

Esempio:

Dato un grafico che ha bordi blu, rossi, verdi e magenta.

$ alpha $ colori: rosso, blu.

$ Epsilon $ Colori: verde, magenta.

La risposta è sì se entrambe le condizioni sono soddisfatte:

1. Tutti i bordi rossi e blu sono contenuti in cricche di dimensioni $ k $ (o più grandi, ovviamente).

2. Esiste almeno un verde e Almeno un bordi magenta contenuti in alcune cricche di taglia $ k $.

Ecco 2 casi speciali, per entrambi $ n = 10, k = 4, alpha $: rosso e blu, $ epsilon $ - verde e magenta. L'unica differenza è il colore del bordo.

Il primo grafico soddisfa le condizioni: tutti i bordi rossi e blu sono contenuti nelle cricche a 4 vertex Abih, FGIJ, CDEF e contengono almeno un bordo verde e almeno un bordo magenta.

Il 2 ° grafico non soddisfa le condizioni perché Blue Edge non è un membro della cricca a 4 Vertex.

Penso che questo problema sia completo PSPACE, ma non sono sicuro della riduzione da TQBF a questo. Se tale riduzione è possibile, non è simile alla riduzione sat a max-clique.