| Article ID: | iaor20102879 |
| Volume: | 36 |
| Issue: | 5 |
| Start Page Number: | 594 |
| End Page Number: | 596 |
| Publication Date: | Sep 2008 |
| Journal: | Operations Research Letters |
| Authors: | Woeginger Gerhard J, Hulett Heather, Will Todd G |
The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding maximization problem is known to be solvable in polynomial time.