0
$\begingroup$

Given:

  1. graph with colored edges;

  2. list of $\alpha$ colors;

  3. list of $\epsilon$ colors;

  4. clique size $k$.

Problem:

  1. Do all edges colored in one of $\alpha$ colors are members of cliques with size $k$?

  2. 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:

  1. All red and blue edges are contained in cliques of size $k$ (or larger, of course).

  2. 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.

Examples

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ @j_random_hacker, changed it to $\alpha$ and $\epsilon$. $\endgroup$
    – rus9384
    Commented May 26, 2017 at 13:46
  • $\begingroup$ a. When you say "Answer yes if 1. (...) 2. (...)", do you mean answer yes if both conditions hold? Or do you mean answer yes if at least one of the conditions hold? In other words, should we combine the conditions with AND, or with OR? b. What do you mean by "not only one of them"? $\endgroup$
    – D.W. ♦
    Commented May 26, 2017 at 14:46

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I know that $k$-clique is a subcase of my problem when only one $\epsilon$ color is given, as well as SAT is a subcase of TQBF when all quantifiers are $\exists$-quantifiers. Also, number of cliques is exponential, so, I'm not sure that certificate has polynomial length. $\endgroup$
    – rus9384
    Commented May 26, 2017 at 15:05
  • $\begingroup$ @rus9384, you only need one $k$-clique per edge, so the certificate has polynomial length. $\endgroup$
    – D.W. ♦
    Commented May 26, 2017 at 15:08
  • $\begingroup$ And what if $k$ can be any number? $\endgroup$
    – rus9384
    Commented May 26, 2017 at 15:09
  • $\begingroup$ @rus9384, yes, $k$ can be any number; it's part of the input. I'm not sure what you're getting at. $\endgroup$
    – D.W. ♦
    Commented May 26, 2017 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.