Modulus of edge covers, fractional edge covers, and stars

Abstract

Modulus on graphs is a very flexible and useful tool for measuring the richness of families of objects defined on a graph. It has been shown that the modulus of special families of objects generalizes classical network theoretic quantities such as shortest path, max flow/min cut, and effective resistance. When the family of graph objects is finite, the modulus problem can be viewed as a convex optimization problem where each object in the family induces an inequality constraint. This implies that calculating the modulus of large families can be difficult due to the large number of constraints. One focus of this dissertation is to establish an efficient way of calculating the modulus of fractional edge covers, a very large family, using the modulus of stars, a much smaller family. In this dissertation, the main objects of interest are edge covers. An edge cover is a subset of edges with the property that each node of the graph sees at least one edge in the cover. The concept of edge covers can be relaxed by defining fractional edge covers, where edges are assigned weights and a node is said to be 'covered' if the weights at each node add to at least one. Direct calculations of both the edge cover modulus and fractional edge cover modulus can be expensive as these families tend to be exponentially large. Moreover, the modulus of these families are related; from the modulus of fractional edge covers we obtain upper and lower bounds for the modulus of edge covers. Through the theory of Fulkerson blocking duality, every family of objects has a corresponding dual family whose modulus is closely related to the modulus of the original family. One of the main results in this dissertation is that the dual family of fractional edge covers is the family of stars, which greatly reduces the number of constraints for the modulus problem. This result allows an approximation for the modulus of edge covers using the modulus of stars. This dissertation studies the relationships of these three families---edge covers, fractional edge covers, and stars---as well as the computational complexity involved in calculating the modulus of these families.