License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.87
URN: urn:nbn:de:0030-drops-64950
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6495/
Go to the corresponding LIPIcs Volume Portal

Takazawa, Kenjiro

Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs

pdf-format:
LIPIcs-MFCS-2016-87.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{takazawa:LIPIcs:2016:6495,
  author =	{Kenjiro Takazawa},
  title =	{{Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{87:1--87:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6495},
  URN =		{urn:nbn:de:0030-drops-64950},
  doi =		{10.4230/LIPIcs.MFCS.2016.87},
  annote =	{Keywords: optimization algorithms,  matching theory,  traveling salesman problem,  restricted 2-matchings,  Hamilton-laceable graphs}
}

Keywords: optimization algorithms, matching theory, traveling salesman problem, restricted 2-matchings, Hamilton-laceable graphs
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI