DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.75

Finding a Maximum Restricted t-Matching via Boolean Edge-CSP

Authors: Yuni Iwamasa, Yusuke Kobayashi, and Kenjiro Takazawa

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

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.

Cite as

Yuni Iwamasa, Yusuke Kobayashi, and Kenjiro Takazawa. Finding a Maximum Restricted t-Matching via Boolean Edge-CSP. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{iwamasa_et_al:LIPIcs.ESA.2024.75,
  author =	{Iwamasa, Yuni and Kobayashi, Yusuke and Takazawa, Kenjiro},
  title =	{{Finding a Maximum Restricted t-Matching via Boolean Edge-CSP}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{75:1--75:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.75},
  URN =		{urn:nbn:de:0030-drops-211463},
  doi =		{10.4230/LIPIcs.ESA.2024.75},
  annote =	{Keywords: Polynomial algorithm, C\underlinek-free 2-matching, Jump system, Boolean edge-CSP}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2018.12

The b-Branching Problem in Digraphs

Authors: Naonori Kakimura, Naoyuki Kamiyama, and Kenjiro Takazawa

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

In this paper, we introduce the concept of b-branchings in digraphs, which is a generalization of branchings serving as a counterpart of b-matchings. Here b is a positive integer vector on the vertex set of a digraph, and a b-branching is defined as a common independent set of two matroids defined by b: an arc set is a b-branching if it has at most b(v) arcs sharing the terminal vertex v, and it is an independent set of a certain sparsity matroid defined by b. We demonstrate that b-branchings yield an appropriate generalization of branchings by extending several classical results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b-branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b-branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b-branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v.

Cite as

Naonori Kakimura, Naoyuki Kamiyama, and Kenjiro Takazawa. The b-Branching Problem in Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kakimura_et_al:LIPIcs.MFCS.2018.12,
  author =	{Kakimura, Naonori and Kamiyama, Naoyuki and Takazawa, Kenjiro},
  title =	{{The b-Branching Problem in Digraphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.12},
  URN =		{urn:nbn:de:0030-drops-95948},
  doi =		{10.4230/LIPIcs.MFCS.2018.12},
  annote =	{Keywords: Greedy Algorithm, Packing, Matroid Intersection, Sparsity Matroid, Arborescence}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2016.87

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

Authors: Kenjiro Takazawa

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

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.

Cite as

Kenjiro Takazawa. Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{takazawa:LIPIcs.MFCS.2016.87,
  author =	{Takazawa, Kenjiro},
  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 =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.87},
  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}
}

3 Search Results for "Takazawa, Kenjiro"

Finding a Maximum Restricted t-Matching via Boolean Edge-CSP

Abstract

Cite as

The b-Branching Problem in Digraphs

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message