Name
Abstract | ||
|---|---|---|
The classical Erdos-Gallai theorem 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 both a local constraint via degree sequences and a global constraint via a sequence of reachability values (number of nodes reachable from a given node). 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 two conjectures that we hope motivate further study of realizability with reachability constraints. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-58150-3_22 | COCOON |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthew Dippel | 1 | 0 | 0.34 |
| Ravi Sundaram | 2 | 762 | 72.13 |
| Akshar Varma | 3 | 0 | 0.34 |