<p>Equivalently, your problem may be stated as follows: You are looking for a subgraph, in which every vertex degree lies in the interval <span class="math-container">$[0,d]$</span> and that contains as many edges as possible. </p>

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

<blockquote>
  <p>M.D. Plummer and L. Lovász:<br>
  Matching Theory<br>
  Volume 29 of Annals of Discrete Mathematics, Elsevier, 1986.</p>
</blockquote>

CC BY-SA 4.0
2019-03-30T14:11:18.433Z
Thanks, Gamow! It is exactly what I was looking for.
Victor
CC BY-SA 4.0
2019-03-30T19:07:32.967Z
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?
Victor
CC BY-SA 4.0
2019-03-30T20:11:19.073Z
@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.)
Gamow
CC BY-SA 4.0
2019-03-30T21:23:09.503Z
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.
Victor
CC BY-SA 4.0
2019-03-30T13:49:15.340Z
2019-03-30T13:49:15.340Z
Gamow
<p>I'm interested in the complexity status of the following problem. </p>

<p><strong>Input</strong>: a graph <span class="math-container">$G=(V,E)$</span> and two natural numbers <span class="math-container">$k$</span> and <span class="math-container">$d$</span>.</p>

<p><strong>Output</strong>: Yes, if there exists a subset <span class="math-container">$E' \subseteq E$</span> of cardinality at most <span class="math-container">$k$</span> such that the maximum degree of <span class="math-container">$G-E' = (V,E \setminus E')$</span> is at most <span class="math-container">$d$</span>. No, otherwise.</p>

<cc.complexity-theory><reference-request><graph-algorithms>
Complexity status of the Edge Deletion problem to bounded degree graphs
Victor
# Complexity status of the Edge Deletion problem to bounded degree graphs

(Asked by: username_0 on 2019-03-29)

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.

**Tags:** cc.complexity-theory, reference-request, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2019-03-30. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks, username_1! It is exactly what I was looking for.  
> **username_0**: username_1, 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?  
> **username_1**: @username_0: 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.)  
> **username_0**: username_1, 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.  

---

