2026-08-20T01:47:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21146 2024-09-23T09:13:18Z ddc:004 open_access

Finding a Maximum Restricted t-Matching via Boolean Edge-CSP Iwamasa, Yuni Kobayashi, Yusuke Takazawa, Kenjiro Polynomial algorithm C_k-free 2-matching Jump system Boolean edge-CSP The problem of finding a maximum 2-matching without short cycles has received significant attention due to its relevance to the Hamilton cycle problem. This problem is generalized to finding a maximum t-matching which excludes specified complete t-partite subgraphs, where t 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 t-partite subgraphs are edge-disjoint; and in the second case the maximum degree of the input graph is at most 2t-1. 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 t+1. Our algorithms are obtained from exploiting the discrete structure of restricted t-matchings and employing an algorithm for the Boolean edge-CSP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuni Iwamasa and Yusuke Kobayashi and Kenjiro Takazawa 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.75 urn:nbn:de:0030-drops-211463 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.75 eng https://creativecommons.org/licenses/by/4.0/legalcode