We propose a combinatorial optimisation model called Limited Query Graph
Connectivity Test. We consider a graph whose edges have two possible states
(on/off). The edges' states are hidden initially. We could query an edge to
reveal its state. Given a source s and a destination t, we aim to test s-t
connectivity by identifying either a path (consisting of only on edges) or a
cut (consisting of only off edges). We are limited to B queries, after which we
stop regardless of whether graph connectivity is established. We aim to design
a query policy that minimizes the expected number of queries.
If we remove the query limit B (i.e., by setting B to the total number of
edges), then our problem becomes a special case of (monotone) Stochastic
Boolean Function Evaluation (SBFE). There are two existing exact algorithms
that are prohibitively expensive. They have best known upper bounds of O(3^m)
and O(2^{2^k}) respectively, where m is the number of edges and k is the number
of paths/cuts. These algorithms do not scale well in practice.
We propose a significantly more scalable exact algorithm. Our exact algorithm
works by iteratively improving the performance lower bound until the lower
bound becomes achievable. Even when our exact algorithm does not scale, it can
be used as an anytime algorithm for calculating lower bound.
We experiment on a wide range of practical graphs. We observe that even for
large graphs (i.e., tens of thousands of edges), it mostly takes only a few
queries to reach conclusion, which is the practical motivation behind the query
limit B. B is also an algorithm parameter that controls scalability. For small
B, our exact algorithm scales well. For large B, our exact algorithm can be
converted to a heuristic (i.e., always pretend that there are only 5 queries
left). Our heuristic outperforms all existing heuristics ported from SBFE and
related literature.

提出了一种组合优化模型，可以在限定次数的查询下寻找图中两点的连通性，创新性地提出了一种较为可扩展的精确算法以及适用于大规模数据的启发式算法。