Non-adaptive Group Testing on Graphs
Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problem of learning a hidden graph for some especial cases, such as hamiltonian cycle, cliques, stars, and matchings. This problem is motivated by problems in chemical reactions, molecular biology and genome sequencing. In this paper, we present a generalization of this problem. Precisely, we consider a graph G and a subgraph H of G and we assume that G contains exactly one defective subgraph isomorphic to H. The goal is to find the defective subgraph by testing whether an induced subgraph contains an edge of the defective subgraph, with the minimum number of tests. We present an upper bound for the number of tests to find the defective subgraph by using the symmetric and high probability variation of Lov\'asz Local Lemma.
Code (0)
등록된 구현이 없습니다.
Tasks
LEMMASimilar Papers 제목 키워드 기반
A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs
We study the problem of learning an unknown graph via group queries on node subsets, where each query reports whether at least one edge is present among the queried nodes. In general, learning arbitrary graphs with $n$ n…
Graph LearningNon-adaptive Learning of Random Hypergraphs with Queries
We study the problem of learning a hidden hypergraph $G=(V,E)$ by making a single batch of queries (non-adaptively). We consider the hyperedge detection model, in which every query must be of the form: ``Does this set $S…
AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing
The first part of the paper presents a review of the gold-standard testing protocol for Covid-19, real-time, reverse transcriptase PCR, and its properties and associated measurement data such as amplification curves that…
Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design
When the infection prevalence of a disease is low, Dorfman showed 80 years ago that testing groups of people can prove more efficient than testing people individually. Our goal in this paper is to propose new group testi…
DecoderExperimental DesignGraph Fairness Learning under Distribution Shifts
Graph neural networks (GNNs) have achieved remarkable performance on graph-structured data. However, GNNs may inherit prejudice from the training data and make discriminatory predictions based on sensitive attributes, su…
Fairness