ECCC-Report TR19-040https://eccc.weizmann.ac.il/report/2019/040Comments and Revisions published for TR19-040en-usTue, 12 Mar 2019 19:07:28 +0200
Paper TR19-040
| The Complexity of Finding {$S$}-factors in Regular Graphs |
Sanjana Kolisetty,
Linh Le,
Ilya Volkovich,
Mihalis Yannakakis
https://eccc.weizmann.ac.il/report/2019/040A 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.Tue, 12 Mar 2019 19:07:28 +0200https://eccc.weizmann.ac.il/report/2019/040