Computer Science and Engineering

Theory Seminar

The Complexity of Finding S-factors in Regular Graphs

Sanjana Kolisetty and Linh LeUniversity of Michigan
3725 Beyster BuildingMap

A graph G has an S-factor, if there exists a spanning subgraph F of G such that for all v \in V: deg_F(v) \in S. The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this talk we will discuss the computational complexity of finding S-factors in regular graphs. Our techniques combine some classical as well as recent tools from graph theory.

Based on joint work with Ilya Volkovich and Mihalis Yannakakis.