Define: $$L=\{(G,k) : G\text{ has a vertex cover of size at most $k$, and a clique of size at least $k$}\}$$

I need to determine whether $L\in \mathrm{NPC}$ or $L\in \mathrm{P}$. I suspect that $L\in \mathrm{NPC}$, been trying to prove it by looking for a reduction from Vertex Cover, but couldn't find one.


The graphs with clique size at least $k$ and VC at most $k$ have a particular structure: They can be partitioned into three sets, $C$, $I$ and a singleton $\{s\}$; $G[C]$ is a clique, $G[I]$ is an independent set and $s$ is just a vertex. $G[C \cup I]$ is what's called a split graph.

Proof: If a graph $G$ contains a clique of size $k$, then that clique uses up (at least) $k-1$ of your vertex cover budget. Let $G,k$ be a yes instance and $C$ any $k$-clique. Observe that $G - C$ is a star with possibly isolated vertices.

There are two cases: $G-C$ has edges, and $G-C$ does not have edges. The latter case is trivial, since we can let $C$ be the solution. In the former case, $G-C$ is the star graph with isolates. Let $s$ be the vertex with non-zero degree.

Both these cases lead to polynomial recognition algorithm. The one in which $G-C$ is an independent set, is the case where $G$ is a split graph. The other case has one vertex $s$ for which $G-s$ is a split graph. Guess $s$, and you're back at case 1.

As xskxzr pointed out, there is not necessarily a unique "split partition", that is, a partitioning of a split graph into the vertex sets $C$ and $I$, however, there are at most $n$ such partitions, and you can try all. This leads in the end to an $O(n^3m)$ algorithm for VC∩C, which I'm sure can be improved.

  • 1
    $\begingroup$ If I understand you correctly, the reduction would be to add a clique of size $k$. but then if I use $k'=2k-1$ I would need a clique of size $2k-1$, and that's a problem. $\endgroup$ – John Apr 22 '19 at 13:35
  • $\begingroup$ I havn't heard of split graphs. Is there a simple polynomial algorithm to determine if a graph is a split graph? and if so, how can I use this information to solve my problem? $\endgroup$ – John Apr 22 '19 at 16:05

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.