A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees

Abstract

General factors are a generalization of matchings. Given a graph $G$ with a set $\ddot{I}€(v)$ of feasible degrees, called a degree constraint, for each vertex $v$ of $G$, the general factor problem is to find a (spanning) subgraph $F$ of $G$ such that ${\text{deg}}_F(x)\in \ddot{I}€(v)$ for every $v$ of $G$. When all degree constraints are symmetric $\hat{I}”$-matroids, the problem is solvable in polynomial time. The weighted general factor problem is to find a general factor of the maximum total weight in an edge-weighted graph. In this paper, we present the first strongly polynomial-time algorithm for a type of weighted general factor problems with real-valued edge weights that is provably not reducible to the weighted matching problem by gadget constructions.

This is a full version of an ISAAC 2023 paper