We explore some natural optimization and reconstruction problems that can be modeled with finite graphs. First, we consider the NP-hard problem of constructing a minimum spanning tree (MST) T for a graph G such that the maximum degree of T is minimized over all MSTs of G. More than 15 years ago, Goemans conjectured the existence of a polynomial-time approximation algorithm achieving an additive error of 1 (in degree) for this problem. The first such algorithm was given this year by Lau and Singh. We give a summary of the progress on this problem and present the first constant-factor approximation algorithm, which borrows its framework from the push-relabel max-flow algorithm by Goldberg. Several natural generalizations of this problem are also of interest, including the minimum bounded-degree spanning tree problem. For this problem, we present the first polynomial-time true approximation algorithm and a quasi-polynomial-time approximation algorithm inspired by Edmonds' use of augmenting paths in his weighted matching algorithm. This part of the talk is based on joint work with Kamalika Chaudhuri, Satish Rao, and Kunal Talwar.

In the second part of the talk, we consider the problem of reconstructing a directed graph, given access to an oracle that answers queries about the reachability relation on the vertices. We show that this problem reduces with little overhead to the task of sorting a partially ordered set (poset), i.e. of completely determining the partial order on a set of elements, given an oracle for the relation and an upper bound on the maximum number of incomparable elements. Faigle and Turan gave upper bounds on the query complexity of sorting a poset. We present the first algorithm of optimal query complexity as well as an efficient algorithm that matches the query complexity of the algorithms given by Faigle and Turan. Several related problems are also considered. This part of the talk is based on joint work with Costis Daskalakis, Richard M. Karp, Elchanan Mossel, and Elad Verbin.

Time permitting, we may also discuss results on a combinatorial reconstruction problem from the domain of computational biology.