Min-max relations on two packing problems

Abstract

Min-max relations appear widely among various combinatorial optimization problems. Packing problems also have an essential position among all topics of graph theory. This thesis aims at investigating two different kinds of packing problems which reflect the min-max relation under certain circumstances. The fractional edge cover packing problem comes from the integer edge cover packing problem which is originally a dual problem of the edge coloring problem. The seagulls packing problem is the simplest of all $F$-packing problems excluding maximum matching problem.

Our first main result is that the fractional edge cover packing problems can be handled in strong polynomial time for any loopless multigraph with three or more vertices. Also the maximum number of edge covers in a fractional packing will not exceed $m+3n-1$ while $n$ and $m$ are the size of vertices and edges of the given graph. The total weight of a maximum fractional edge cover packing is the fractional cover index $\xi^*(G)=\min \{\delta(G), \Phi(G)\}$, where $\delta(G)$ is the minimum degree of $G$ and $\Phi(G)=\min \{\frac{2|E^{+}(U)|}{|U|+1}: U\subseteq V, |U| \ge 3 \ {\rm and \ odd}\}$ ($E^{+}(U)$ is the set of edges in $G$ with at least one end in $U$). We give a detailed algorithm for finding such a packing and estimate the complexity of it.

Our second result shows that the maximum packing number of seagulls equals to the minimum covering number of seagulls for any weight function defined on vertices in certain graphs without specific forbidden structures. A similar result for edge weighted seagulls packing also holds with respect to a different set of forbidden structures. We further extend the previous two results and find out two more classes of graphs whose all subgraphs enjoy the same min-max properties as the original graphs have (one class for vertex weighted graphs and another for edge weighted graphs). Detailed forbidden structures of all these classes of graphs together with their proofs are given in the main body of this thesis.