Forbidden configurations, structural descriptions, and algorithm design

Abstract

The thesis consists of two parts. The combinatorial optimization problems considered in both two parts can be formulated in the form of the {\em packing and covering problems}. A {\em clutter} $\mathcal{B}$ is family of subsets of a finite ground set $V(\mathcal{B})$ such that any member of $\mathcal{B}$ is not included in another. Let $w$ be a nonnegative integral function on $V(\mathcal{B})$. A {\em covering} of $\mathcal{B}$ is a subset $Z$ of $V(\mathcal{B})$ such that the intersection of $Z$ and each member of $\mathcal{B}$ is nonempty. The {\em covering problem} seeks the covering $Z$ with minimum capacity $w(Z)$. A {\em packing} of $\mathcal{B}$ is a nonnegative integral function $y$ on the members of $\mathcal{B}$ such that $\sum_{e\in B\in \mathcal{B}}y(B)\leq w(e)$ for each element $e\in V(\mathcal{B})$. The {\em packing problem} is to find the packing of $\mathcal{B}$ with the value $\sum_{B\in\mathcal{B}}y(B)$ maximized. A clutter is said to have the {\em Max-Flow Min-Cut property} (or simply, {\em MFMC property}), if the maximum value of packings equals to the minimum capacity of coverings.

In the first part, we consider the {\em integral biflow maximization problem}. Let $G$ be a graph with four distinct vertices $s_1,t_1,s_2,t_2$ and nonnegative integral edge capacities $w$. A {\em biflow} (or a {\em 2-commodity flow}) in $G$ is a packing of the clutter $\mathcal{P}$ of all $s_1$-$t_1$ and $s_2$-$t_2$ paths in $G$. The integral biflow maximization problem is exactly the packing problem in $\mathcal{P}$. The graphs for which the clutter $\mathcal{P}$ has the MFMC property can be characterized by forbidden configuration due to Seymour's characterization of all binary clutters with the MFMC property. We call such graphs as {\em Seymour graphs}. In this thesis, we characterize Seymour graphs by structural description and design a combinatorial polynomial-time algorithm for finding the maximum integral biflows in Seymour graphs.

In the second part, we focus on the packing and covering problems on the clutter $\mathcal{C}$ of all cycles in a {\em tournament} with nonnegative integral arc capacities, where a {\em tournament} is a digraph in which there is exactly one arc between each pair of vertices. Chen et al. characterized the tournaments for which the clutter $\mathcal{C}$ has the MFMC property, and hence showed the polynomial-time solvability of these two problems on such tournaments based on the ellipsoid method for linear programming. In view of the limited efficiency of the ellipsoid method in practical, we design a totally combinatorial polynomial-time algorithm for packing and covering cycles in such tournament, which relies heavily on a global structure description in a recent work by Chen et al.