A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914805327069184 |
|---|---|
| author | Shao, Shuai Živný, Stanislav |
| author_facet | Shao, Shuai Živný, Stanislav |
| contents | 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 $\text{deg}_F(x) \in π(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. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_11761 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees Shao, Shuai Živný, Stanislav Discrete Mathematics Computational Complexity Data Structures and Algorithms 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 $\text{deg}_F(x) \in π(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. 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. |
| title | A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2301.11761 |