Realization problems on reachability sequences

The classical Erdös-Gallai theorem (1960) kicked off the study of graph realizability by characterizing degree sequences. We extend this line of research by investigating realizability of directed acyclic graphs (DAGs) given a sequence of tuples each containing multiple node properties including the degree, reachability value (number of nodes reachable from a given node), depth and height of a node. The most interesting problems are when the sequences contain both a local constraint via degree values and a global constraint via reachability values. We show that, without degree constraints, DAG reachability realization is solvable in linear time, whereas it is strongly NP-complete given upper bounds on in-degree or out-degree. After defining a suitable notion of bicriteria approximation based on consistency, we give two approximation algorithms achieving O ( log ⁡ n ) -reachability consistency and O ( log ⁡ n ) -degree consistency; the first, randomized, uses LP (Linear Program) rounding, while the second, deterministic, employs a k-set packing heuristic. We end with some future directions of research and a set of conjectures that we hope will motivate further study of realizability with reachability constraints.

Authors

• Matthew Dippel
• Ravi Sundaram Northeastern University
• Akshar Varma

Keywords

• Reachability sequences
• Graph realization
• Bicriteria approximation
• Strong NP-completeness