Real-weighted general factors on subcubic graphs

Source abstract

Abstract General factors generalize the concept of graph matchings and have been extensively studied in combinatorial optimization. Given a graph G where each vertex v is assigned a set $$\pi (v)$$ π ( v ) of feasible degrees (called a degree constraint), the general factor problem seeks a (spanning) subgraph F of G such that $$\deg _F(v) \in \pi (v)$$ deg F ( v ) ∈ π ( v ) for all v of G . When all degree constraints are symmetric $$\Delta$$ Δ -matroids, the problem is solvable in polynomial-time. The weighted general factor problem further extends this by incorporating edge weights, and the goal is to find a general factor that maximizes the total weight in an edge-weighted graph. In this paper, we propose a strongly polynomial-time algorithm for the real-weighted general factor problem on subcubic graphs by establishing a refined structural result that ensures the optimality of weighted graph factors. As an application of our result, we obtain a strongly polynomial-time algorithm for the terminal backup problem, a variant of the Steiner tree problem. Furthermore, we provide a characterization theorem for matching-gadget realizable degree constraints.