کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429702 | 687638 | 2008 | 11 صفحه PDF | دانلود رایگان |

We consider the problem of learning a general graph using edge-detecting queries. In this model, the learner may query whether a set of vertices induces an edge of the hidden graph. This model has been studied for particular classes of graphs by Grebinski and Kucherov [V. Grebinski, G. Kucherov, Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs, in: Fifth Israel Symposium on the Theory of Computing Systems, 1997, pp. 166–173] and Alon et al. [N. Alon, R. Beigel, S. Kasif, S. Rudich, B. Sudakov, Learning a hidden matching, in: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 197–206], motivated by problems arising in genome sequencing. We give an adaptive deterministic algorithm that learns a general graph with n vertices and m edges using O(mlogn) queries, which is tight up to a constant factor for classes of non-dense graphs. Allowing randomness, we give a 5-round Las Vegas algorithm using queries in expectation. We give a lower bound of Ω((2m/r)r/2) for learning the class of non-uniform hypergraphs of dimension r with m edges.
Journal: Journal of Computer and System Sciences - Volume 74, Issue 4, June 2008, Pages 546-556