Recovery of disrupted airline operations using k-Maximum Matching in graphs.

By Berge's theorem, finding a maximum matching in a graph relies on the use of augmenting paths . When no further constraint is added, Edmonds' algorithm allows to compute a maximum matching in polynomial time by sequentially augmenting such paths. Motivated by applications in the scheduling of airline operations, we consider a similar problem where only paths of bounded length can be augmented. Precisely, let k ≥ 1 be an odd integer, and M a matching of a graph G . What is the maximum size of a matching that can be obtained from M by using only augmenting paths of length at most k ? We first prove that this problem can be solved in polynomial time for k ≤ 3 in any graph and that it is NP-complete for any fixed k ≥ 5 in the class of planar bipartite graphs of degree at most 3 and arbitrarily large girth. We then prove that this problem is in P, for any k , in several subclasses of trees such as caterpillars or trees with all vertices of degree at least 3 “far appart”. Moreover, this problem can be solved in time O ( n ) in the class of n -node trees when k and the maximum degree are fixed parameters. Finally, we consider a more constrained problem where only paths of length exactly k can be augmented. We prove that this latter problem becomes NP-complete for any fixed k ≥ 3 and in trees when k is part of the input. [ABSTRACT FROM AUTHOR]