Takazawa, Kenjiro
Finding a Maximum 2Matching Excluding Prescribed Cycles in Bipartite Graphs
Abstract
We introduce a new framework of restricted 2matchings close to Hamilton cycles. For an undirected graph (V,E) and a family U of vertex subsets, a 2matching F is called Ufeasible if, for each setU in U, F contains at most setU1 edges in the subgraph induced by U. Our framework includes C_{<=k}free 2matchings, i.e., 2matchings without cycles of at most k edges, and 2factors covering prescribed edge cuts, both of which are intensively studied as relaxations of Hamilton cycles. The problem of finding a maximum Ufeasible 2matching is NPhard. We prove that the problem is tractable when the graph is bipartite and each setU in U induces a Hamiltonlaceable graph. This case generalizes the C_{<=4}free 2matching problem in bipartite graphs. We establish a minmax theorem, a combinatorial polynomialtime algorithm, and decomposition theorems by extending the theory of C_{<=4}free 2matchings. Our result provides the first polynomially solvable case for the maximum C_{<=k}free 2matching 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 2matching problem in O(n^2 m) time, where n and m are the numbers of vertices and edges, respectively.
BibTeX  Entry
@InProceedings{takazawa:LIPIcs:2016:6495,
author = {Kenjiro Takazawa},
title = {{Finding a Maximum 2Matching Excluding Prescribed Cycles in Bipartite Graphs}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {87:187:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6495},
URN = {urn:nbn:de:0030drops64950},
doi = {10.4230/LIPIcs.MFCS.2016.87},
annote = {Keywords: optimization algorithms, matching theory, traveling salesman problem, restricted 2matchings, Hamiltonlaceable graphs}
}
2016
Keywords: 

optimization algorithms, matching theory, traveling salesman problem, restricted 2matchings, Hamiltonlaceable graphs 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

2016 