论文标题
在学习带有路径查询的隐藏的有向图
On Learning a Hidden Directed Graph with Path Queries
论文作者
论文摘要
在本文中，我们考虑使用路径查询重建有向图的问题。在此查询的学习模型中，从学习者中隐藏了图形，学习者可以通过路径查询访问有关它的信息。对于源和目标节点，路径查询返回是否有从源到隐藏图中目标节点的有向路径。在本文中，我们首先为$ n $顶点和$ k $连接的组件提供学习图。然后，我们研究了有限程度的定向树木的情况，并提供了学习“几乎树”的新算法 - 已添加了额外边缘的定向树。我们还提供了一些下限结构，以证明我们的方法是合理的。
In this paper, we consider the problem of reconstructing a directed graph using path queries. In this query model of learning, a graph is hidden from the learner, and the learner can access information about it with path queries. For a source and destination node, a path query returns whether there is a directed path from the source to the destination node in the hidden graph. In this paper we first give bounds for learning graphs on $n$ vertices and $k$ strongly connected components. We then study the case of bounded degree directed trees and give new algorithms for learning "almost-trees" -- directed trees to which extra edges have been added. We also give some lower bound constructions justifying our approach.
