In this paper, we characterize in several manners the class of contraction perfect graphs which are the perfect graphs that remain perfect after the contraction of any edge set. We define the utter graph u ( G ) which is the graph whose stable sets are in bijection with the co-2-plexes of G , and prove that u ( G ) is perfect if and only if G is contraction perfect. Moreover, we exhibit the strong link between co-2-plexes and induced matchings and discuss its consequences according to known results on these problems. This yields several classes of graphs for which the maximum weighted co-2-plex is solvable in polynomial time. Finally, we show how our results extend to a new class of graphs for which finding a maximum weighted induced matching can be done in polynomial time.

In this paper, we propose two exact algorithms based on the computation of the Dijkstra tree to solve the multiple pairs shortest path problem. Traditionally, to solve this kind of problems, algorithms are based on distance matrices. For sparse graphs, the computation of these matrices is too costly. The two approaches that we propose allow tackling this issue by computing a small number of Dijkstra trees. We test our algorithms on telecommunication network instances and random instances, and we discuss the dependence of the obtained results on the structure of sources and destinations of commodities. We also propose an extension of the Bi-Dijkstra algorithm to consider several destinations together.

We introduce the reverse Chvátal--Gomory rank $r^*(P)$ of an integral polyhedron $P$, defined as the supremum of the Chvátal--Gomory ranks of all rational polyhedra whose integer hull is $P$. A well-known example in dimension two shows that there exist integral polytopes $P$ with $r^*(P)=+\infty$. We provide a geometric characterization of polyhedra with this property in every dimension, and investigate upper bounds on $r^*(P)$ when this value is finite.

Given a symmetric crossing supermodular set function p on V and a partition of V, we solve the problem of finding a graph with ground set V having edges only between the classes of such that for every subset X of V the cut of the graph defined by X contains at least p(X) edges. The objective is to minimize the number of edges of the graph. This problem is a common generalization of the global edge-connectivity augmentation of a graph with partition constraints, which was solved by Bang-Jensen, Gabow, Jordán and Szigeti [1] and the problem of covering a symmetric crossing supermodular set function solved by Benczúr and Frank [3]. Our problem can be considered as an abstract form of the problem of global edge-connectivity augmentation of a hypergraph by a multipartite graph, which was earlier solved by the authors [5].