Ph.D. Theses

The Asymmetric Orientation Control Matching Problem: Analysis and Algorithms

By Lily Briggs
Advisor: Mukkai Krishnamoorthy
March 26, 2015

This thesis explores a matching problem we call the Asymmetric by the study of structural controllability from a graph-theoretic perspective, and is also closely related to other useful graph problems, such as the Asymmetric Assignment problem and the Asymmetric Traveling Salesman problem. If we define a partial assignment as a node-disjoint cover of simple paths and cycles in a digraph, our problem is: given a symmetric, weighted digraph, find a maximum weight asymmetric partial assignment. In this thesis, we analyze the problem's complexity, present a few algorithmic approaches to solving it, and prove some bounds on solution values in trees.

We prove that AOCM is NP-complete, and further, that it is APX-hard. We show that the uniform-weight case, however, is reducible to finding simple 2-matchings in undirected graphs, and is thus polynomially solvable.

Next, we show work on a linear programming algorithm using cutting planes, in which we prove several useful theorems for shrinking and reducing the search space for violated cutting planes of two different types.

We also analyze four heuristic algorithms, and show that one of them, with a worst case running time of O(m) (where m is the number of edges) finds above 96% of the optimal value in all of our test cases with uniform weights; however, for general weights, we show that a greedy algorithm outperforms all of our other heuristics on all non-bipartite graphs.

Finally, we study the problem in the context of trees. We particularly look at the uniform-weight version of the problem. In trees, this is equivalent to finding the Hamiltonian completion number of a tree. We generalize the Jacobsthal numbers, a sequence of natural numbers, and show that the nth number in the generalized m-Jacobsthal sequence is the Hamiltonian completion number of a perfect m-ary tree of height n. Additionally, we prove a few other bounds on solution values in trees, and under certain graph operations. Finally, we explore the relationship between structural controllability and Optimal Channel Networks, a model for river networks.

Return to main PhD Theses page