URCS Seminars & Talks

Tuesday, June 14, 2022

10:00 AM

WH2506; https://rochester.zoom.us/s/93330546240 (hybrid)

Ph.D. Thesis Defense

Andrew Read-McFarland

University of Rochester

Sampling and Decision Problems with Connectivity Constraints

In this work we focus on categorizing various problems on graphs with connectivity constraints, proving when it is easy or hard to solve (whether that be deciding, approximately sampling, or exactly counting). While we generally prefer to show a problem is easy (and give an algorithm to solve it), if a problem is hard it useful to know a polynomial time solution is unlikely to exist. Thus, we seek to find the hardness thresholds of graph theoretic problems with some form of connectivity constraints.

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)