Pairwise Reachability Oracle and Preserver under failures

DIPTARKA CHAKRABORTY (NUS)

KUSHAGRA CHATTERJEE (NUS)

KEERTI CHOUDHARY (IIT DELHI)

What is Pairwise Reachability Preserver?

​

​

It’s a sparse subgraph H, which preserves the reachability property in between a set of vertex pairs P, even after bounded number failures.

​

​

​

What is Pairwise Reachability Preserver?

​

​

It’s a sparse subgraph H, which preserves the reachability property in between a set of vertex pairs P, even after bounded number failures.

​

​

We call H as k-FTRS (Fault tolerant Reachability Subgraph)

k

Demand Pairs

Example of Pairwise Reachability Preserver

Preserves Reachability

with no failures (k = 0)

G

H

Example of Pairwise Reachability Preserver

Preserves Reachability

with no failures (k = 0)

Cannot preserve reachability

with one failure (k = 1)

G

H

G

H

Example of Pairwise Reachability Preserver

Preserves Reachability

with no failures (k = 0)

Cannot preserve reachability

with one failure (k = 1)

G

H

G

H

1-FTRS

Pairwise Reachability Preserver

Previous Results

Baswana et al (STOC 2016)

Chakraborty and Choudhary (ICALP 2020)

(Corollary)

Pairwise Reachability Preserver (Our Work)

Reachability Preserver

What is Pairwise Reachability Oracle?

It’s a data structure D which answers the reachability query after bounded number of failures in between a given pair of vertices.

​

​

​

What is Pairwise Reachability Oracle?

It’s a data structure D which answers the reachability query after bounded number of failures in between a given pair of vertices.

​

​

We call D as k-FTRO (Fault Tolerant Reachability Oracle)

k

Our work

Query Time: O(1)

Today’s Talk

Reachability Preserver

Upper Bound Construction of 2-FTRS (Single Pair)

S

t

S

t

G

Upper Bound Construction of 2-FTRS (Single Pair)

S

t

S

t

G

(Baswana et al)

Upper Bound Construction of 2-FTRS (Single Pair)

s

t

a

b

c

• For any pair (s,t) we consider two such paths and which intersects only at (s,t) cut vertices and cut edges.

​

Outer strands

Upper Bound Construction of 2-FTRS (Single Pair)

s

t

a

b

c

• For any pair (s,t) we consider two such paths and which intersects only at (s,t) cut vertices and cut edges.

​

• For 1-FTRS, it is enough to preserve these two paths.

​

• Is it enough to preserve these two paths for 2-FTRS?

​

Outer strands

Upper Bound Construction of 2-FTRS (Single Pair)

s

a

b

c

• For any pair (s,t) we would get two such paths and which intersects only at (s,t) cut vertices and cut edges.

​

• Is it enough to preserve these two paths for 2-FTRS?

​

• No, because if there are failures one on and another on , there might be a coupling path such that t is reachable from s using that coupling path.

Coupling Path

Outer strands

t

Pruning of Coupling paths

s

t

Type A

Pruning of Coupling paths

s

t

Type A

Pruning of Coupling paths

s

t

Type A

Pruning of Coupling paths

s

t

s

s

t

Type A

Type B

Pruning of Coupling paths

s

t

s

s

t

Type A

Type B

Pruning of Coupling paths

s

t

s

s

t

Type A

Type B

= Outer Strands + Coupling Paths

= O(n)

Why 2-FTRS?

s

t

s

t

Type A

Type B

Upper Bound Construction of 2-FTRS

s

t

​

​

Upper Bound Construction of 2-FTRS

s

t

​

​

• We create a hitting set of size

Hitting Set which hits all the - subpaths

Upper Bound Construction of 2-FTRS

s

t

• ​

​

• We create a hitting set of size

​

• We construct SS-SD 2-FTRS from each vertex in the hitting set.

Hitting Set (H) which hits all the - subpaths

OR

(Baswana et al)

Upper Bound for 2-FTRS

S

T

G

SS-SD FTRS of each vertex in the hitting set. ( )

Union of all the - paths

SS-SD FTRS of each vertex in the hitting set.

Upper Bound for 2-FTRS

S

T

G

SS-SD FTRS of each vertex in the hitting set. ( )

Union of all the - paths

SS-SD FTRS of each vertex in the hitting set.

Union of all the - paths

Upper Bound for 2-FTRS

S

T

G

SS-SD FTRS of each vertex in the hitting set. ( )

Union of all the - paths

SS-SD FTRS of each vertex in the hitting set.

Union of all the - paths

Union of all coupling paths ( after sparsification)

Upper Bound for 2-FTRS

S

T

G

SS-SD FTRS of each vertex in the hitting set. ( )

Union of all the - paths

SS-SD FTRS of each vertex in the hitting set.

Union of all the - paths

Union of all coupling paths ( after sparsification)

Getting rid of log n factor

S

T

SS-SD FTRS of each vertex in the hitting set. ( )

Union of all the - paths

SS-SD FTRS of each vertex in the hitting set.

Union of all the - paths

Union of all coupling paths ( after sparsification)

Fractional Hitting Set

Lower Bound for 2-FTRS

• Take two arbitrary integers N and r.

Lower Bound for 2-FTRS

Each path is of length N.

• Take two arbitrary integers N and r.

​

• We take r paths of length N in both blocks A and B.

BLOCK A

BLOCK B

Lower Bound for 2-FTRS

Each path is of length N.

• Take two arbitrary integers N and r.

​

• We take r paths of length N in both blocks A and B.

​

• We create a complete bipartite graph in between the vertices at level in Block A with the vertices at level in Block B

BLOCK A

BLOCK B

Level

All Pairs in are in the edge-set

Lower Bound for 2-FTRS

Each path is of length N.

• Take two arbitrary integers N and r.

​

• We take r paths of length N in both blocks A and B.

​

• We create a complete bipartite graph in between the vertices at level in Block A with the vertices at level in Block B

​

• Let

​

• Hence, , and , . Hence,

BLOCK A

BLOCK B

Level

All Pairs in are in the edge-set

Lower Bound for 2-FTRS

Each path is of length N.

• Take two arbitrary integers N and r.

​

• We take r paths of length N in both blocks A and B.

​

• We create a complete bipartite graph in between the vertices at level in Block A with the vertices at level in Block B

​

• Let

​

• Hence, , and , . Hence,

BLOCK A

BLOCK B

Level

All Pairs in are in the edge-set

Future Works

(Closing the Gap)

(Closing the Gap)

Get a better bound

THANK YOU