Given:graph with colored edges;list of $\alpha$ colors;list of $\epsilon$ colors;clique size $k$.Problem:Do all edges colored in one of $\alpha$ colors are members of cliques with size $k$?Isn't there an edge of some of $\epsilon$ color that is not contained in clique of size $k$?Example:Given some graph that has blue, red, green and magenta edges.$\alpha$ colors: red, blue.$\epsilon$ colors: green, magenta.Answer is yes if both conditions are satisfied:All red and blue edges are contained in cliques of size $k$ (or larger, of course).There exists at least one green and at least one magenta edges that are contained in some cliques of size $k$.Here are 2 special cases, for both $n = 10, k = 4, \alpha$: red and blue, $\epsilon$ - green and magenta. The only difference is color of edge BE.1st graph satisfies the conditions: all red and blue edges are contained in 4-vertex cliques ABIH, FGIJ, CDEF as well as they contain at least one green and at least one magenta edge.2nd graph doesn't satisfy the conditions because blue edge BE is not a member of 4-vertex clique.I think this problem is PSPACE-complete but I'm not sure about reduction from TQBF to this. If such reduction is possible, it is not similar to known SAT to max-clique reduction.
Colored cliques complexity
complexity theory;graphs;clique
Your problem is in NP.  (A certificate for a yes answer is to list one of the $k$-cliques that each edge is contained in.)  Therefore, it's not likely to be PSPACE-complete: if it were PSPACE-complete, that would imply NP = PSPACE, which would be surprising.Your problem is NP-complete.  It is at least as hard as the $k$-clique problem. Suppose we have a graph and we want to know whether it contains a $k$-clique.  Then we can color all edges green, let $\alpha$ be the empty list, and let $\epsilon$ be the list containing only the color green.  Now the graph has a $k$-clique if and only if the answer to your problem is yes.  But testing for a $k$-clique is NP-complete, so it follows that your problem is NP-complete too.