# 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://www.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.

**Advisor:** 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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-6.html %F Riesenfeld:EECS-2008-6