In a directed graph (digraph) $G(V,A)$, a set of vertices $C\subseteq V$ is called a supportive clique if (1) for every $u\neq v$ in $C$, either $(u,v)\in A$ or $(v,u)\in A$ and (2) for every $u\in C$, there exists $v,w\in C$ such that $(u,v), (w,v)\in C$.

In other words, a supportive clique in digraph is a standard clique if we omit the direction of all arcs, when taking back into account the direction of arcs, every vertex in a supportive have at least an incoming arc from and an outgoing to other vertices in the clique.


Input: A digraph $G(V,A)$ and $k\in\mathbb{N}$

Output: YES if there exists a supportive clique of size $k$ in $G$, otherwise NO

What is the complexity of this problem?


Your Answer

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

Browse other questions tagged or ask your own question.