Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
We say that an undirected graph $G=(V, E)$ is special if for every vertex $v\in V$ and edge $\{u, w\}\in E$, it holds that $\{v, u\}\in E$ or $\{v, w\}\in E$. In other words, a graph is special if for every vertex $v$, the set of the vertices that are not neighbors to $v$ is an independent set.
Is the vertex cover problem still hard when restricted to special graphs? I tried considering the standard NP-hardness proof of the vertex cover problem, but the output graph is far from being special.
Your graph is a complete multi-partite graph, on which the solution is easy (choose all vertices except the ones in the largest part).
To see this, define a relation $\sim$ on $V$: $x \sim y$ if $\{x,y\} \notin E$. Clearly $x \sim x$, and if $x \sim y$ then $y \sim x$. If $x \sim y$ and $y \sim z$ then $x \sim z$: indeed, otherwise, $\{y,z\}$ is an edge but neither $\{x,y\}$ nor $\{x,z\}$ are. Thus $\sim$ is an equivalence relation. Denoting its equivalence classes by $V_1,\ldots,V_r$, the graph is a complete multi-partite graph with parts $V_1,\ldots,V_r$.
