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.

  • 1
    $\begingroup$ Can you share the motivation for this question? In what context did you encounter it? Are you able to credit the original source? $\endgroup$
    – D.W.
    Oct 29 '21 at 22:45
  • $\begingroup$ I came up with it, just curios whether the problem remains hard for such graphs. They seem to have many edges but perhaps not too many so that the problem remains hard. $\endgroup$
    – bbb3321
    Oct 30 '21 at 12:39

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$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.