We first consider perhaps the most elementary of such a problem, sampling a connected subgraph. We find unless NP = RP there is no FPAS to sample a connected subgraph of a fixed size k. Examining a variant where a subgraph of size k is sampled with probability proportional to λk, we find it easy to sample for λ < λd and hard for λd < λ < 1 (where λd is a constant based upon the maximum degree of the graph). Moreover, we show local Markov chains sampling either of these models do not rapidly mix on a family of trees, making it unlikely such Markov chain are useful for sampling these objects.
We then consider precedence constrained scheduling, where we have a set of tasks, some of which need to be concluded before others can start, and schedule assigning how many tasks can be executed in parallel at a given time. We expand upon the known results for the decision variant (finding an order preserving mapping from G to H), showing if H is a general graph it is hard to decide, if G is a tree and H is a complete layered graph it is also hard to decide, and if G is a collection of path graphs and H is a complete layered graph it is easy to decide. We then move on to consider sampling an order preserving mapping from G to H, giving a FPAS when G is a collection of path graphs and H is a complete layered graph. Finally, we give a dynamic programming algorithm for exactly counting the number of order preserving mappings from G to H when G is a collection of path graphs and H is a complete layered graph of bounded width.
Lastly, we examine the problem of fairly partitioning a space. We first examine doing so in a geometric space with Voronoi partitions, proving a Voronoi partition exists in any convex space. We then consider a graphical model, where we find a spanning tree of a graph and then remove an edge so that the resulting components are as balanced in size as possible. We prove if G is a complete graph then we sample a tree that gives a close to equitable split with high probability, and give experimental data supporting the conjectures that the same holds for G being a n x n grid or sampled from the Gn,p model.
Advisor: Prof. Daniel Stefankovic (Computer Science) Committee: Prof. Lane Hemaspaandra (Computer Science), Prof. Muthu Venkitasubramaniam (Computer Science, Georgetown University), and Prof. Arjun Krishnan (Mathematics) Chair: Prof. Sevak Mkrtchyan (Mathematics)