Finding a Maximum Restricted \({t}\)-Matching via Boolean Edge-CSP
SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 816-835
DOI: 10.1137/24m1713727 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 29.05.2026. Verfasst von Yuni Iwamasa und 2 weiteren Autor:innen. Die Arbeit nennt 56 Literaturangaben. Gefördert von: Japan Society for the Promotion of Science.
Abstract (Originalsprache)
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.
Förderung
- Japan Society for the Promotion of Science
Zitieren
APA
Iwamasa, Y., Kobayashi, Y., & Takazawa, K. (2026). Finding a Maximum Restricted \({t}\)-Matching via Boolean Edge-CSP. SIAM Journal on Discrete Mathematics, 40(2), 816-835. https://doi.org/10.1137/24m1713727
Vancouver
Iwamasa Y, Kobayashi Y, Takazawa K. Finding a Maximum Restricted \({t}\)-Matching via Boolean Edge-CSP. SIAM Journal on Discrete Mathematics. 2026;40(2):816-835. doi:10.1137/24m1713727
BibTeX
@article{Iwamasa2026,
author = {Iwamasa, Yuni and Kobayashi, Yusuke and Takazawa, Kenjiro},
title = {Finding a Maximum Restricted \(t\)-Matching via Boolean Edge-CSP},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {2},
pages = {816--835},
doi = {10.1137/24m1713727}
}
EUVIMED