# Optimization and Reconstruction over Graphs

### Samantha J. Riesenfeld

### EECS Department, University of California, Berkeley

### Technical Report No. UCB/EECS-2008-6

### January 14, 2008

### http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-6.pdf

We study several instances of the following combinatorial optimization problem: Efficiently find a graph that satisfies, to the extent possible, a given set of constraints. The thesis begins with two NP-hard problems: The Minimum-Degree Minimum Spanning Tree (MDMST) problem is to find, given a graph, an MST of minimum degree. The Minimum Bounded-Degree Spanning Tree (MBDST) problem is to find, given a graph and an integer B, a minimum-cost tree in the set of spanning trees of degree at most B. We present the first polynomial-time constant-factor approximation algorithm for the MDMST problem, which uses the push-relabel framework developed by Goldberg [20] for the max-flow problem. It improves Fischer¿s local-search algorithm [14]. Via an analysis by Konemann and Ravi [34], our algorithm implies the first polynomialtime constant-factor bi-criteria approximation algorithm for the MBDST problem. It also works for a new generalization of the MDMST problem. Other results include the first true MBDST approximation algorithms: a polynomial-time algorithm incurring no error in cost, and a quasi-polynomial-time algorithm, based on augmenting paths, that significantly improves the error in degree by finding a spanning tree of optimal cost and degree B+O(log n log log n). Our cost-bounding method requires finding MSTs that meet both upper and lower degree bounds.

The second part of the thesis considers the problem of reconstructing a directed graph, given the vertices and an oracle for the reachability relation. We show this reduces to the problem of sorting a partially ordered set (poset). Sorting algorithms obtain information about a poset by queries that compare two elements. We give an algorithm that sorts a width-w poset of size n and has query complexity O(wn + n log n), meeting the information-theoretic lower bound. We describe a variant of Mergesort that has query complexity O(wnlogn), matching the upper bound shown by Faigle and Turan [13], and total complexity O(w^2 n log n). The exact total complexity of sorting remains unresolved. We also give upper and lower bounds for several related problems, including finding the minimal elements in a poset, which we show has query and total complexity Theta(wn), and its generalization, k-selection.

**Advisors:** Richard M. Karp

BibTeX citation:

@phdthesis{Riesenfeld:EECS-2008-6, Author= {Riesenfeld, Samantha J.}, Title= {Optimization and Reconstruction over Graphs}, School= {EECS Department, University of California, Berkeley}, Year= {2008}, Month= {Jan}, Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-6.html}, Number= {UCB/EECS-2008-6}, Abstract= {We study several instances of the following combinatorial optimization problem: Efficiently find a graph that satisfies, to the extent possible, a given set of constraints. The thesis begins with two NP-hard problems: The Minimum-Degree Minimum Spanning Tree (MDMST) problem is to find, given a graph, an MST of minimum degree. The Minimum Bounded-Degree Spanning Tree (MBDST) problem is to find, given a graph and an integer B, a minimum-cost tree in the set of spanning trees of degree at most B. We present the first polynomial-time constant-factor approximation algorithm for the MDMST problem, which uses the push-relabel framework developed by Goldberg [20] for the max-flow problem. It improves Fischer¿s local-search algorithm [14]. Via an analysis by Konemann and Ravi [34], our algorithm implies the first polynomialtime constant-factor bi-criteria approximation algorithm for the MBDST problem. It also works for a new generalization of the MDMST problem. Other results include the first true MBDST approximation algorithms: a polynomial-time algorithm incurring no error in cost, and a quasi-polynomial-time algorithm, based on augmenting paths, that significantly improves the error in degree by finding a spanning tree of optimal cost and degree B+O(log n log log n). Our cost-bounding method requires finding MSTs that meet both upper and lower degree bounds. The second part of the thesis considers the problem of reconstructing a directed graph, given the vertices and an oracle for the reachability relation. We show this reduces to the problem of sorting a partially ordered set (poset). Sorting algorithms obtain information about a poset by queries that compare two elements. We give an algorithm that sorts a width-w poset of size n and has query complexity O(wn + n log n), meeting the information-theoretic lower bound. We describe a variant of Mergesort that has query complexity O(wnlogn), matching the upper bound shown by Faigle and Turan [13], and total complexity O(w^2 n log n). The exact total complexity of sorting remains unresolved. We also give upper and lower bounds for several related problems, including finding the minimal elements in a poset, which we show has query and total complexity Theta(wn), and its generalization, k-selection.}, }

EndNote citation:

%0 Thesis %A Riesenfeld, Samantha J. %T Optimization and Reconstruction over Graphs %I EECS Department, University of California, Berkeley %D 2008 %8 January 14 %@ UCB/EECS-2008-6 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-6.html %F Riesenfeld:EECS-2008-6