Directed acyclic constrained connectivity: complexity and applications

Abstract

In this thesis we will explore a new problem on Graph Theory named Directed Acyclic Constrained Connectivity. Directed Acyclic Constrained Connectivity is a modification of (s, t)-Connectivity where we introduce constraints that restrict edge use. We show that Directed Acyclic Constrained Connectivity is NP-Complete. We reduce Graph Coloring problems such as the 3-Coloring Problem to Directed Acyclic Constrained Connectivity. We also show that Directed Acyclic Constrained Connectivity can be related to the enumeration of Maximal Independent Sets. This means that some cases of Directed Acyclic Constrained Connectivity are solvable in polynomial time using advanced algorithms for enumerating Maximal Independent Sets. Finally, we apply our findings to a problem in the field of Access Control and Cyber Security. We show that the Safety Problem for the Next Generational Access Control (NGAC) Model is NP-Complete based on our findings for Directed Acyclic Constrained Connectivity. The NGAC Model is a new model for Access Control that is based on the Role Based Access Control (RBAC) Model.