I'm interested in the complexity status of the following problem.

Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$.

Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality at most $k$ such that the maximum degree of $G-E' = (V,E \setminus E')$ is at most $d$. No, otherwise.


Equivalently, your problem may be stated as follows: You are looking for a subgraph, in which every vertex degree lies in the interval $[0,d]$ and that contains as many edges as possible.

This problem is well-known to be solvable in polynomial time.
For instance, it is discussed in Chapter 10 (and in particular in Exercise 10.1.4) of the book

M.D. Plummer and L. Lovász:
Matching Theory
Volume 29 of Annals of Discrete Mathematics, Elsevier, 1986.

| cite | improve this answer | |
  • $\begingroup$ Thanks, Gamow! It is exactly what I was looking for. $\endgroup$ – Victor Mar 30 '19 at 14:11
  • $\begingroup$ Gamow, isn't Exercise 10.1.4 about (inclusion-wise) maximal subgraph $H$? How do we derive the desired result about a subgraph that contains as many edges as possible? $\endgroup$ – Victor Mar 30 '19 at 19:07
  • $\begingroup$ @Victor: No, no, no. Just study the chapter, and you will see that it discusses the max-cardinality version. (Finding an inclusion-wise maximal subgraph would be trivial, and far below the level of Lovasz and Plummer.) $\endgroup$ – Gamow Mar 30 '19 at 20:11
  • $\begingroup$ Gamow, indeed, finding an inclusion-wise maximal subgraph is trivial. I was just confused by the fact that the terms "maximal" and "minimal" are defined in the inclusion-wise sense in the book. $\endgroup$ – Victor Mar 30 '19 at 21:23

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.