Realization Problems on Reachability Sequences
Realization Problems on Reachability Sequences
复制标题
DOI：
10.1007/978-3-030-58150-3_22
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Matthew Dippel;Ravi Sundaram;Akshar Varma
中科院分区：
文献类型：
--
作者：
Matthew Dippel;Ravi Sundaram;Akshar Varma
经典的Erdös-Gallai定理（1960）通过描述度序列开始了对图可实现性的研究。我们扩展这条线的研究，通过调查的可实现性的有向无环图（DAG）给定的元组序列，每个包含多个节点的属性，包括程度，可达性值（从一个给定的节点可达的节点数），深度和高度的节点。最有趣的问题是当序列包含通过度值的局部约束和通过可达性值的全局约束时。我们发现，没有度的限制，DAG可达实现是可解的线性时间，而它是强NP-完全的上限内度或度。在定义了一个合适的概念的双准则近似一致性的基础上，我们给出了两个近似算法实现O（log n）-可达性一致性和O（log n）-度一致性;第一，随机，使用LP（线性规划）舍入，而第二，确定性，采用k-集包装启发式。最后，我们提出了一些未来的研究方向和一组图表，我们希望这将激励进一步研究可达性约束的可实现性。
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.