3
$\begingroup$

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?

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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, 2020 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, 2020 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, 2020 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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