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 for the max-flow problem. It improves Fischer's local-search algorithm. Via an analysis by Konemann and Ravi, 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(wn log n), matching the upper bound shown by Faigle and Turan, 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.