0
$\begingroup$

My problem: Given a graph $G=(V, E)$ and an integer $\ell$,add a minimum number of edges to $G$ so that in the resulting graph every vertex has degree at least $\ell$.

Is there a polynomial-time algorithm for this? Is it NP-complete?

Thanks!

$\endgroup$
0

1 Answer 1

2
$\begingroup$

By complementing the graph, this problem is a special case of the following problem:

Given a graph $G=(V, E)$ and a desired degree $d_v$ for each vertex $v\in V$, find a maximum-size subset $E'$ of $E$ such that each vertex $v\in V$ has at most $d_v$ edges in $E'$.

Polynomial-time algorithms for this problem (e.g. by reduction to maximum matching) are discussed in the paper "Another look at the degree constrained subgraph problem" by Yossi Shiloach, https://doi.org/10.1016/0020-0190(81)90009-0.

$\endgroup$
2

Your Answer

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

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