1 of 33

Faster Algorithm for Second (s,t)-Mincut & Breaking Quadratic Barrier for Dual Edge Sensitivity for (s,t)-Mincut

Surender Baswana1, Koustav Bhanja2, and Anupam Roy3

​

1,3: IIT Kanpur, India

2: Weizmann Institute of Science, Israel

​

 

ESA 2025

Funding: Tapas Mishra Memorial Chair of Surender Baswana and ERC grant of Merav Parter

2 of 33

2

 

 

 

 

 

 

 

 

 

Contributing edges

 

 

 

 

 

 

 

 

 

(s,t)-cut?

3 of 33

A (Global) Cut?

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 of 33

Global Mincut

4

 

 

 

 

(s,t)-Mincut

Two Well-Known Mincuts

 

 

 

 

5 of 33

(s,t) Mincut

 

 

 

 

 

Second (s,t)-Mincuts

 

 

 

 

6 of 33

Our Main Results

6

 

7 of 33

Problem 1

7

 

8 of 33

Why Second?

8

 

 

 

+

 

Almost settled!

 

 

9 of 33

Existing Algorithms

 

 

 

Our Results

 

 

10 of 33

10

Key Idea: An ‘Equivalence’

Computing

Second (s,t)-mincut

Computing Global mincut

 

11 of 33

11

Time Complexity Difference: (s,t)-cut and Global Cut

(s,t)-mincut

in Directed Weighted Graph

Global Mincut

in Undirected Weighted Graph

 

 

(s,t)-mincut

in Directed Weighted Graph

Global Mincut

in Directed Weighted Graph

 

 

Second (s,t)-mincut

in Directed Weighted Graph

 

Global Mincut

in Directed Weighted Graph

 

 

 

12 of 33

A Special case : Minimum+1 (s,t)-cut

 

 

13 of 33

Problem 2

13

 

14 of 33

Sensitivity Oracle

14

Compact

Data Structure

Graph

 

Query

Output

Query

Output

Pre-process Graph

Static Algorithm

Significantly Faster!

1.

2.

Sensitivity

Oracle

15 of 33

Existing Single Edge Sensitivity Oracle

15

Addressing dual edge sensitivity,

Well-Studied!

 

 

-Picard and Queyranne,

Math. Prog. Studies 1980

Multiple Edge Failures?

16 of 33

16

 

 

17 of 33

Existing and New Results

17

 

Baswana, Bhanja, and Pandey,

ICALP 2022, TALG 2023

​

Bhanja, ICALP 2025

Multi-Graphs

Undirected Multi-graphs

 

Bhanja, ICALP 2025

Undirected Simple Graphs

 

irrespective of query time

 

18 of 33

Key Tool

Linear Space Structure for characterizing all min+1 (𝑠,𝑡)-Cuts

19 of 33

 

19

 

Directed Multigraphs

Matches the bound on space

With DAG of [Picard & Queyranne 1980]

for (s,t)-mincuts

 

[Baswana, Bhanja, and Paney, ICALP 2022 & TALG 2023]

Undirected Multigraphs

 

 

 

 

20 of 33

Overview of Our First Result

Algorithm for Second (s,t)-mincut

​

21 of 33

21

 

 

 

 

 

 

22 of 33

22

 

 

 

23 of 33

23

Approach: Equivalence between

global mincut and Second (s,t)-mincut

 

 

 

 

24 of 33

24

Approach: Establishing Opposite Direction

 

 

 

25 of 33

Global Mincut

25

 

 

 

 

(s,t)-Mincut

Relation b/w Global Mincut and (s,t)-cuts

 

 

 

 

 

Second (s,t)-Mincut

26 of 33

Residual Graph as a “Bridge”�

27 of 33

27

Residual Graph

 

 

 

 

 

28 of 33

28

 

 

 

 

 

 

 

 

 

 

 

Flow Conservation

29 of 33

29

 

 

 

 

 

 

 

30 of 33

30

Establishing ‘Equivalence’

 

 

 

 

 

 

 

 

 

 

31 of 33

31

 

Any graph

 

Generalizing: [BBP23] Graph Decomposition

32 of 33

32

 

Open Problems

33 of 33

Thank you.

Koustav Bhanja

Email: koustav.bhanja@weizmann.ac.il