Minmax relations for graphs

Louisiana State University, Baton Rouge LA

Investigators

Abstract

Minmax relations for graphs Abstract A graph is a mathematical model for various networks, including communication networks, transportation networks, and social networks. Many important network parameters, like the capability, flexibility, and reliability, are often very difficult to compute. The goal of this project is to identify graphs for which some of these parameters are efficiently computable. To accomplish this, the PI proposes to study the structure of optimal solutions. These structural results are fundamentally important and they will have numerous applications on computing many related graph parameters. To be precise, the PI proposes to study the following three fundamental problems in combinatorial optimization: 1. To characterize graphs for which the clutter of (edge-sets of) odd st-paths is ideal/Mengerian. This problem generalizes the ordinary matching problem as well as the ordinary edge-disjoint paths problem. 2. To characterize graphs for which the clutter of (vertex-set of) odd circuits is ideal/Mengerian. This is a problem very closely related to the t-perfect graph problem, which arises naturally in the study of stable sets in graphs. One of the goals of this project is to discover the connections between these two problems. 3. To characterize perfectly 2-edge-connected graphs. This is a problem originated from the study of the Traveling Salesman Problem. One of its attractive properties is that being perfectly 2-edge-connected is preserved under the "dual" of the induced-minor relation, which is a graph containment relation preserved by many important graph properties. All the proposed problems are fundamental and attractive. They resemble the perfect graph problem in many ways: they all involve beautiful minmax relations, they all have polyhedral and algorithmic implications, and they all generalize many known results.