Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
复制标题
DOI：
10.1016/j.disopt.2017.05.003
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Kenjiro Takazawa
中科院分区：
文献类型：
--
作者：
Kenjiro Takazawa
我们引入了一个新的框架，限制2-匹配接近汉密尔顿圈。对于一个无向图（V，E）和一个顶点子集族U，一个2-匹配F称为U-可行的，如果|F [U]| ≤| U|-1对于每个U∈ U，其中F [U]是由U诱导的F中的边的集合。如果F是2-因子，则这个性质使得F满足U∈ U的子环消去约束。我们的框架可以描述C≤ k-free 2-匹配，即不含至多k条边的圈的2-匹配和覆盖指定边割的2-因子，这两种匹配都是作为汉密尔顿圈的松弛而被深入研究的.虽然寻找最大U-可行2-匹配的问题是NP-困难的，我们证明了当图是二分的，每个U∈ U诱导一个Hamilton-laceable图时，这个问题是易处理的。这种情况推广了二部图中的C≤ 4-free 2-匹配问题。通过推广C≤ 4-free 2-匹配的理论，建立了极小极大定理、组合多项式时间算法和分解定理。我们的结果提供了第一个多项式可解的情况下，最大的C≤ k-免费的2-匹配问题，k≥ 5。例如，在二部图中，每个长度为6的圈至少有两个弦，我们的算法在O（n2 m）时间内解决了最大C≤ 6-free 2-匹配问题，其中n和m分别是顶点和边的数目.
We introduce a new framework for 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| F [U]|≤| U|− 1 for each U∈ U, where F [U] is the set of edges in F induced by U. If F is a 2-factor, this property makes F satisfy the subtour elimination constraint for U∈ U. Our framework can describe C≤ k-free 2-matchings, ie, 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. While 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 U∈ 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.