Exact learning of multitrees and almost-trees using path queries

DOI10.1007/978-3-031-20624-5_18MaRDI QIDQ6109014zbMATH OpenOpenAlexFDO

Authors Ramtin Afshar, Michael T. Goodrich

Publication date 26 July 2023

Published in LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.04216

zbMATH Keywords

directed acyclic graphsexact learninggraph reconstruction

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Abstract: 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.

Cites work

• A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
• An optimal algorithm to reconstruct trees from additive distance data
• Circuit and decision tree complexity of some number theoretic problems
• Constructing Computer Virus Phylogenies
• Decision tree complexity and Betti numbers
• Exact learning of multitrees and almost-trees using path queries
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• From query complexity to computational complexity
• Graph reconstruction with a betweenness oracle
• scientific article; zbMATH DE number 2079368 (Why is no real title available?)
• scientific article; zbMATH DE number 7651142 (Why is no real title available?)
• Learning a bounded-degree tree using separator queries
• On the longest path algorithm for reconstructing trees from distance matrices
• Optimal query complexity bounds for finding graphs
• Parallelism in Comparison Problems
• Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
• Reconstruction and verification of chordal graphs with a distance oracle
• The multi-tree approach to reliability in distributed networks
• The query complexity of finding a hidden permutation
• The spectra of wrapped butterfly digraphs

Cited in

(4)

• On the hardness of learning queries from tree structured data
• Algorithms for learning parsimonious context trees
• The Complexity of Learning Tree Patterns from Example Graphs
• Exact learning of multitrees and almost-trees using path queries

This page was built for publication: Exact learning of multitrees and almost-trees using path queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109014)