# Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.

The answer is probably negative. But my problem at hand is simply the shortest path problem.

Consider a graphical model with two variables

$$X - Y$$

Both $X$ and $Y$ can take one of the two states $\{1,2\}$. The task is to find the assignment of $X$ and $Y$ that minimizes

$$f(X,Y) = \sum_{i=1}^2 \sum_{j=1}^2 T_{ij} \cdot [X=i \ \&\& \ Y=j].$$

$T_{ij} \ge 0$ are given parameters. $[x]=1$ if $x$ is true, and $0$ otherwise. More generally we can have longer chains and more states, solvable by the Baum-Welch algorithm.

Question: is it possible to formulate this problem as a submodular minimization problem (over a lattice), so that the optimal $X$ and $Y$ can be read from its solution? Some straightforward trials fail:

1. Encode $X=1$ by including $X$. It fails because no assumption is made on $T$.

2. Introduce two indicator variables for $X=0$ and $X=1$. But then the constraint of exclusion leaves the feasible set not a lattice.

I guess it can be boiled down to min-cut, which has a submodular objective. But I still can't connect the dots. It is ok to add auxiliary variables, but going to the dual will be a pain (as this problem is nested in another problem at hand).

Thanks in advance.

• Is $T$ just 2x2? Why can't you just enumerate all 4 values of $T_{ij}$ and select whichever is smallest? – Nicholas Mancuso Feb 2 '16 at 1:01