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:
Encode $X=1$ by including $X$. It fails because no assumption is made on $T$.
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.
