Maximum Number of Requests on a Path With a Given Grooming Factor

Abstract

We give an optimal solution to the Maximum All Request Path Grooming (MARPG) problem motivated by a traffic grooming application and by its interest in computing lower bounds on the cutwidth of a graph. We are given a directed path on vertices and a positive integer capacity (grooming factor). The MARPG problem consists of determining a maximum‐cardinality set of pairwise‐different simple sub‐dipaths (requests) subject to the constraint that each arc is contained in at most of these dipaths. This problem can be solved in polynomial time using a reduction to a minimum cost flow problem in a directed graph. In this paper, we fully characterize the set of requests of an optimal solution to the MARPG problem and show how to compute in constant time its cardinality . Furthermore, we fix an unfortunate error in the formula of that appears in the preliminary conference version of this paper. We first show that the solution obtained by greedily taking the requests of the smallest size (length) is not always optimal, disproving a claim from previous work. We then characterize optimal solutions and show that they are obtained by a different greedy algorithm based on a weight order. We characterize the so‐called “anomalies” which roughly correspond to the set of requests belonging to an optimal solution but not to the smallest‐size greedy algorithm. Then, we establish a formula returning in constant time the value of the number of anomalies and therefore the exact cardinality of of an optimal solution to the MARPG problem. Finally, we establish upper bounds on the number of anomalies, in particular, the general one that the number of anomalies is at most . These bounds have been used to get new lower bounds on the cutwidth of a graph.