DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property:

For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\emptyset$, where $N(v)$ is the neighborhood of $v$.


Input: An undirected graph $G(V,E)$ and a natural number $k$

Output: YES if $G$ has a module $A\subseteq V$ with $|A|=k$, otherwise NO

What is the complexity of GRAPH-MODULE 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.