A strongly polynomial-time algorithm for weighted general factors with three feasible degrees
General factors are a generalization of matchings. Given a graph G with a set π(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 degF (v) ∈ π(v) for every v of G. When all degree constraints are s...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss-Dagstuhl - Leibniz Zentrum für Informatik
2023
|
| Summary: | General factors are a generalization of matchings. Given a graph G with a set π(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 degF (v) ∈ π(v) for every v of G. When all degree constraints
are symmetric ∆-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. Strongly
polynomial-time algorithms are only known for weighted general factor problems that are reducible
to the weighted matching problem by gadget constructions.
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. |
|---|