2026-10-30

It was shown by Fiorini et al. (https://arxiv.org/abs/2106.05947) that

$$\min \{c^{\top }x:Ax\le b,x\in {\mathbb{Z}}^n\}$$

is solvable in strongly polynomial time if $A$ is totally $\Delta$-modular and contains at most two nonzero entries in each row or in each column. This result assumes $\Delta$ is fixed, and the worst-case complexity blows up as $\Delta$ increases. They do not provide a worst-case complexity simply stating that for fixed $\Delta$ it is polynomial time which depends on $\Delta$, but the degree is enormous with no specific exponent provided. For that reason, it may be best to stick to Artmann et al.’s $\Delta =2$ case which has a more reasonable exponent (I believe it is degree 4. They make use of Seymour decomposition theorem).

The MSFN is of the form

$$\min \{c^{\top }(x^{+},x^{-},y^{+},y^{-}):x^{+}-x^{-}-B{y}^{+}+B{y}^{-}=c,x^{+},x^{-},y^{+},y^{-}\in {\mathbb{Z}}_{\ge 0}^{\ast }\}.$$

However, the only crucial component for determining the vertices of the polytope is $y=y^{+}-y^{-}$ and $B$ if on a pseudometric satisfies the requirements for Fiorini et al. Can we perhaps encode the problem in a different way to get it in the correct form while preserving totally $\Delta$-modularity and at most two nonzero entries per row?

We can capture $|y_j|$ by introducing variable $z_j$with constraints

$$\begin{array}{rl}{y}_j-z_j& \le 0\\ z_j& \ge 0\end{array}$$

and the objective terms to

$$y^{+}+y^{-}⟶2z_j-y_j.$$

Indeed, if $y_j<0$ then $z_j=0$ and the cost is $|y_j|$. If $y_j\ge 0$, then $z_j=y_j$ and the cost is $|y_j|$.

For row $i$ of $B$, let $u(i)$ and $v(i)$ be the two non-zero positions with coefficients ${\alpha }_i,{\beta }_i\in \{\pm 1\}$. Then it follows that

$$B_{i}y={\alpha }_i{y}_{u(i)}+{\beta }_i{y}_{v(i)}$$

which implies that

$$x_i=b_i-B_{i}y=b_i-{\alpha }_i{y}_{u(i)}-{\beta }_i{y}_{v(i)}.$$

A classic trick to encode $|x_i|$ is by adding $t_i\ge |b_i-B_{i}y|$:

$$\begin{array}{rl}{t}_i& \ge b_i-B_{i}y=b_i-{\alpha }_i{y}_{u(i)}-{\beta }_i{y}_{v(i)}\\ t_i& \ge B_{i}y-b_i={\alpha }_i{y}_{u(i)}+{\beta }_i{y}_{v(i)}-b_i\end{array}$$

and swapping $|x_i|$ with $t_i$ in the objective.

At this point, our problem looks like

$$\left[\begin{array}{ccc}I& -I& 0\\ 0& -I& 0\\ B& 0& -I\\ -B& 0& -I\end{array}\right]\left[\begin{array}{c}y\\ z\\ t\end{array}\right]\le \left[\begin{array}{c}0\\ 0\\ -b\\ b\end{array}\right].$$

While this preserves totally $\Delta$-modular, we now have three non-zero entries per row.

Define $B=B^1+B^2$ such that $B_i^1$ corresponds to the $u(i)$ entries and $B_i^2$ corresponds to the $v(i)$ entries (if they exist, otherwise the row is just zero). Then we can split $x_i$ up as follows:

$$\begin{array}{rl}{p}_i& =B_i^{1}y={\alpha }_i{y}_{u(i)}\\ q_i& =B_i^{2}y={\beta }_i{y}_{v(i)}\\ x_i& =p_i+q_i.\end{array}$$

Claim: $t_i\ge b_i-B_{i}y$ and $t_i\ge B_{i}y-b_i$ is equivalent to:

$$\begin{array}{rl}{p}_i& \le b_i-{\alpha }_i{y}_{u(i)}\\ q_i& \le -\beta y_{v(i)}\\ p_i+q_i& \le 0\\ p_i^{\prime }& \le {\alpha }_i{y}_{u(i)}-b_i\\ q_i^{\prime }& \le {\beta }_i{y}_{v(i)}\\ p_i^{\prime }+q_i^{\prime }& \le 0.\end{array}$$

Proof. Adding the first two constraints gives us $p_i+q_i\le b_i-B_{i}y$. Likewise, adding constraints 4 and 5 gives us $p_i^{\prime }+q_i^{\prime }\le B_{i}y-b_i$. Through minimization, we get that

$$\begin{array}{rl}{p}_i+q_i& =\min (0,b_i-B_{i}y)\\ p_i^{\prime }+q_i^{\prime }& =\min (0,B_{i}y-b_i).\end{array}$$

Thus, $p_i+q_i$ and $p_i^{\prime }+q_i^{\prime }$ act identical to $x_i^{+}$ and $x_i^{-}$. Thus, we get that

$$\min |x_i|=\min \{-(p_i+q_i)-(p_i^{\prime }+q_i^{\prime })\}.$$

$\square$

Assuming everything is correct, the new ILP is given by

$$\begin{array}{rlrl}& \text{min}& \sum _{i=1}^m{w}_i[-(p_i+q_i)-(p_i^{\prime }+q_i^{\prime })]+\lambda \sum _{j=1}^n{v}_j(2z_j-y_j)& \\ & \text{s.t.}& y_j-z_j& \le 0\\ & & -z_j& \le 0\\ & & p_i+B_i^{1}y& \le b_i\\ & & q_i+B_i^{2}y& \le 0\\ & & p_i+q_i& \le 0\\ & & p_i^{\prime }-B_i^{1}y& \le -b_i\\ & & q_i^{\prime }-B_i^{2}y& \le 0\\ & & p_i^{\prime }+q_i^{\prime }& \le 0.\end{array}$$

Therefore, the constraints in matrix form looks like

$$\left[\begin{array}{cccccc}I& -I& 0& 0& 0& 0\\ 0& -I& 0& 0& 0& 0\\ B^1& 0& I& 0& 0& 0\\ B^2& 0& 0& I& 0& 0\\ 0& 0& I& I& 0& 0\\ -B^1& 0& 0& 0& I& 0\\ -B^2& 0& 0& 0& 0& I\\ 0& 0& 0& 0& I& I\end{array}\right]\left[\begin{array}{c}y\\ z\\ p\\ q\\ p^{\prime }\\ q^{\prime }\end{array}\right]\le \left[\begin{array}{c}0\\ 0\\ b_i\\ 0\\ 0\\ -b_i\\ 0\\ 0\end{array}\right].$$

which satisfies the conditions by Fiorini et al. as long as the boundary matrix $B$ does. Moreover, this matrix is (strictly) totally $\Delta$-modular if and only if $B$ is (strictly) totally $\Delta$-modular. The objective vector is given by

$$\left[\begin{array}{cccccc}-\lambda v^{\top }& 2\lambda v^{\top }& -w^{\top }& -w^{\top }& -w^{\top }& -w^{\top }\end{array}\right].$$

Lemma: Let $A$ be totally $\Delta$-modular with at most two non-zero entries per row and pick a row $r=\alpha e_u+\beta e_v$ of $A$ with $\alpha ,\beta \in \{-1,0,1\}$. Build the matrix $A^{\prime }$ by the following steps:

1. Remove row $r$
2. Add two new columns $p$ and $q$
3. Add three rows: $r_1=\alpha e_u+e_p$, $r_2=\beta e_v+e_q$, and $r_3=e_p+e_q$.

It follows that $A^{\prime }$ is totally $\Delta$-modular.

Proof. Let $S$ be a square submatrix of $A^{\prime }$. Split the rows of $S$ into $R$ containing rows of $A$ that are not $r$, and added rows $R^{\prime }\subseteq \{r_1,r_2,r_3\}$. We consider four cases on the new columns in $S$.

Case 1 (no new columns are added): If $r_3$ is in $R^{\prime }$, then it follows that there is a zero row implying that $\det S=0$. Otherwise, $S$ is a submatrix of $A$ with potentially $\alpha e_u$ or $\beta e_v$ added. Thus, $|\det S|\le \Delta$ by Lemma 2.2.

Case 2 (only column $p$ is added): Column $p$ only shows up in $r_1$ and $r_3$. Clearly, if $S$ uses neither rows, then there is a zero column so $\det S=0$. Assume only $r_1$ is used. Then we get the submatrix

$$\left[\begin{array}{cccccc}\alpha & \cdots & 0& \cdots & 1& 0\end{array}\right]$$

which can be eliminated by expanding along column $p$ giving a submatrix of $A$. We get a simiilar case if only $r_3$ is used. If $r_1$ and $r_3$ are both in $S$, then we get the submatrix

$$\left[\begin{array}{cccccc}\alpha & \cdots & 0& \cdots & 1& 0\\ 0& \cdots & 0& \cdots & 1& 0\end{array}\right]$$

Apply the row operation $r_1\leftarrow r_1-r_3$, which does not alter $\det S$. Then by expanding along column $p$, we get a submatrix $S^{\prime }$ which is simply a submatrix of $A$ with $\alpha$ inserted along a single row. Thus, by case 1, $|\det S|=|\det S^{\prime }|\le \Delta$.

Case 3 (only column $q$ is added): Same case as case 2 but with $r_2$ instead of $r_1$.

Case 4 (both $p$ and $q$): Notice that if $S$ contains less than two rows from $\{r_1,r_2,r_3\}$, then there will be at least one zero column along $p$ or $q$ giving $\det S=0$. We break into cases on which rows are in $S$.

• $\{r_1,r_2\}$: then we have the following submatrix in $S$

$$\left[\begin{array}{cccccc}\alpha & \cdots & 0& \cdots & 1& 0\\ 0& \cdots & \beta & \cdots & 0& 1\end{array}\right].$$

By expanding along $p$ and $q$ we have removed the additions giving a submatrix of $A$.

• $\{r_1,r_3\}$: then we have the following submatrix in $S$

$$\left[\begin{array}{cccccc}\alpha & \cdots & 0& \cdots & 1& 0\\ 0& \cdots & 0& \cdots & 1& 1\end{array}\right].$$

Expanding along column $q$ then column $p$ to remove the additions gives a submatrix of $A$.

• $\{r_2,r_3\}$: similar argument as $\{r_1,r_3\}$.
• $\{r_1,r_2,r_3\}$: then we have the following submatrix in $S$

$$\left[\begin{array}{cccccc}\alpha & \cdots & 0& \cdots & 1& 0\\ 0& \cdots & \beta & \cdots & 0& 1\\ 0& \cdots & 0& \cdots & 1& 1\end{array}\right].$$

Perform the row operations $r_3\leftarrow r_3-r_1$ and $r_3\leftarrow r_3-r_2$ to get the new submatrix

$$\left[\begin{array}{cccccc}\alpha & \cdots & 0& \cdots & 1& 0\\ 0& \cdots & \beta & \cdots & 0& 1\\ -\alpha & \cdots & -\beta & \cdots & 0& 0\end{array}\right].$$

Expanding along columns $p$ and $q$ leaves a submatrix of $A$ in which row $r$ was negated. Thus, $|\det S|\le \Delta$.

Therefore, all cases give $|\det S|\le \Delta$. $\square$

Claim: If $B$ is totally $\Delta$-modular, so is the constraint matrix $M$.

Proof. Starting from $B$, we can build $M$ by the following steps:

1. For each row $B_i$, create a copy of $-B_i$
2. For each row $B_i$ apply the above lemma which gives the $p$ and $q$ blocks. Repeat for each row $-B_i$ to get the $p^{\prime }$ and $q^{\prime }$ blocks.
3. Add $-I$ blocks for $z$.
4. Apply row/column permutations.

All of the above operations preserve totally $\Delta$-modular. $\square$

Question: Is $M$ strictly totally $\Delta$-modular?

Theorem: Let $\Delta \ge 1$ be a fixed integer. Then there is a strongly polynomial time algorithm for the subset of MSFN instances in which $|K|$ is a pseudomanifold and $[{\partial }_n]$ is totally $\Delta$-modular is solvable in strongly polynomial time.