TR19-040 Authors: Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

Publication: 12th March 2019 19:07

Downloads: 1361

Keywords:

A graph $G$ has an \emph{$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 paper we study the computational complexity of finding $S$-factors in regular graphs.

Our techniques combine some classical as well as recent tools from graph theory.