Title | : | A Linear Size Approximate Distance Oracle for Chordal Graphs |
Speaker | : | Gaurav Singh (IIT Madras) |
Details | : | Mon, Jul 28, 2014 3:00 PM, @ BSB 361 |
Abstract | : | A Graph is chordal if every cycle of length greater than three has a chord. Chord is an edge joining two non adjacent vertices. We present a distance oracle for chordal graphs. Distance oracle is a data structure that stores information of the distance between vertices of a graph. Given a chordal graph G on n vertices we preprocess it in O(n^2) time and space to build a data structure of size O(n) 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,v in V(G), we output a distance value d <= d_G(u,v) + 11, where d_G(u,v) is the distance between u and v in G. In contrast, for the closely related APSP problem on chordal graphs, the current best algorithm runs in O(n^2.376) 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 then design an efficient data structure to additively approximate (error of +3) these minimum hitting sets of cliques for all paths in the clique tree. These are then integrated with an efficient data structure to answer LCA queries in rooted trees to yield our distance oracle for a given chordal graph. Chordal graphs are often represented by its Clique Tree in very compact and efficient manner. Clique tree is a structure that contains most of the information of the associated chordal graph. We exploit the structural properties of the clique tree to extract the distance information of the associated chordal graph. We keep this information in a data structure that can answer any query of distance between any pair of vertices of graph in constant time.The most impressive feature of our data structure is its constant query time in spite of the fact that it uses only linear space, i.e., it does not store distance between all the pairs of vertices explicitly. (This is the MS Seminar, cross listed here). |