Real-weighted general factors on subcubic graphs

• 成果类型: Article; Early Access
• 署名作者: Shao, Shuai; Zivny, Stanislav
• 署名单位: Chinese Academy of Sciences; University of Science & Technology of China, CAS; Hefei National Laboratory; University of Oxford
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02416-3
• 发表日期: 2026-09-14
• 关键词: Graph factor; Terminal backup problem; Matching-gadget; Strongly polynomial-time; Symmetric -matroid; algorithm; matchings

摘要

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) of feasible degrees (called a degree constraint), the general factor problem seeks a (spanning) subgraph F of G such that degF(v)is an element of pi(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.