Approximate Distance Oracle in O(n2) Time and O(n) Space for Chordal Graphs

We preprocess a given unweighted chordal graph

G

on

n

vertices in

O

(

n

2

) time to build a data structure of

O

(

n

) size such that any subsequent distance query can be answered in constant time with a bounded constant factor error. In particular, for each pair of vertices

u

i

,

u

j

 ∈ 

V

(

G

), 1 ≤ 

i

,

j

 ≤ 

n

, we take constant time to output a distance value

d

ij

 ≤ 2

d

G

(

u

i

,

u

j

) + 8 using our data structure, where

d

G

is the distance between

u

i

and

u

j

in

G

. In contrast, for the closely related APSP problem on chordal graphs, the current best algorithm runs in

O

(

n

2.373

) time. Our improvement comes from a relationship that we discover between the graph distance and minimum hitting sets of cliques on certain paths in a clique tree associated with a chordal graph. We design an efficient data structure which additively approximates (error of +3) these minimum hitting sets of cliques for all the paths in the clique tree. This data structure is then integrated with an efficient data structure which answers LCA queries in rooted trees to yield our distance oracle for the given chordal graph.