Margaret Mitchell's PhD Thesis

Title: On the Complexity of Creating Vertex Series Parallel Graphs from Directed Acyclic Graphs.

Motivation: The necessity for breaking up graphs (such as PERT charts for example) into subgraphs in order gain an understanding of the underlying dependencies, and the difficulty of doing so for many graphs without a loss of dependency information.

Supervisors: Prof. Mike Johnson, Prof. Bernard Mans and Prof. Norman Foo.


Abstract

In this thesis we establish NP-Completeness for a decision problem associated with adding edges to a directed acyclic graph to create a graph that is vertex series parallel. This decision problem has applications for representing prerequisite information in a structured way.

Directed acyclic graphs are a natural means of representing prerequisite information that involves parallelism. An item a can be represented a vertex. The notion of item a being a prerequisite for item b can be represented by the directed edge (a,b). However, for a large or complex graph, obtaining an overall view of the relationships it contains becomes difficult unless the graph can be decomposed into distinct parts.

Directed acyclic graphs do not generally lend themselves to appropriate decomposition. There exists, however, a subset of directed acyclic graphs, called vertex series parallel (VSP) graphs, which, once transitively reduced, are easily decomposed. Transitive reduction does not alter the prerequisite relationships in a graph, and decomposing a transitively reduced VSP graph permits a top-down view of the relationships within the graph. This provides a better understanding of the prerequisite information within the graph. It is therefore useful to be able to transform any directed acyclic graph into a graph that is VSP by the addition of edges, and we show that this transformation can be performed successfully for any directed acyclic graph.

In transforming a directed acyclic graph to a VSP graph, we want the number of edges added to a given graph to be as few as possible, in order for the resulting graph to be as similar as possible to the original graph. This raises the question of whether there exists a polynomial-time algorithm for finding an optimally transformed VSP graph for a given directed acyclic graph. We define an associated decision problem, and we prove this problem to be NP-Complete.