UC Irvine

Parameterized complexity provides an important framework to deal with hard problems by restricting some problem parameter to be a fixed constants. Problems which are categorized as fixed-parameter tractable with respect to some parameters are problems that can be solved in polynomial time, if such parameters are bounded by a fixed value.

In this dissertation, in Chapter 2, we first study the problem of recognizing k-leaf powers and representing k-leaf roots. A graph G is a k-leaf power of a tree if its vertices correspond to leaves of the tree and a pair of leaves have distance at most k if and only if the corresponding vertices in G are adjacent. Then, the tree is a k-leaf root of G. A graph is a k-leaf power if it has at least one k-leaf root. We show recognizing k-leaf powers parameterized by k and the degeneracy of the input graph is fixed parameter tractable. This is the first result in the literature studying this problem in the paradigm of parameterized complexity and providing a polynomial-time algorithm working on multiple values of k.

Following this line of work, in Chapter 3, we study the parameterized complexity of the problem of finding induced subgraphs with hereditary properties under the condition that the input graph belongs to a hereditary graph class, as well. In this work, we provide a framework that settles the parameterized complexity of various graph classes.

To show the importance of graph representation, we emphasize that our proposed technique for recognition of k-leaf powers for graphs of bounded degeneracy heavily relies on our representation of k-leaf roots as a subgraph of the graph product of the input graph and a cycle graph of size k. Additionally, in Chapter 4, we study the problem of simplifying activity-on-edge graphs, which provides an insight on how graph representation can further help data analysis such as enabling a better understanding of the flow of project schedules. In an activity-on-edge graph, vertices represent project milestones and edges represent the tasks/activities of the project. We simplify such representations of project schedules to enhance visualization of an abstract timeline of the potential critical paths of the project by optimally minimizing the number of vertices while maintaining the reachability relations among tasks.