Finding a Maximum Restricted \({t}\)-Matching via Boolean Edge-CSP
- 29 May 2026
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (2) , 816-835
Abstract
The problem of finding a maximum 2-matching without short cycles has received significant attention due to its relevance to the Hamiltonian cycle problem. This problem is generalized to finding a maximum [Formula: see text]-matching which excludes specified complete [Formula: see text]-partite subgraphs, where [Formula: see text] is a fixed positive integer. The polynomial solvability of this generalized problem remains an open question. In this paper, we present polynomial-time algorithms for the following two cases of this problem: in the first case the forbidden complete [Formula: see text]-partite subgraphs are edge-disjoint, and in the second case the maximum degree of the input graph is at most [Formula: see text]. Our result for the first case extends the previous work of Nam (1994), showing the polynomial solvability of the problem of finding a maximum 2-matching without cycles of length four, where the cycles of length four are vertex-disjoint. The second result expands upon the works of Bérczi and Végh (2010) and Kobayashi and Yin (2012), which focused on graphs with maximum degree at most [Formula: see text]. Our algorithms are obtained from exploiting the discrete structure of restricted [Formula: see text]-matchings and employing an algorithm for the Boolean edge-CSP.Keywords
All Related Versions
Funding Information
- Japan Society for the Promotion of Science (JP24K02901)
- Japan Society for the Promotion of Science (JP22K17854)
- Japan Society for the Promotion of Science (JP24K21315)
- Japan Society for the Promotion of Science (JP20K11692)
- Japan Society for the Promotion of Science (JP22H05001)
- Japan Society for the Promotion of Science (JP20K11699)
This publication has 43 references indexed in Scilit:
- Finding triangle‐free 2‐factors in general graphsJournal of Graph Theory, 2024
- Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden TrianglesMathematical Programming, 2021
- Optimal General Matchings2018
- Improved Algorithms for Even Factors and Square-Free Simple b-MatchingsAlgorithmica, 2012
- Polyhedron of triangle-free simple 2-matchings in subcubic graphsMathematical Programming, 2012
- Restricted b-Matchings in Degree-Bounded Graphs2010
- Combinatorial algorithms for matchings, even factors and square-free 2-factorsMathematical Programming, 2006
- The Membership Problem in Jump SystemsJournal of Combinatorial Theory, Series B, 1997
- General Antifactors of GraphsJournal of Combinatorial Theory, Series B, 1993
- Antifactors of graphsPeriodica Mathematica Hungarica, 1973