Advancement: Spectral methods for graph minor problems

Speaker Name: 
Andrew Stolman
Speaker Title: 
PhD Student (Advisor: Seshadhri Comandur)
Speaker Organization: 
Computer Science
Start Time: 
Thursday, March 14, 2019 - 9:30am
End Time: 
Thursday, March 14, 2019 - 11:30am
Location: 
Engineering 2, Room 215
Organizer: 
Seshadhri Comandur

Abstract:  A wide range of algorithmic problems, such as deciding the existence of small vertex separators and deciding embeddability questions, are answerable through the detection of forbidden graph minors. A graph, $G$, is said to contain a graph, $H$, as a minor if there is a subgraph of $G$ which can be contracted along edges to produce a graph isomorphic to $H$. Many classes of graphs are characterized by minors which do not appear in any graph in the class - the so-called forbidden minors. Thus far, algorithms for forbidden minor problems have largely relied on tools from geometry and combinatorics. In this proposal, we put forth a new paradigm. There is a deep connection between the behavior of random walks on graphs and the existence of forbidden minors. Leveraging this insight, we are able to make progress on decade-long open problems. This proposal contains two papers which answer two such open problems, as well as a plan to apply this a! pproach to other graph minor problems.