Minmax relations for graphs

点击翻译按钮获取中文摘要

Minmax relations for graphsAbstractA graph is a mathematical model for various networks, includingcommunication networks, transportation networks, and social networks. Manyimportant network parameters, like the capability, flexibility, andreliability, are often very difficult to compute. The goal of this projectis to identify graphs for which some of these parameters are efficientlycomputable. To accomplish this, the PI proposes to study the structure ofoptimal solutions. These structural results are fundamentally importantand they will have numerous applications on computing many related graphparameters.To be precise, the PI proposes to study the following three fundamentalproblems 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 resemblethe perfect graph problem in many ways: they all involve beautiful minmaxrelations, they all have polyhedral and algorithmic implications, and theyall generalize many known results.