2026-07-23T01:03:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6495 2024-03-06T10:38:26Z ddc:004 open_access

Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs Takazawa, Kenjiro optimization algorithms matching theory traveling salesman problem restricted 2-matchings Hamilton-laceable graphs We introduce a new framework of restricted 2-matchings close to Hamilton cycles. For an undirected graph (V,E) and a family U of vertex subsets, a 2-matching F is called U-feasible if, for each setU in U, F contains at most |setU|-1 edges in the subgraph induced by U. Our framework includes C_{<=k}-free 2-matchings, i.e., 2-matchings without cycles of at most k edges, and 2-factors covering prescribed edge cuts, both of which are intensively studied as relaxations of Hamilton cycles. The problem of finding a maximum U-feasible 2-matching is NP-hard. We prove that the problem is tractable when the graph is bipartite and each setU in U induces a Hamilton-laceable graph. This case generalizes the C_{<=4}-free 2-matching problem in bipartite graphs. We establish a min-max theorem, a combinatorial polynomial-time algorithm, and decomposition theorems by extending the theory of C_{<=4}-free 2-matchings. Our result provides the first polynomially solvable case for the maximum C_{<=k}-free 2-matching problem for k >= 5. For instance, in bipartite graphs in which every cycle of length six has at least two chords, our algorithm solves the maximum C_{<=6}-free 2-matching problem in O(n^2 m) time, where n and m are the numbers of vertices and edges, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kenjiro Takazawa 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.87 urn:nbn:de:0030-drops-64950 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.87 eng https://creativecommons.org/licenses/by/3.0/legalcode