Complexité des cliques colorées

Question

Donné:

1. graphique avec des bords colorés;

2. Liste des couleurs $ alpha $;

3. Liste des couleurs $ epsilon $;

4. Taille de la clique $ k $.

Problème:

1. Tous les bords colorés dans l'une des couleurs $ alpha $ sont-ils membres de cliques avec une taille $ k $?

2. N'y a-t-il pas un avantage de une couleur $ epsilon $ qui n'est pas contenue dans la clique de taille $ k $?

Exemple:

Compte tenu d'un graphique qui a des bords bleus, rouges, verts et magenta.

$ alpha $ couleurs: rouge, bleu.

$ epsilon $ couleurs: vert, magenta.

La réponse est oui si les deux conditions sont remplies:

1. Tous les bords rouges et bleus sont contenus dans des cliques de taille $ k $ (ou plus, bien sûr).

2. Il existe au moins un vert et Au moins un bord magenta contenu dans certaines cliques de taille $ k $.

Voici 2 cas spéciaux, pour les deux $ n = 10, k = 4, alpha $: rouge et bleu, $ epsilon $ - vert et magenta. La seule différence est la couleur du bord.

Le 1er graphique satisfait aux conditions: tous les bords rouges et bleus sont contenus dans des cliques à 4 vertex Abih, FGIJ, CDEF ainsi qu'elles contiennent au moins un vert et au moins un bord magenta.

Le 2ème graphique ne satisfait pas aux conditions car Blue Edge Be n'est pas un membre de la clique à 4 vertex.

Je pense que ce problème est PSPACE-COMPLET, mais je ne suis pas sûr de réduction de TQBF à cela. Si une telle réduction est possible, elle n'est pas similaire à la réduction connu SAT à max-clique.