Prophets in Parallel: Dynamic Cut Minimization in Series-Parallel Graphs
\(\)
We introduce a sequential version of the minimum $s$-$t$ cut problem, defined by a directed graph with source $s$ and sink $t$, and nonnegative random variables for each arc representing arc weights. We start with a working set $S = \{s\}$ and observe weight realizations for outgoing arcs from $S$ only. We choose to either stop or to add a node to $S$ with the objective of minimizing the expected weight of the chosen cut. When the graph is a directed $s$-$t$ path, the model reduces to the classical prophet inequality problem in minimization form. We formulate the problem as a dynamic program (DP) and show that computing the expected cost of an optimal policy is #P-hard even on series-parallel graphs. We leverage a linear programming (LP) formulation of the DP to construct a separable cost-to-go function approximation (CFA), yielding a lower bound. We design a heuristic policy based on the CFA and provide a worst-case performance guarantee that depends on graph topology but is independent of arc weight distributions. Our computational experiments demonstrate the empirical quality of the heuristic policy.