Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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