Near-Linear Query Complexity for Graph Inference

How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? Let

$$G = (V,E)$$

G

=

(

V

,

E

)

be a connected, undirected, and unweighted graph of bounded degree. The edge set

E

is initially unknown, and the graph can be accessed using a

distance oracle

, which receives a pair of vertices (

u

,

v

) and returns the distance between

u

and

v

. In the

verification

problem, we are given a hypothetical graph

$$\hat{G} = (V,\hat{E})$$

G

^

=

(

V

,

E

^

)

and want to check whether

G

is equal to

$$\hat{G}$$

G

^

. We analyze a natural greedy algorithm and prove that it uses

$$n^{1+o(1)}$$

n

1

+

o

(

1

)

distance queries. In the more difficult

reconstruction

problem,

$$\hat{G}$$

G

^

is not given, and the goal is to find the graph

G

. If the graph can be accessed using a

shortest path oracle

, which returns not just the distance but an actual shortest path between

u

and

v

, we show that extending the idea of greedy gives a reconstruction algorithm that uses

$$n^{1+o(1)}$$

n

1

+

o

(

1

)

shortest path queries. When the graph has bounded treewidth, we further bound the query complexity of the greedy algorithms for both problems by

$$\tilde{O}(n)$$

O

~

(

n

)

. When the graph is chordal, we provide a randomized algorithm for reconstruction using

$$\tilde{O}(n)$$

O

~

(

n

)

distance queries.