Linear-Time Algorithms for Maximum-Weight Induced Matchings and Minimum Chain Covers in Convex Bipartite Graphs
Boris Klemz, Günter Rote
Abstract
Abstract A bipartite graph $$G=(U,V,E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>U</mml:mi> <mml:mo>,</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is convex if the vertices in V can be linearly ordered such that for each vertex $$u\in U$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>U</mml:mi> </mml:mrow> </mml:math> , the neighbors of u are consecutive in the ordering of V . An induced matching H of G is a matching for which no edge of E connects endpoints of two different edges of H . We show that in a convex bipartite graph with n vertices and m weighted edges, an induced matching of maximum total weight can be computed in $$O(n+m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time. An unweighted convex bipartite graph has a representation of size O ( n ) that records for each vertex $$u\in U$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>U</mml:mi> </mml:mrow> </mml:math> the first and last neighbor in the ordering of V . Given such a compact representation , we compute an induced matching of maximum cardinality in O ( n ) time. In convex bipartite graphs, maximum-cardinality induced matchings are dual to minimum chain covers . A chain cover is a covering of the edge set by chain subgraphs , that is, subgraphs that do not contain induced matchings of more than one edge. Given a compact representation, we compute a representation of a minimum chain cover in O ( n ) time. If no compact representation is given, the cover can be computed in $$O(n+m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time. All of our algorithms achieve optimal linear running time for the respective problem and model, and they improve and generalize the previous results in several ways: The best algorithms for the unweighted problem versions had a running time of $$O(n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> (Brandstädt et al. in Theor. Comput. Sci. 381(1–3):260–265, 2007. 10.1016/j.tcs.2007.04.006 ). The weighted case has not been considered before.