／var／logmarcus chiu

Maximum Independent／Disjoint Paths Problem

Created on

Maximum Independent/Disjoint Paths Problem Types

  • maximum edge-independent/disjoint paths problem - find max number of edge-disjoint s-t paths (2 paths are edge-independent/disjoint if they have no arc/edge in common)
  • maximum node-independent/disjoint paths problem - find max number of node-disjoint s-t paths (2 paths are node-independent/disjoint if they have no vertex/node in common)

Solving Maximum Edge-Independent/Disjoint Paths Problem With Maximum Flow

  • assign each directed edge with a unit capacity
  • then apply MaxFlow algorithm

THEOREM: there are k edge-independent/disjoint paths from s to t if and only if the max flow value is k

Solving ALL Independent/Disjoint Path Problems With Maximum Flow

Edge-Independent/Disjoint Paths

Node-Independent/Disjoint Paths

Directed Graph
  • reduce to MaxFlow with unit capacities
  • node split
  • reduce to MaxFlow with unit capacities

Undirected Graph
  • use gadget
  • reduce to MaxFlow with unit capacities
  • edge split
  • node split
  • reduce to MaxFlow with unit capacities

Node Split

Edge Split

Gadget