2026-07-28T08:11:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11583 2024-03-06T10:48:22Z ddc:004 open_access

The Complexity of Finding S-Factors in Regular Graphs Kolisetty, Sanjana Le, Linh Volkovich, Ilya Yannakakis, Mihalis constraint satisfaction problem Dichotomy theorem Graph Factors 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sanjana Kolisetty and Linh Le and Ilya Volkovich and Mihalis Yannakakis 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.21 urn:nbn:de:0030-drops-115834 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.21 eng https://creativecommons.org/licenses/by/3.0/legalcode