Imagine I have a graph $(V,E)$ of vertices $V$ and undirected edges $E$. Then a clique is a set of vertices $(v_1,...,v_n)$ such that that there is an edge between any pair $(v_i,v_j)$ of vertices inside this set $(v_1,...,v_n)$.

The problem of a maximum clique is finding a clique which contains as much vertices as possible and the problem is NP-complete.

Now imagine I have given a directed and acyclic graph. Then I can reorder the graph in such a way that there can only be an edge from $i$ to $j$ if $i<j$ (so the corresponding adjacency matrix would be an upper triangle matrix). Now I want to find a maximum set of vertices $(v_1,...,v_n)$ such that between any pair $(v_i,v_j)$ of vertices inside the set with $i<j$ there is a directed edge from $v_i$ to $v_j$ . It is somehow the directed version of the maximum clique problem. So e.g. if a clique set is given by $(v_1,v_2,v_3)$, then there must be an edge $v_1v_2$, $v_1v_3$ and $v_2v_3$.

Now I am of course wondering if this problem would still be NP-complete... Does anyone have an idea?

I just realized a mistake.... If I just change all directed in undirected edges then it reduces to a regular maximum clique problem, right? Hence, the problem is NP-complete?

  • $\begingroup$ Yes, you have just reduced it to a maximum clique problem for the underlying simple graph. $\endgroup$ – Morgan Rodgers Oct 22 '18 at 17:15
  • $\begingroup$ Yeah, my problem is actually a bit different, I have a directed graph that may contain cycles. And I want to find a "maximum directed clique" given some permutation. So depending on the permutation, I want a set of vertices where there is an edge between any pair of vertices from the vertex being first to the vertex being second under this permutation. This is more complex and obviously the case I asked is a special case when there are no cycles... $\endgroup$ – user299124 Oct 22 '18 at 17:21
  • $\begingroup$ So my problem should be NP-hard $\endgroup$ – user299124 Oct 22 '18 at 17:22
  • $\begingroup$ I am not sure if you get me... :-) But if you do and you have an idea how to use algorithms for the normal clique problem to my problem - let me know $\endgroup$ – user299124 Oct 22 '18 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy