0
$\begingroup$

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.

SUPPORTIVE 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?

$\endgroup$

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.