Maximum Induced Matching: Recursive Computation and an Availability-Uniform Branch-Length Analysis

Abstract

Induced matchings are a fundamental graph-theoretic concept with applications in secure communication, network flow, and very-large-scale integration. An induced matching in a graph is a set of pairwise non-adjacent edges such that no edge of the graph joins the endpoints of two distinct edges in the set. A maximum induced matching is an induced matching of the largest possible cardinality. Since the maximum induced matching problem is NP-hard, identifying conditions under which exact recursive computation is efficient remains an important question. In this article, we analyze the time and space complexity of a deterministic recursive algorithm for computing a maximum induced matching. We analyze an idealized availability-uniform edge-elimination model for successive edge selections along a recursive branch. In this model, whenever r≥1 edges are available, the number of edges remaining available after the next selection is assumed to be uniformly distributed over {0,1,…,r−1}, with this transition law applying at every step. Under this additional modeling assumption, we establish that the expected branch length is at most 1+lnm, where m is the number of edges in the input graph. The expectation is taken with respect to the assumed transition process, not with respect to an input graph sampled from G(n,m). In particular, the availability-uniform assumption is not derived from the G(n,m) random-graph model, and the logarithmic expected branch-length result is not claimed as an average-case property of that input distribution. We also establish general worst-case time and space bounds for the deterministic algorithm.