Exact Learning of Multitrees and Almost-Trees Using Path Queries
Exact Learning of Multitrees and Almost-Trees Using Path Queries
复制标题
DOI：
10.48550/arxiv.2208.04216
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Ramtin Afshar;M. Goodrich
中科院分区：
文献类型：
--
作者：
Ramtin Afshar;M. Goodrich
给定有向图G=（V，E），路径查询path（u，v）返回G中是否存在从u到v的有向路径，对于V中的u，v顶点。在本文中，我们研究了精确学习的查询复杂度的情况下，学习G是可能的使用路径查询。特别是，我们提供了有效的学习算法，以及下界，多树和几乎树，包括蝴蝶网络。
Given a directed graph, G=(V,E), a path query, path(u,v), returns whether there is a directed path from u to v in G, for u,v vertices in V. Given only V, exactly learning all the edges in G using path queries is often impossible, since path queries cannot detect transitive edges. In this paper, we study the query complexity of exact learning for cases when learning G is possible using path queries. In particular, we provide efficient learning algorithms, as well as lower bounds, for multitrees and almost-trees, including butterfly networks.