The Complexity of Finding S-factors in Regular Graphs

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.