This award targets counting and sampling variants of a number of cut and path problems in several restricted graph classes including planar graphs, the 8-connected 2D grid, and the 3D grid. These graph classes are primarily motivated by applications in computer vision where several recent results renewed interest in the minimization variants of these problems. The importance of the corresponding counting and sampling variants stems from, among others, automated learning of the parameters of the underlying probabilistic models such as the Markov Random Field.
The proposed research builds on the PI's recent works on counting and sampling minimum (s,t)-cuts and minimum single-source-multi-sink cuts with connectivity priors, both in planar graphs. These problems are used in image segmentation applications and form an initial step towards the ultimate goal of computing the partition function for weighted cuts, i.e., the summation of the cut weights across all (s,t)-cuts; this quantity is essential for model parameter learning via the maximum likelihood principle. The PI will study a variety of cut and path problems that generalize the initial results from different perspectives. These include studying other connectivity priors, moving beyond planarity, and beyond minimum cuts and shortest paths.
The research will actively involve undergraduate and master students. Related educational materials are projected to annually impact over 600 students, about 10 of them from the National Technical Institute for the Deaf. In addition to standard dissemination venues like conferences and journals, the PI will also present the results at the annual Imagine RIT festival. This community outreach festival attracted about 35,000 visitors in 2012, many of them middle and high school students.
