EUVIMEDEUVIMED entdecken
Crossref

Finding a Maximum Restricted \({t}\)-Matching via Boolean Edge-CSP

Yuni Iwamasa, Yusuke Kobayashi, Kenjiro Takazawa

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →