Let $G = (V, E)$ be an undirected graph and $U \subseteq V$ some subset of its vertices. An induced graph $G[U]$ is graph created from $G$ by removing all vertices that are not part of the set $U$.

I want to find a polynomial time algorithm that has graph $G = (V, E)$ and integer $k$ as input and returns a maximum set $U \subseteq V$ with largest size such that all vertices of $G[U]$ have degree at most $k$.

My idea with greedy algorithm that removes vertices with largest degree or vertices connected with most vertices with degree greater than $k$ doesn't work.

Does anyone know how to solve this problem in polynomial time?

  • $\begingroup$ @PålGD I edited question, is it comprehensible for you now? $\endgroup$ – jason Jul 1 '20 at 10:30

Let $G$ be any graph and let $k = 0$.

This problem is, as you correctly pointed out in a comment, better known as Independent Set and is famously NP-complete.

It is therefore unlikely that there is an algorithm solving your problem (which is slightly more general) in polynomial time.

  • $\begingroup$ k and G is an input you cannot let it be whatever you want. Also i don't see how this would answer the question. $\endgroup$ – jason Jul 1 '20 at 12:22
  • $\begingroup$ Return largest possible subset of V such that for every (v1, v2) in that subset {v1, v2} is not an element of E. In other words largest set of vertices not connected by edge $\endgroup$ – jason Jul 1 '20 at 14:05
  • $\begingroup$ Ok I think I know what you ment by that. It leaves us with NP complete problem: en.wikipedia.org/wiki/Independent_set_(graph_theory) Thank you for help. $\endgroup$ – jason Jul 1 '20 at 14:27

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.