Optimization and reconstruction over graphs
Richard M. Karp, Samantha J. Riesenfeld · 2007
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 (MBDST) 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 polynomial-time 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+ Olognloglog 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 2n log n). The exact total complexity of sorting remains unresolved. We also give upper and lower bounds for several related problems, including biding the minimal elements in a poset, which we show has query and total complexity Θ(wn), and its generalization, k-selection.