Optimal general factor problem and jump system intersection

DOI10.1007/978-3-031-32726-1_21MaRDI QIDQ6086009zbMATH OpenOpenAlexFDO

Authors Yusuke Kobayashi

Publication date 9 November 2023

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.00779

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Abstract: In the optimal general factor problem, given a graph $G=(V,E)$ and a set $B(v)subseteqmathbbZ$ of integers for each $vinV$, we seek for an edge subset $F$ of maximum cardinality subject to $d_F(v)inB(v)$ for $vinV$, where $d_F(v)$ denotes the number of edges in $F$ incident to $v$. A recent crucial work by Dudycz and Paluch shows that this problem can be solved in polynomial time if each $B(v)$ has no gap of length more than one. While their algorithm is very simple, its correctness proof is quite complicated. In this paper, we formulate the optimal general factor problem as the jump system intersection, and reveal when the algorithm by Dudycz and Paluch can be applied to this abstract form of the problem. By using this abstraction, we give another correctness proof of the algorithm, which is simpler than the original one. We also extend our result to the valuated case.

Recommendations

• Even factors, jump systems, and discrete convexity
• Optimal general matchings
• The membership problem in jump systems
• General factors of graphs
• Matching, matroids, and extensions

Cites work

• \(\Delta\)-matroid and jump system
• Antifactors of graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of Matroid Property Algorithms
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Discrete Convex Analysis
• General antifactors of graphs
• General factors of graphs
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• Integer Programming and Combinatorial Optimization
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• Matching theory
• Matroid matching and some applications
• Matroid Parity and Jump Systems: A Solution to a Conjecture of Recski
• Operations on M‐Convex Functions on Jump Systems
• Optimal general matchings
• Packing subgraphs in a graph
• Paths, Trees, and Flowers
• Submodular functions and optimization.
• Terminal backup, 3D matching, and covering cubic graphs
• The factorization of graphs. II
• The membership problem in jump systems
• Time bounds of basic steepest descent algorithms for \(M\)-convex function minimization and related problems

Cited in

(5)

• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• A strongly polynomial-time algorithm for weighted general factors with three feasible degrees
• Optimal general factor problem and jump system intersection
• Faster algorithms on linear delta-matroids
• Parameterized algorithms for matching integer programs with additional rows and columns

This page was built for publication: Optimal general factor problem and jump system intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086009)