11institutetext: Sauder School of Business, University of British Columbia,
Canada
11email<EMAIL_ADDRESS>
22institutetext: School of Mathematics, Georgia Institute of Technology, USA
22email<EMAIL_ADDRESS>
33institutetext: Department of Mathematics, University of California Davis,
USA
33email<EMAIL_ADDRESS>
# Extended formulations for a class of polyhedra with bimodular cographic
constraint matrices

Joseph Paat 11 Zach Walsh 22 Luze Xu 33

###### Abstract

We are motivated by integer linear programs (ILPs) defined by constraint
matrices with bounded determinants. Such matrices generalize the notion of
totally-unimodular matrices. When the determinants are bounded by $2$, the
matrix is called bimodular. Artmann et al. give a polynomial-time algorithm
for solving any ILP defined by a bimodular constraint matrix. Complementing
this result, Conforti et al. give a compact extended formulation for a
particular class of bimodular-constrained ILPs, namely those that model the
stable set polytope of a graph with odd cycle packing number $1$. We
demonstrate that their compact extended formulation can be modified to hold
for polyhedra such that (1) the constraint matrix is bimodular, (2) the row-
matroid generated by the constraint matrix is cographic and (3) the right-hand
side is a linear combination of the columns of the constraint matrix. This
generalizes the important special case from Conforti et al. concerning
4-connected graphs with odd cycle transversal number at least four. Moreover,
our results yield compact extended formulations for a new class of polyhedra.

##  1 Introduction.

For a constraint matrix $\mathbf{A}\in\mathbb{Z}^{m\times n}$ with
$\operatorname{rank}(\mathbf{A})=n$ and a right-hand side
$\mathbf{b}\in\mathbb{Z}^{m}$, define the polyhedron

$\mathcal{P}:=\left\\{\mathbf{x}\in\mathbb{R}^{n}:\
\mathbf{A}\mathbf{x}\leq\mathbf{b}\right\\}.$ (1)

The integer linear programming (ILP) problem is to check if
$\mathcal{P}\cap\mathbb{Z}^{n}$ is feasible or empty. Although the ILP problem
is NP-complete in general, see, e.g., [25], Lenstra shows in [17] that it can
be solved in polynomial time if the parameter $n$ is fixed. Looking beyond
Lenstra, an open question is whether or not the ILP problem can be solved when
a different parameter is fixed, namely the largest determinant of the
constraint matrix $\mathbf{A}$:

$\Delta(\mathbf{A}):=\max\left\\{|\det\mathbf{B}|:\ \mathbf{B}~{}\text{is an
$n\times n$ submatrix of $\mathbf{A}$}\right\\}.$

We say that $\mathbf{A}$ is $\Delta$-modular if $\Delta(\mathbf{A})\leq\Delta$
for $\Delta\in\mathbb{N}$.

There is a collection of work supporting the conjecture that an ILP can be
solved when $\mathbf{A}$ is $\Delta$-modular and $\Delta$ is fixed. For
instance, if $\Delta(\mathbf{A})=1$, then $\mathbf{A}$ is equivalent (up to a
unimodular mapping) to a totally unimodular (TU) constraint matrix; in this
setting, the ILP can be solved via linear programming; see, e.g., [25].
Another notable piece of work tackles the setting when $\Delta(\mathbf{A})\leq
2$, where the matrix $\mathbf{A}$ is called bimodular. Artmann et al. [2] show
that even the optimization version of integer linear programming can be solved
in strongly polynomial time when $\mathbf{A}$ is bimodular. For the setting
$\Delta\geq 3$, there are various works that prove the conjecture under
additional assumptions, e.g., no determinants of $\mathbf{A}$ are zero [1],
all determinants of $\mathbf{A}$ are $0$ or $\pm\Delta$, and $\Delta\leq 4$
[18, 20], or each row and/or column of $\mathbf{A}$ has at most two non-zero
entries [10]. Along similar lines of work, there are many structural results
about $\Delta$-modular matrices, e.g., proximity to the linear relaxation [6],
sparsity of solutions [12, 15], the so-called column number, which in some way
bounds the dimension of the ILP [3, 11, 16, 22, 23, 24]. However, to the best
of our knowledge the conjecture remains open in its general form, even when
$\Delta=3$.

In this manuscript, we revisit the setting when $\mathbf{A}$ is bimodular. The
bimodular algorithm given by Artmann et al. [2] applies Seymour’s
decomposition of TU matrices [27]. Conforti et al. [9] give an alternative
approach for the following special class of bimodular problems. Suppose $G$ is
a graph on $n$ nodes with edge-node incidence matrix $\mathbf{M}$. The
corresponding stable set polytope $\operatorname{STAB}(G)$ is the convex hull
of all incidence vectors corresponding to stable sets, that is,

$\operatorname{STAB}(G)=\operatorname{conv}(\mathcal{P}_{G}\cap\mathbb{Z}^{n}),$

where

$\mathcal{P}_{G}:=\left\\{\mathbf{x}\in\mathbb{R}^{n}:\
\mathbf{A}^{\prime}\mathbf{x}\leq\mathbf{b}^{\prime}\right\\}:=\left\\{\mathbf{x}\in\mathbb{R}^{n}:\
\left[\begin{array}[]{c}\mathbf{M}\\\ \phantom{-}\mathbf{I}\\\
-\mathbf{I}\end{array}\right]\mathbf{x}\leq\left[\begin{array}[]{c}\mathbf{0}\\\
\mathbf{1}\\\ \mathbf{0}\end{array}\right]\right\\}.$ (2)

It is known that $\Delta(\mathbf{A}^{\prime})=2^{\operatorname{ocp}(G)}$,
where $\operatorname{ocp}(G)$ is the maximum number of node disjoint odd
cycles in $G$ [13]. Thus, if $\operatorname{ocp}(G)=1$, then
$\mathbf{A}^{\prime}$ is bimodular. Conforti et al. design a compact extended
formulation for $\operatorname{STAB}(G)$ when $\operatorname{ocp}(G)=1$. An
extended formulation of a polyhedron $\mathcal{Q}\subseteq\mathbb{R}^{d}$ is a
description

$\mathcal{Q}=\left\\{\mathbf{x}\in\mathbb{R}^{d}:\ \text{there exists
$\mathbf{y}\in\mathbb{R}^{k}$ such that}\
\mathbf{B}\mathbf{x}+\mathbf{C}\mathbf{y}\leq\mathbf{d}\right\\},$

where $\mathbf{B}\in\mathbb{R}^{\ell\times d}$,
$\mathbf{C}\in\mathbb{R}^{\ell\times k}$, and
$\mathbf{d}\in\mathbb{R}^{\ell}$. The number $\ell$ is called the size of the
extended formulation. The following is Conforti et. al’s result:

######  Theorem 1.1 (Theorem 1 in [9])

For every graph $G$ on $n$ nodes with $\operatorname{ocp}(G)\leq 1$, the
polytope $\operatorname{conv}(\mathcal{P}_{G}\cap\mathbb{Z}^{n})$ admits an
extended formulation of size in $O(n^{2})$. Moreover, this extended
formulation can be constructed in polynomial time.

Using the extended formulation presented in Theorem 1.1, one can solve the
corresponding ILP in polynomial time. Our work looks to build on this result.
We are guided by the following question:

Main Question: | Let $\mathbf{A}\in\mathbb{Z}^{m\times n}$ be bimodular with $\operatorname{rank}(\mathbf{A})=n$, let $\mathbf{b}\in\mathbb{Z}^{n}$,
---|---
| and define $\mathcal{P}$ as in (1). Under what conditions on $\mathbf{A}$
and $\mathbf{b}$
| does $\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ admit a compact
extended formulation?

Here, the term ‘compact’ is meant to indicate that that the size of the
extended formulation is bounded by a polynomial in the binary encoding size of
$\mathcal{P}$. The work in [16, 22] shows that a bimodular matrix can have at
most $m\leq n^{2}+3n$ distinct non-zero rows. Later on, we consider constraint
matrices whose rows form a cographic matroid; in this case, the number of
distinct non-zero rows is known to be linear in $n$; see [14] or [21, pg.
145]. Hence, we aim to find conditions when
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ admits an extended
formulation whose size is upper bounded by a polynomial in $n$ and possibly
the binary encoding sizes of the largest entries in $\mathbf{A}$ and
$\mathbf{b}$.

When exploring the main question, we observe that previous work by Cevallos et
al. [7] places limitations on what one can expect. In their work, they
consider so-called mixed-integer linear extended formulations (MILEFs), which
are extended formulations that allow for ‘integrality constraints’; see [7]
for a precise definition. One of their results is relevant for us:

######  Theorem 1.2 (Theorem 5.4 in [7])

There exists a constant $\gamma>0$ such that the following holds. For every
$n$, there is a bimodular integer program with $O(n^{2})$ variables such that
any MILEF of size at most $2^{\gamma n}$ for the convex hull of its [the
integer program’s] feasible points requires $\Omega(n/\log n)$ integrality
constraints.

In this manuscript, we do not allow for integrality constraints in our
extended formulations. Therefore, the important takeaway from Theorem 1.2 is
that some polyhedra $\mathcal{P}$ in $n$ variables defined by bimodular
constraint matrices are such that
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ does not admit a compact
extended formulation. We revisit their example later in order to provide
additional context for our result.

##  2 Results.

Mindful of Theorems 1.1 and 1.2, we aim to find new families of polyhedra
defined by bimodular constraint matrices for which there exist compact
extended formulations. Our main result places one condition on $\mathbf{b}$
and one condition on $\mathbf{A}$ (aside from being bimodular). For the
condition on $\mathbf{b}$, we require that $\mathbf{b}$ is in the column span
of $\mathbf{A}$, which we denote by $\operatorname{span}(\mathbf{A})$. For the
condition on $\mathbf{A}$, we look to the matroid represented by the rows of
$\mathbf{A}$. We write $M(\mathbf{A}^{\top})$ to denote the column matroid of
$\mathbf{A}^{\top}$, i.e., the row matroid of $\mathbf{A}$. Furthermore, we
say that $M(\mathbf{A}^{\top})$ is cographic if it is the dual of a graphic
matroid.

We can now state our main result.

###### Theorem 2.1

Let $\mathbf{A}\in\mathbb{Z}^{m\times n}$ have
$\operatorname{rank}(\mathbf{A})=n$ and let $\mathbf{b}\in\mathbb{Z}^{m}$.
Define $\mathcal{P}$ as in (1). Assume that  (i) $\mathbf{A}$is bimodular,
(ii) $M(\mathbf{A}^{\top})$is cographic,  (iii)
$\mathbf{b}\in\mathrm{span}(\mathbf{A})$.  Then
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ admits an extended
formulation of size in $O(n^{2})$ that can be constructed in polynomial time.

Our assumptions in Theorem 2.1 allow us to derive compact extended
formulations for new families of bimodular problems; see Section 4. Moreover,
using Theorem 2.1 and a structural lemma (Lemma 8 in [9]), we are able to
recover one of the results due to Conforti et al. To state their result,
define the odd cycle transversal number $\operatorname{oct}(G)$ of a graph
$G=(V,E)$ is the minimum cardinality of a set of nodes $X\subseteq V$ such
that $G-X$ is bipartite.

######  Corollary 1 (Follows from Theorem 2 and Theorem 14 in [9])

If $G$ is a $4$-connected graph on $n$ nodes with $\operatorname{ocp}(G)\leq
1$ and $\operatorname{oct}(G)\geq 4$, then the polytope
$\operatorname{conv}(\mathcal{P}_{G}\cap\mathbb{Z}^{n})$ admits an extended
formulation whose size is in $O(n^{2})$.

Assumptions  _(ii)_ and  _(iii)_ are inspired by the work in [9]; some of
their arguments appear in a more general form in [8]. Consequently, our proof
of Theorem 2.1 follows closely the proof of Theorem 1 in [9]. However, there
are steps that allow us to generalize parts of their work. For instance, in
their proof of Corollary 1, Conforti et al. use a characterization due to
Lovász stating that a $4$-connected graph $G$ with $\operatorname{ocp}(G)\leq
1$ and $\operatorname{oct}(G)\geq 4$ has an even-face embedding in the
projective plane; see [9, Theorem 2]. Via the lens of matroid theory, our
approach offers a direct algebraic proof to sidestep the complexities
introduced by the even-face embedding argument. Our proof of Corollary 1
follows from Theorem 2.1 via a result of Lovász (see Theorem 4.1) which shows
that the column matroid of the node-edge incidence matrix of $G$ is cographic
when $G$ is $4$-connected with $\operatorname{ocp}(G)\leq 1$ and
$\operatorname{oct}(G)\geq 4$; see Subsection 4.3 for more details.

Theorem 2.1 extends Corollary 1 in two directions. First, the corollary
applies only to a specific class of cographic bimodular matrices (i.e., the
matrix $\mathbf{A}^{\prime}$ in (2)), while Theorem 2.1 holds for all
bimodular cographic matrices. Second, the results in [9] apply only with
$\mathbf{b}=\mathbf{1}$, while Theorem 2.1 holds for any vector $\mathbf{b}$
in the column span of $\mathbf{A}$. It follows from a result of Slilaty (see
Lemma 1) that if $\mathbf{A}^{\top}$ represents a cographic matroid of a graph
$H$ and is also the node-edge incidence matrix of a graph, then $H$ is
projective-planar. Therefore, the following corollary of Theorem 2.1 gives a
new family of matrices for which the corresponding polytope has a polynomial-
size extended formulation; these results do not follow from work in [9]. We
discuss this in Section 4.

###### Corollary 2

Suppose $H$ is a graph that is not projective-planar and $\mathbf{A}^{\top}$
is a bimodular matrix with $\operatorname{rank}(\mathbf{A}^{\top})=n$ that
represents the cographic matroid of $H$. Let
$\mathbf{b}\in\mathrm{span}(\mathbf{A})$. Then the polytope
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ admits an extended
formulation whose size is in $O(n^{2})$.

Consider the following covered by Corollary 2. If $H$ is any non-projective-
planar graph, then the cographic matroid of $H$ has a representation as the
row matroid of a unimodular matrix $\mathbf{U}$. We can then apply any
bimodular column operations and row scalings to obtain a bimodular matrix
$\mathbf{A}$ so that $M(\mathbf{U}^{\top})=M(\mathbf{A}^{\top})$. In
particular, $M(\mathbf{A}^{\top})$ is cographic, and Corollary 2 applies to
$\mathbf{A}^{\top}$.

An open question is how to further generalize Theorem 2.1. The example by
Cevallos et al. [7] demonstrates that assumption  _(i)_ is not sufficient for
the existence of a compact extended formulation. Moreover, in their example
$M(\mathbf{A}^{\top})$ is graphic rather than cographic; see Section 4. Hence,
we cannot relax  _(iii)_ and expand  _(ii)_ to include graphic matroids.

The rest of the manuscript is outlined as follows. We provide some
preliminaries and notation on matroids; see Section 3. In Section 4, we
illustrate Theorem 2.1 by pointing to new families of bimodular-constrained
ILPs for which we have compact extended formulations. We also contrast our
result with the negative example of Cevallos et al., and we prove Corollary 1.
For the sake of presentation, in Section 5 we collect necessary lemmas to
prove Theorem 2.1. Finally, we prove Theorem 2.1 in Section 6.

##  3 Preliminaries and notation.

We use capital bold font to denote matrices, e.g., $\mathbf{A}$. For
$\mathbf{A}\in\mathbb{R}^{m\times n}$ and sets $I\subseteq\\{1,\dotsc,m\\}$
and $J\subseteq\\{1,\dotsc,n\\}$, we use
$\mathbf{A}_{I,J}\in\mathbb{R}^{|I|\times|J|}$ to denote the submatrix of
$\mathbf{A}$ with rows indexed by $I$ and columns indexed by $J$. If
$J=\\{1,\dotsc,n\\}$, then we write $\mathbf{A}_{I}:=\mathbf{A}_{I,J}$. If
$I=\\{i\\}$ and $J=\\{j\\}$ are singletons, then we write
$A_{i,j}:=\mathbf{A}_{I,J}$. We use lower case bold font for vectors, e.g.,
$\mathbf{x}$, and denote the $i$th entry of $\mathbf{x}$ by $x_{i}$. For
$I\subseteq\\{1,\dotsc,n\\}$ and $\mathbf{x}\in\mathbb{R}^{n}$, we write
$\mathbf{x}(I):=\sum_{i\in C}x_{i}$. We use $\mathbf{1}$ and $\mathbf{0}$ to
denote the matrix (or vector) of all-ones and all-zeros, respectively; the
dimensions of $\mathbf{1}$ and $\mathbf{0}$ are implied by context. We use
$\mathbf{I}_{r}$ to denote the $r\times r$ identity matrix. The $i$th standard
unit vector in $\mathbb{R}^{n}$ is denoted by $\mathbf{e}^{i}$. We use
$\mathbb{Z}_{+}$ and $\mathbb{R}_{+}$ to denote the set of non-negative
integers and real numbers, respectively.

Matroids were introduced independently by Nakasawa [19] and Whitney [29] as a
combinatorial abstraction of rank functions that arise in linear algebra. We
use standard notation in matroid theory. For more, we direct the reader to
[21]. A matroid is a pair $M=(E,r)$, where $E=E(M)$ is a finite ground set and
$r:2^{E}\to\mathbb{Z}$ is a rank function that is submodular and non-
decreasing. We write matroids, their ground sets, and elements within using
italic font. If $\mathbf{A}$ is a matrix over a field $\mathbb{F}$ with
columns indexed by $E$, then the function $r:2^{E}\to\mathbb{Z}$ defined by
$r(X):=\operatorname{rank}(\mathbf{A}[X])$ defines a matroid $M(\mathbf{A})$
on $E$ called the column matroid of $\mathbf{A}$, where $\mathbf{A}[X]$ is the
set of columns of $\mathbf{A}$ corresponding to $X$. We say that
$M(\mathbf{A})$ is $\mathbb{F}$-representable. If $\mathbf{A}$ is a signed
node-edge incidence matrix of a graph $H$, then $M(\mathbf{A})$ is also the
graphic matroid of $H$, denoted by $M(H)$. The rank function of $M(H)$ is
$r(X)=|V(H[X])|-c(H[X])$ for all sets $X$ of edges of $H$, where $c(H[X])$ is
the number of connected components of the subgraph $H[X]$. We refer to
$M(K_{r})$, the graphic matroid of the complete graph on $r$ vertices, as a
clique. The canonical representation of $M(K_{r})$ over any field is

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>cm}}2.84544pt\lx@intercol\hfil\mathbf{I}_{r-1}\hfil\hskip
4.26773pt&\mathbf{D}_{r-1}\hfil\hskip
2.84544pt\end{array}]\in\mathbb{Z}^{(r-1)\times((r-1)+\binom{r-1}{2})},$

where the columns of $\mathbf{D}_{r-1}$ are $\mathbf{e}^{i}-\mathbf{e}^{j}$
for all $1\leq i<j\leq r-1$. The dual of a matroid $M=(E,r)$ is the matroid
$M^{*}=(E,r^{*})$ where $r^{*}(X)=|X|-(r(E)-r(E-X))$ for all $X\subseteq E$.
If $M$ is the dual of a graphic matroid, then $M$ is cographic. The canonical
representation of $M^{*}(K_{r})$ over any field is
$[-\mathbf{D}_{r-1}^{\top}~{}\mathbf{I}_{\binom{r-1}{2}}].$

##  4 Discussion and examples.

In this section, we discuss on how Theorem 2.1 fits in with past results. In
Subsection 4.1 we identify a family of polyhedra that does not explicitly
appear in [9], yet meets the assumptions of Theorem 2.1; this is Corollary 2.
In Subsection 4.2 we discuss why the example in Cevallos et al. does not meet
the assumptions of Theorem 2.1. In Subsection 4.3, we prove Corollary 1.

###  4.1 Extended formulations for a new family of polyhedra.

In this section we apply our main result to bimodular matrices $\mathbf{A}$
for which $M(\mathbf{A}^{\top})$ is the cographic matroid of a graph $H$ that
is not projective-planar. It follows from results in [9] that if
$\mathbf{A}^{\top}$ is bimodular and is the node-edge incidence matrix of a
graph, and $M(\mathbf{A}^{\top})$ is cographic, then we can find a compact
extended formulation for $\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$.
Aligned with these assumptions, Slilaty proved that if $\mathbf{A}^{\top}$ is
the node-edge incidence matrix of a graph and is also the cographic matroid of
a $2$-connected graph $H$, then $H$ is projective planar:

######  Lemma 1 (Theorem 3, part 1, in [28])

If $H$ is a $2$-connected graph satisfying $M^{*}(H)=M(\Sigma)$ for some
signed graph $\Sigma$, then $H$ is projective-planar.

However, not all graphs are projective planar. For example, let
$\mathbf{A}^{\top}$ be any bimodular representation of the cographic matroid
of a complete graph $K_{r}$ with $r\geq 7$. In terms of the matrix, suppose
that $[\mathbf{I}_{6}~{}\mathbf{D}_{7}]$ is the matrix representing the
graphic matroid $K_{7}$. Then, for

$\mathbf{A}^{\top}=\mathbf{B}\left[\begin{array}[]{rr}-\mathbf{D}_{7}^{\top}&\mathbf{I}_{15}\end{array}\right],$

where $|\det\mathbf{B}|=2$, we have
$M(\mathbf{A}^{\top})=M([-\mathbf{D}_{7}^{\top}~{}\mathbf{I}_{15}])=M^{*}([\mathbf{I}_{6}~{}\mathbf{D}_{7}])=M^{*}(K_{7})$.
Using Corollary 2, there is a compact extended formulation for
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ for this constraint
matrix and suitable $\mathbf{b}$.

###  4.2 Comparing Theorem 2.1 to an example by Cevallos et al.

While our main result extends the work of Conforti et al. to all bimodular
cographic matroids, we cannot hope to extend it to include graphic matroids as
well. To illustrate this, we will use an example matrix $\mathbf{A}$ from the
paper of Cevallos et al. and show that $\mathbf{A}^{\top}$ is graphic. Let
$D=(V,A)$ be a complete directed graph on $n$ nodes, where $n$ is even, and
suppose $\mathbf{D}$ is the node-arc incidence matrix of $D$. Cevallos et al.
[7, Section 5.8] consider the polyhedron

$\displaystyle\mathcal{P}:=$
$\displaystyle\left\\{(\mathbf{x},\mathbf{y},z)\in\mathbb{R}^{A}_{+}\times\mathbb{R}^{V}\times\mathbb{R}:~{}\begin{array}[]{l}x_{(v,w)}\geq
y_{w}-y_{v}~{}~{}\forall~{}(v,w)\in A,\\\\[4.26773pt] \sum_{v\in
V}y_{v}=2z+1\end{array}\right\\}$ $\displaystyle=$
$\displaystyle\left\\{(\mathbf{x},\mathbf{y},z)\in\mathbb{R}^{A}\times\mathbb{R}^{V}\times\mathbb{R}:~{}\mathbf{A}\begin{bmatrix}\mathbf{x}\\\
\mathbf{y}\\\ z\end{bmatrix}\leq\left[\begin{array}[]{r}\mathbf{0}\\\
\mathbf{0}\\\ 1\\\ -1\end{array}\right]\right\\},$

where

$\mathbf{A}:=\left[\begin{array}[]{rrr}-\mathbf{I}_{A}&\mathbf{D}^{\top}&\mathbf{0}\\\
-\mathbf{I}_{A}&\mathbf{0}\phantom{{}^{\top}}&\mathbf{0}\\\
\mathbf{0}^{\top}&\mathbf{1}^{\top}&-2\\\
\mathbf{0}^{\top}&-\mathbf{1}^{\top}&2\\\ \end{array}\right].$

The coefficient matrix $\mathbf{A}$ is bimodular, and
$\mathbf{b}\in\operatorname{span}(\mathbf{A})$ because the sum of the columns
corresponding to $\mathbf{y}$ is
$(\mathbf{0}_{A},\mathbf{0}_{A},|V|,-|V|)^{\top}$. Cevallos et al. show
$\operatorname{conv}(\mathcal{P}\cap(\mathbb{Z}^{A}\times\mathbb{Z}^{V}\times\mathbb{Z}))$
does not have a compact extended formulation.

We briefly argue why $M(\mathbf{A}^{\top})$ is a graphic matroid. Note that
the last two rows of $\mathbf{A}$ are parallel. Since the class of graphic
matroids is closed under parallel extensions, we may delete the last row of
$\mathbf{A}$. The last row of the resulting matrix is not in span of the other
rows (it is a coloop of $M(\mathbf{A}^{\top})$). Since the class of graphic
matroids is closed under adding coloops (by adding vertices with degree $1$),
we may delete the last two rows of $\mathbf{A}$. Let $\mathbf{A}_{1}$ be the
resulting matrix. For each row of $\mathbf{A}_{1}$ with $3$ nonzero entries,
subtract the column with the first nonzero entry from the column with the
third nonzero entry. Since the second nonzero entry in each row of
$\mathbf{D}^{\top}$ is $-1$, the matrix $\mathbf{A}_{2}$ obtained from
$\mathbf{A}_{1}$ by performing this operation to each column of
$\mathbf{A}_{1}$ has at most two nonzero entries in each row, and each row
with two nonzero entries has a $1$ and a $-1$. Therefore, after scaling each
row by $-1$ we see that the transpose of the resulting matrix $\mathbf{A}_{3}$
is a column submatrix of $\mathbf{D}$. Hence, $M(\mathbf{A}_{3}^{\top})$ is
graphic. As column operations and row scaling do not change the row matroid,
it follows that $M(\mathbf{A}^{\top})$ is also graphic.

###  4.3 A proof of Corollary 1.

As in [9, Theorem 1], we apply the same result by Lovász on the
characterization of graphs without disjoint odd cycles. However, we restate
the theorem in Theorem 4.1 using the matroid language used in the original
proof of Theorem 6.7. The matroid properties enable us to bypass the even face
embedding argument. In [9], the even face embedding property is used to derive
a reformulation (Lemma 12 in [9]), whereas we present a more general approach
to reformulate (Lemma 6). Consequently, we use the cographic matroid property
to recover their result (Corollary 1) and demonstrate a more general result
(Theorem 2.1).

A matroid $M=(E,r)$ is 3-connected if there is no partition $(X,Y)$ of $E$
such that $|X|,|Y|\geq j$ and $r(X)+r(Y)-r(E)<j$ for some $j\in\\{1,2\\}$. A
matroid $M=(E,r)$ is internally 4-connected if it is 3-connected and
$\min\\{|X|,|Y|\\}=3$ for every partition $(X,Y)$ of $E$ such that
$|X|,|Y|\geq 3$ and $r(X)+r(Y)-r(E)<3$. Seymour [26] proved that if
$M=M(\mathbf{A})$ for a unimodular matrix $\mathbf{A}$ and $M$ is internally
4-connected, then $M$ is either graphic, cographic, or a specific $10$-element
matroid called $R_{10}$.

######  Theorem 4.1 (Lovász, cited in [26] Theorem 6.7, page 546-547)

Let $M$ be the column matroid of the node-edge incidence matrix of a graph $G$
such that $\mathrm{ocp}(G)\leq 1$. Then, $M$ is regular. Furthermore, if $M$
is also internally 4-connected, then

  1. (1)

if $M\cong R_{10}$, then $G\cong K_{5}$;

  2. (2)

if $M$ is graphic, then there exists a node $v$ such that $G-v$ is bipartite,
or there exists a circuits $\\{e,f,g\\}$ such that $G-\\{e,f,g\\}$ is
bipartite;

  3. (3)

if $M$ is cographic, then $G$ has an even-face embedding in the projective
plane.

We can then have the following corollary.

###### Corollary 3

Assume that $G=(V,E)$ is 4-connected with $\mathrm{oct}(G)\geq 4$ and
$\mathrm{ocp}(G)=1$. Let $\mathbf{A}^{\top}$ be the node-edge incidence matrix
of $G$. Then $M=M(\mathbf{A}^{\top})$ is cographic.

###### Proof

By Theorem 4.1 we know that $M$ is regular. It is straightforward, but
technical, to show that $M$ is internally 4-connected (in fact, we show that
$M$ is 4-connected).

###### Claim

$M$ is internally 4-connected.

  * Proof of Claim. Let $r$ be the rank function of $M$. For a subgraph $H$ of $G$ we write $c(H)$ and $b(H)$ for the number of components and bipartite components, respectively, of $H$. The matroid $M$ is a signed-graphic matroid with underlying graph $G$; we direct the reader to [21] for background information on signed-graphic matroids. For this proof we only need the fact that if $X$ is a set of edges of $G$, then $r(X)=|V(G[X])|-b(G[X])$, where $G[X]$ is the graph induced by $X$; see [28].

Suppose that $M$ is not internally 4-connected. Hence, there is a partition
$(X,Y)$ of $E$ such that $r(X)+r(Y)-r(E)<j$ and $|X|,|Y|\geq j$ for some
$j\in\\{1,2,3\\}$. Choose such a partition with $c(G[X])+c(G[Y])$ as small as
possible. Let $Z=V(G[X])\cap V(G[Y])$. We will argue that

every component of $G[X]$ or $G[Y]$ has a vertex that is not in $Z$. (3)

By symmetry, it suffices to prove this for $G[X]$. Note that each component of
$G[X]$ either has vertex set contained in $Z$ and at most three vertices, or
contains at least four vertices in $Z$, because $G$ is $4$-connected. The
graph $G$ has no triangles because $\operatorname{oct}(G)\geq 4$ and
$\operatorname{ocp}(G)=1$. Hence, each component of $G[X]$ with at most three
vertices and vertex set contained in $Z$ is a path with one or two edges.

As a first step towards proving (3), assume for the sake of contradiction that
every component of $G[X]$ has its vertex set contained in $Z$ and at most
three vertices. Under this assumption, we have $r(X)=|X|$. Also, the vertex of
$G[Y]$ is equal to the vertex set of $G$. Let $X^{\prime}\subseteq X$ be such
that $|X-X^{\prime}|=j$ (possibly $X^{\prime}=\varnothing$). We have

$r(X-X^{\prime})+r(Y\cup X^{\prime})-r(E)\leq
r(X)-|X^{\prime}|+r(Y)+|X^{\prime}|-r(E)<j,$ (4)

and $|X-X^{\prime}|,|Y\cup X^{\prime}|\geq j$. If $r(Y\cup X^{\prime})=r(E)$,
then

$r(X-X^{\prime})+r(Y\cup X^{\prime})-r(E)=|X-X^{\prime}|\geq j.$

However, this contradicts (4). Hence, $r(Y\cup X^{\prime})<r(E)$. Since
$G[Y\cup X^{\prime}]$ and $G$ have the same vertex set and $G$ is connected,
this means that $G[Y\cup X^{\prime}]$ has more components than $G$. Moreover,
because $|X-X^{\prime}|=j\leq 3$, this implies that $X-X^{\prime}$ is a set of
at most three edges whose deletion disconnects $G$. However, then $G$ has a
set of at most three vertices whose deletion disconnects $G$, which
contradicts that $G$ is 4-connected. Therefore, $G[X]$ has a component with
vertex set that is not completely contained in $Z$, and contains at least four
vertices in $Z$. Moreover, this component has at least five vertices, and
therefore has at least four edges. Denote this edge set by $X^{*}$. Thus,
$|X^{*}|\geq 4$.

As a final step towards proving (3), assume for the sake of contradiction that
$G[X]$ has a component with vertex set contained in $Z$ and at most three
vertices. Let $X^{\prime\prime}$ be the set of edges of this component. The
previous paragraph demonstrates that $G[X^{*}]$ is not this component.
Therefore $|X-X^{\prime\prime}|\geq|X^{*}|\geq 4$. Note that
$r(X-X^{\prime\prime})=r(X)-|X^{\prime\prime}|$ because each element of
$X^{\prime\prime}$ is a coloop of the matroid $M$ restricted to $X$. Consider
the partition $(X-X^{\prime\prime},Y\cup X^{\prime\prime})$ of $E$. We have

$r(X-X^{\prime\prime})+r(Y\cup X^{\prime\prime})-r(E)\leq
r(X)-|X^{\prime\prime}|+r(Y)+|X^{\prime\prime}|-r(E)<j.$

However, this contradicts the minimality of $c(G[X])+c(G[Y])$ because
$|X-X^{\prime\prime}|\geq 4>j$. Therefore, each component of $X$ has a vertex
that is not in $Z$, which completes the proof of the statement claimed in (3).

Claim (3) implies that $|Z|\geq 4\cdot c(G[X])$ because $G$ is $4$-connected.
By applying the same reasoning to $G[Y]$, we have $|Z|\geq 4\cdot c(G[Y])$.
Without loss of generality, we may assume that $c(G[X])\geq c(G[Y])$. The
graph $G$ has an odd cycle because $\operatorname{ocp}(G)=1$. Thus,
$r(E)=|V(G)|$ and

$r(E)=|V(G)|=|V(G[X])|+|V(G[Y])|-|Z|.$

Given that $j\leq 3$, we have

$\displaystyle 2$ $\displaystyle\geq r(X)+r(Y)-r(E)$
$\displaystyle=|Z|-b(G[X])-b(G[Y])$ $\displaystyle\geq 4\cdot
c(G[X])-b(G[X])-b(G[Y])$ $\displaystyle\geq\Big{(}3\cdot
c(G[X])-b(G[X])\Big{)}+\Big{(}c(G[Y])-b(G[Y])\Big{)}$ $\displaystyle\geq 2+0,$

which implies that equality holds throughout, and so
$c(G[X])=c(G[Y])=b(G[X])=b(G[Y])=1$, and $|Z|=4$. Therefore, $G[X]$ and $G[Y]$
are connected bipartite graphs that have four common vertices. Thus, every odd
cycle of $G$ contains two vertices in $Z$, which implies that
$\operatorname{oct}(G)\leq 3$, a contradiction. Consequently, $M$ is
internally 4-connected. $\diamond$

Following the claim, we see that outcome _(1)_ , _(2)_ , or _(3)_ from Theorem
4.1 holds. Outcomes _(1)_ and _(2)_ cannot hold because
$\operatorname{ocp}(G)\geq 4$, and so outcome _(3)_ holds, as desired. ∎

To recover Corollary 1, we use the following lemma from Conforti et al.

######  Lemma 2 (Lemma 8 in [9])

For every graph $G$ on $n$ nodes,
$\operatorname{STAB}(G)=\operatorname{conv}\\{\mathbf{x}\in\mathbb{Z}^{n}:\mathbf{A}\mathbf{x}\leq\mathbf{b}\\}\cap[0,1]^{n}$,
where $\mathbf{A}$ is the edge-node incidence matrix of $G$, and
$\mathbf{b}=\nicefrac{{1}}{{2}}\cdot\mathbf{A}\mathbf{1}$.

Consider the matrix $\mathbf{A}$ and vector $\mathbf{b}$ in Lemma 2. Assuming
$\operatorname{ocp}(G)=1$, we have that $\mathbf{A}$ is bimodular and
$\mathbf{b}\in\operatorname{span}(\mathbf{A})$. Hence, by Theorem 2.1, we know
that
$\operatorname{conv}\\{\mathbf{x}\in\mathbb{Z}^{n}:\mathbf{A}\mathbf{x}\leq\mathbf{b}\\}$
admits an extended formulation of size in $O(n^{2})$. With the lemma, we can
then obtain an extended formulation and recover Corollary 1. We re-emphasize
that the difference between this approach and Conforti et al. is the method of
finding an extended formulation for
$\operatorname{conv}\\{\mathbf{x}\in\mathbb{Z}^{n}:\mathbf{A}\mathbf{x}\leq\mathbf{b}\\}$.

##  5 Lemmas for Theorem 2.1.

In this section, we collect lemmas that we use in our proof of Theorem 2.1.
Throughout, we consider $\mathbf{A}\in\mathbb{Z}^{m\times n}$,
$\mathbf{b}\in\operatorname{span}(\mathbf{A})$, and $\mathcal{P}$ as in (1).

The first simple setting that we handle in Theorem 2.1 is when $\mathbf{b}$ is
an integer linear combination of the columns of $\mathbf{A}$. Here,
$\mathcal{P}$ is a translated cone and a compact extended formulation for
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$. The following simple
observation applies to all translated polyhedral cones with integral vertices
defined by $\Delta$-modular matrices, so we state it in generality.

###### Lemma 3

Let $\mathbf{A}\in\mathbb{Z}^{m\times n}$ be a $\Delta$-modular matrix with
$\operatorname{rank}(\mathbf{A})=n$. Assume there exists
$\overline{\mathbf{x}}\in\mathbb{Z}^{n}$ such that
$\mathbf{b}=\mathbf{A}\overline{\mathbf{x}}$. Then
$\mathcal{P}=\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ and the
number of facets of $\mathcal{P}$ is in $O(n^{2}\Delta^{2})$.

###### Proof

The assumptions $\operatorname{rank}(\mathbf{A})=n$ and
$\mathbf{b}=\mathbf{A}\overline{\mathbf{x}}$ for
$\overline{\mathbf{x}}\in\mathbb{Z}^{n}$ imply that $\mathcal{P}$ is a
translated rational cone with vertex $\overline{\mathbf{x}}\in\mathbb{Z}^{n}$.
The integer hull of a rational cone is the rational cone itself, so
$\mathcal{P}=\operatorname{conv}\left\\{\mathbf{x}\in\mathbb{Z}^{n}:~{}\mathbf{A}\mathbf{x}\leq\mathbf{b}\right\\}$.

The facets of $\mathcal{P}$ are defined by some subset of the inequalities
$\mathbf{A}\mathbf{x}\leq\mathbf{b}$ defined by distinct rows of $\mathbf{A}$.
It is known that the number of distinct rows of a $\operatorname{rank}$-$n$
$\Delta$-modular matrix is polynomial in $n$ and $\Delta$, e.g., [16, Theorem
2] shows that the number of distinct rows is in $O(n^{2}\Delta^{2})$. ∎

The remaining lemmas address the setting when $\mathbf{b}$ is not an integer
linear combination of the columns of $\mathbf{A}$. As in Conforti et al., we
consider an affine transformation of
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ into the space of slack
variables. Here, we define

$\mathcal{Q}(\mathbf{A},\mathbf{b}):=\operatorname{conv}\left\\{\mathbf{b}-\mathbf{A}\mathbf{x}\in\mathbb{Z}_{+}^{m}:~{}\mathbf{x}\in\mathbb{Z}^{n}\right\\}.$

###### Lemma 4

Let $\mathbf{A}\in\mathbb{Z}^{m\times n}$ have
$\operatorname{rank}(\mathbf{A})=n$ and
$\mathbf{b}\in\mathbb{Z}^{m}\cap\operatorname{span}(\mathbf{A})$. Then

$\mathcal{Q}(\mathbf{A},\mathbf{b})=\\{\mathbf{b}-\mathbf{A}\mathbf{x}:\mathbf{x}\in\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})\\}.$

Moreover, for any unimodular matrix $\mathbf{U}\in\mathbb{Z}^{n\times n}$
(i.e., $|\det\mathbf{U}|=1$), we have

$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})=\big{\\{}\mathbf{U}\mathbf{x}:~{}\mathbf{x}\in\operatorname{conv}\\{\mathbf{w}\in\mathbb{Z}^{n}:\mathbf{A}\mathbf{U}\mathbf{w}\leq\mathbf{b})\\}\big{\\}}.$

###### Proof

The first equation follows from the definitions of
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ and
$\mathcal{Q}(\mathbf{A},\mathbf{b})$, and the fact that the convex hull
operation commutes with affine maps. The second equation follows from the fact
$\mathbf{U}\cdot\mathbb{Z}^{n}=\mathbb{Z}^{n}$ for any unimodular matrix
$\mathbf{U}$. ∎

Lemma 6 will assist in our affine transformation. To prove this lemma, we use
the following result that can be found in [2].

######  Lemma 5 (Lemma 3.3 in [2])

Let $\mathbf{B}\in\mathbb{Z}^{n\times n}$ satisfy $|\det\mathbf{B}|=2$. Then,
$\mathbf{B}^{-1}$ has the following structure: There exists a nonempty set of
row indices $I\subseteq\\{1,\dotsc,n\\}$ and a nonempty set of column indices
$J\subseteq\\{1,\dotsc,n\\}$ such that
$B^{-1}_{i,j}\in\nicefrac{{1}}{{2}}+\mathbb{Z}$ for all $(i,j)\in I\times J$
and $B^{-1}_{i,j}\in\mathbb{Z}$ for all $(i,j)\not\in I\times J$.

The assumptions of Lemma 6 will be satisfied in the proof of Theorem 2.1 after
applying a suitable unimodular transformation, and possibly rearranging
columns and rows.

###### Lemma 6

Let $\mathbf{A}\in\mathbb{Z}^{m\times n}$ be a bimodular matrix of the form

$\mathbf{A}=\begin{bmatrix}\mathbf{A}_{B}\\\ \mathbf{A}_{N}\end{bmatrix}$

where $B:=\\{1,\dotsc,n\\}$ satisfies $|\det\mathbf{A}_{B}|=2$ and
$N:=\\{1,\dotsc,m\\}\setminus B$. Let $I\subseteq\\{1,\dotsc,m\\}$ and
$J\subseteq B$ be the sets of indices obtained by applying Lemma 5 to
$\mathbf{A}_{B}$. Furthermore, assume

<EMAIL_ADDRESS>cm}c}\mathbf{A}_{J,J}\hfil\hskip 7.11317pt&\mathbf{0}\\\
\mathbf{A}_{B\setminus J,J}\hfil\hskip 7.11317pt&\mathbf{A}_{B\setminus
J,B\setminus J}\end{array}\right],$

and assume
$\nicefrac{{1}}{{2}}\cdot\mathbf{1}^{\top}\mathbf{A}_{J,J}\in\mathbb{Z}^{|J|}$.
Let $\mathbf{b}\in\mathbb{Z}^{m}\cap\operatorname{span}(\mathbf{A})$. Then

$\mathcal{Q}(\mathbf{A},\mathbf{b})=\operatorname{conv}\left\\{\mathbf{y}\in\mathbb{Z}_{+}^{m}:\begin{array}[]{r}\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}(\mathbf{y}-\mathbf{b})=\mathbf{0}\\\\[4.26773pt]
\text{and}~{}\mathbf{y}(J)\equiv\mathbf{b}(J)\mod 2\end{array}\right\\}.$ (5)

###### Proof

Let $\mathcal{R}(\mathbf{A},\mathbf{b})$ denote the set generating the convex
hull in the right hand side of Equation (5).

To show
$\mathcal{Q}(\mathbf{A},\mathbf{b})\subseteq\operatorname{conv}(\mathcal{R}(\mathbf{A},\mathbf{b}))$,
let
$\mathbf{y}\in\\{\mathbf{b}-\mathbf{A}\mathbf{x}\in\mathbb{Z}_{+}^{m}:~{}\mathbf{x}\in\mathbb{Z}^{n}\\}$.
Suppose $\mathbf{x}\in\mathbb{Z}^{n}$ is such that
$\mathbf{y}:=\mathbf{b}-\mathbf{A}\mathbf{x}\geq\mathbf{0}$. We have

$\textstyle\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}(\mathbf{y}-\mathbf{b})=\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}\left(-\begin{bmatrix}\mathbf{A}_{B}\\\
\mathbf{A}_{N}\end{bmatrix}\mathbf{x}\right)=\mathbf{0}.$

Using the assumption that
$\nicefrac{{1}}{{2}}\cdot\mathbf{1}^{\top}\mathbf{A}_{J,J}\in\mathbb{Z}^{|J|}$,
we see that

$\textstyle\mathbf{y}(J)-\mathbf{b}(J)=-\mathbf{1}^{\top}\mathbf{A}_{J,J}\mathbf{x}_{J}=-2\left(\nicefrac{{1}}{{2}}\cdot\mathbf{1}^{\top}\mathbf{A}_{J,J}\right)\mathbf{x}_{J}\equiv
0\mod 2.$

Thus, $\mathbf{y}\in\mathcal{R}(\mathbf{A},\mathbf{b})$. Therefore,
$\mathcal{Q}(\mathbf{A},\mathbf{b})\subseteq\operatorname{conv}(\mathcal{R}(\mathbf{A},\mathbf{b}))$.

To prove
$\operatorname{conv}(\mathcal{R}(\mathbf{A},\mathbf{b}))\subseteq\mathcal{Q}(\mathbf{A},\mathbf{b})$,
let $\mathbf{y}\in\mathcal{R}(\mathbf{A},\mathbf{b})$. Set
$\mathbf{x}:=\mathbf{A}_{B}^{-1}(\mathbf{b}_{B}-\mathbf{y}_{B})$. Hence,
$\mathbf{b}_{B}-\mathbf{A}_{B}\mathbf{x}=\mathbf{y}_{B}\geq 0$. Using
$\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}(\mathbf{y}-\mathbf{b})=\mathbf{0}$,
we have

$\mathbf{b}_{N}-\mathbf{A}_{N}\mathbf{x}=\mathbf{b}_{N}+\mathbf{A}_{N}\mathbf{A}_{B}^{-1}(\mathbf{y}_{B}-\mathbf{b}_{B})=\mathbf{y}_{N}\geq\mathbf{0}.$

It suffices to check that $\mathbf{x}\in\mathbb{Z}^{n}$. Let $i\in I$.
According to Lemma 5, we have $A^{-1}_{i,j}\in\nicefrac{{1}}{{2}}+\mathbb{Z}$
for each $j\in J$ and $A^{-1}_{i,j}\in\mathbb{Z}$ for each $j\not\in J$. Using
this, along with $\mathbf{y}(J)\equiv\mathbf{b}(J)\mod 2$, we see that

$\begin{array}[]{rcl}x_{i}&=&\sum_{j\in
J}{A}^{-1}_{i,j}(b_{i}-y_{i})+\sum_{j\not\in
J}{A}^{-1}_{i,j}(b_{i}-y_{i})\\\\[2.84544pt]
&=&\nicefrac{{1}}{{2}}\cdot(\mathbf{b}(J)-\mathbf{y}(J))+\sum_{j\in
J}({A}^{-1}_{i,j}-\nicefrac{{1}}{{2}})(b_{i}-y_{i})+\sum_{j\not\in
J}{A}^{-1}_{i,j}(b_{i}-y_{i})\in\mathbb{Z}.\end{array}$

Let $i\notin I$. We have $x_{i}\in\mathbb{Z}$ because
$(\mathbf{A}_{B}^{-1})_{i,j}\in\mathbb{Z}$ and $y_{j}-b_{j}\in\mathbb{Z}$ for
all $j\in\\{1,\dotsc,n\\}$. Thus, $\mathbf{x}\in\mathbb{Z}^{n}$. Therefore,
$\operatorname{conv}(\mathcal{R}(\mathbf{A},\mathbf{b}))\subseteq\mathcal{Q}(\mathbf{A},\mathbf{b})$.
∎

The following results can be found in [21]. For
$\mathbf{X}\in\mathbb{R}^{p\times q}$, we use
$\mathbf{X}^{\\#}\in\\{0,1\\}^{p\times q}$ to denote the matrix obtained from
$\mathbf{X}$ by replacing every non-zero entry by a one. The following two
lemmas are used to prove that the cographic matroid with special bimodular
matrix representation has an equivalent node-arc incidence matrix
representation up to only row operations.

######  Lemma 7 (Proposition 6.4.1 in [21])

Let $[\mathbf{I}_{r}~{}\mathbf{D}_{1}]$ and
$[\mathbf{I}_{r}~{}\mathbf{D}_{2}]$ be matrices over fields $\mathbb{F}_{1}$
and $\mathbb{F}_{2}$, respectively, with the columns of each labelled, in
order, by $\mathbf{f}_{1},\dotsc,\mathbf{f}_{t}$. If the identity map on
$\\{\mathbf{f}_{1},\dotsc,\mathbf{f}_{t}\\}$ is an is an isomorphism from
$M([\mathbf{I}_{r}~{}\mathbf{D}_{1}])$ to
$M([\mathbf{I}_{r}~{}\mathbf{D}_{2}])$, then
$\mathbf{D}_{1}^{\\#}=\mathbf{D}_{2}^{\\#}$.

The following lemma originally appeared in [5].

######  Lemma 8 (Lemma 10.1.7 in [21])

Let $\mathbf{D}_{1}$ and $\mathbf{D}_{2}$ be totally unimodular matrices. If
$\mathbf{D}_{1}^{\\#}=\mathbf{D}_{2}^{\\#}$, then $\mathbf{D}_{2}$ can be
obtained from $\mathbf{D}_{1}$ by multiplying some rows and columns by $-1$.

Our main contribution in Theorem 2.1 is to show that a more general polyhedron
can be reformulated into the convex hull of nonnegative integer circulations
with a parity constraint. The following lemma from [9] shows that the
reformulation has a compact extended formulation.

######  Lemma 9 (Lemma 13 in [9])

Let $\mathbf{D}$ be the node-arc incidence matrix of a directed graph
$H=(V,A)$, and let $X\subseteq A$. Then the convex hull of nonnegative integer
circulations $\mathbf{y}$ in $H$ with $\mathbf{y}(X)$ odd, i.e., the set

$\operatorname{conv}\left\\{\mathbf{y}\in\mathbb{Z}_{+}^{A}:~{}\mathbf{D}\mathbf{y}=\mathbf{0},~{}\mathbf{y}(X)\equiv
1\mod 2\right\\}.$

admits an extended formuation of size in $O(|V|\cdot|A|)$.

##  6 A proof of Theorem 2.1.

Let $\mathbf{A}\in\mathbb{Z}^{m\times n}$ be bimodular with
$\operatorname{rank}(\mathbf{A})=n$ and let $\mathbf{b}\in\mathbb{Z}^{m}$.
Define $\mathcal{P}$ as in (1). Let $\overline{\mathbf{x}}\in\mathbb{R}^{n}$
be such that $\mathbf{A}\overline{\mathbf{x}}=\mathbf{b}$. If there exists an
$n\times n$ submatrix $\mathbf{B}$ of $\mathbf{A}$ with $|\det\mathbf{B}|=1$,
then $\overline{\mathbf{x}}\in\mathbb{Z}^{n}$. Thus, by Lemma 3,
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ has a compact extended
formulation of size in $O(n^{2})$.

For the remainder of the proof, assume that there is no $n\times n$ submatrix
$\mathbf{B}$ of $\mathbf{A}$ with $|\det\mathbf{B}|=1$. Hence, as $\mathbf{A}$
is bimodular, we have that every $n\times n$ submatrix $\mathbf{B}$ of
$\mathbf{A}$ satisfies $|\det\mathbf{B}|\in\\{0,2\\}$. Finding a set
$B\subseteq\\{1,\dotsc,m\\}$ such that $|\det\mathbf{A}_{B}|=2$ can be done in
polynomial time, e.g., through Gaussian elimination. After finding such a set
$B$, by Lemma 4, we can apply a unimodular transformation on the columns of
$\mathbf{A}$, e.g., Hermite Normal Form transformation, and reorder rows and
columns of $\mathbf{A}$ to assume that
$\mathbf{A}=\begin{bmatrix}\mathbf{A}_{B}\\\ \mathbf{A}_{N}\end{bmatrix}$, and
for some $C\subseteq B$, we have

$\mathbf{A}_{B}=\begin{bmatrix}\mathbf{A}_{C}&\mathbf{0}\\\
\mathbf{0}&\mathbf{I}_{n-|C|}\end{bmatrix},\quad\text{where}\quad\mathbf{A}_{C}=\begin{bmatrix}\mathbf{I}_{|C|-1}&0\\\\[2.84544pt]
\mathbf{1}^{\top}&2\end{bmatrix}.$

Consequently, every entry in the $|C|$-th column of $\mathbf{A}_{N}$ is either
0 or $\pm 2$, i.e., $\mathbf{A}\mathbf{A}_{B}^{-1}$ is a totally unimodular
matrix. Otherwise, we could construct an $n\times n$ submatrix of $\mathbf{A}$
whose determinant is not in $\\{0,\pm 2\\}$.

We consider two cases depending on the parity of $\mathbf{b}(C)$. For the
first case, assume $\mathbf{b}(C)$ is even. Because
$\mathbf{b}_{B}=\mathbf{A}_{B}\overline{\mathbf{x}}\in\mathbb{Z}^{n}$, we know
that $\overline{\mathbf{x}}\in\mathbb{Z}^{n}$ or
$\overline{\mathbf{x}}\in\nicefrac{{1}}{{2}}\cdot\mathbf{e}^{|C|}+\mathbb{Z}^{n}$.
If
$\overline{\mathbf{x}}\in\nicefrac{{1}}{{2}}\cdot\mathbf{e}^{|C|}+\mathbb{Z}^{n}$,
then
$\mathbf{b}(C)=\mathbf{1}^{\top}\mathbf{A}_{C}\overline{\mathbf{x}}_{C}\equiv
1\mod 2$, which is a contradiction. Thus,
$\overline{\mathbf{x}}\in\mathbb{Z}^{n}$. Therefore, there is a compact
extended formulation of $\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$
of size in $O(n^{2})$ according to Lemma 3.

For the second case, assume $\mathbf{b}(C)$ is odd. Lemma 4 states that
$\mathcal{Q}(\mathbf{A},\mathbf{b})$ and
$\operatorname{conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ are affinely equivalent.
Thus, we only need to show that $\mathcal{Q}(\mathbf{A},\mathbf{b})$ has a
compact extended formulation. By Lemma 6 and the fact $\mathbf{b}(C)\equiv
1\mod 2$, we know that

$\mathcal{Q}(\mathbf{A},\mathbf{b})=\operatorname{conv}\left\\{\mathbf{y}\in\mathbb{Z}_{+}^{m}:\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}\mathbf{y}=\mathbf{0}~{}\text{and}~{}\mathbf{y}(C)\equiv
1\mod 2\right\\}.$

Furthermore, the matroid $M^{*}$ represented by
$\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}$
is graphic because $M$ is cographic.

We claim that there exists a node-arc incidence matrix $\mathbf{D}\in\\{0,\pm
1\\}^{(m-n+1)\times m}$ such that

$\mathcal{Q}(\mathbf{A},\mathbf{b})=\operatorname{conv}\left\\{\mathbf{y}\in\mathbb{Z}_{+}^{m}:~{}\mathbf{D}\mathbf{y}=\mathbf{0},~{}\mathbf{y}(C)\equiv
1\mod 2\right\\}.$

Lemma 9 will then imply that $\mathcal{Q}(\mathbf{A},\mathbf{b})$ has a
compact extended formulation of size in $O((m-n+1)m)$. We have $m\in O(n)$
because $M$ is cographic [21, pg. 145]. Thus, the size of the extended
formulation is in $O((m-n+1)m)\subseteq O(n^{2})$. To prove the claim, it
suffices to argue that there exists such a $\mathbf{D}$, for which given
$\mathbf{y}\in\mathbb{R}^{m}$, we have $\mathbf{D}\mathbf{y}=\mathbf{0}$ if
and only if
$\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}\mathbf{y}=\mathbf{0}$.

Let $H$ be a graph such that
$M^{*}=M(H)=M([-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}])$. We
can assume that $M(H)=M(\mathbf{E})$, where $\mathbf{E}$ can be obtained in
polynomial time [4, page 326] and

$\begin{bmatrix}\mathbf{E}\\\
-\mathbf{1}^{\top}\mathbf{E}\end{bmatrix}\in\\{0,\pm 1\\}^{(m-n+1)\times m}$

is the node-arc incidence matrix of $H$ with arbitrary orientation. The row
sum of a node-arc incidence matrix is $\mathbf{0}$, so the last row is
$-\mathbf{1}^{\top}\mathbf{E}$.

Suppose $\mathbf{E}=[\mathbf{E}_{1}~{}\mathbf{E}_{2}]$, where
$\mathbf{E}_{2}\in\mathbb{Z}^{(m-n)\times(m-n)}$. The matrix $\mathbf{E}_{2}$
is invertible because the last $m-n$ columns of $M^{*}$ form a basis. Hence,
$[\mathbf{E}_{2}^{-1}\mathbf{E}_{1}~{}\mathbf{I}_{m-n}]$ is a TU matrix
representing the same matroid $M^{*}$. By Lemma 7,
$(\mathbf{E}_{2}^{-1}\mathbf{E}_{1})^{\\#}=(-\mathbf{A}_{N}\mathbf{A}_{B}^{-1})^{\\#}$.
Thus, by Lemma 8, the matrix $\mathbf{E}_{2}^{-1}\mathbf{E}_{1}$ can be
obtained from $-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}$ by multiplying some rows
and columns by $-1$, say
$\mathbf{P}_{1}(-\mathbf{A}_{N}\mathbf{A}_{B}^{-1})\mathbf{P}_{2}=\mathbf{E}_{2}^{-1}\mathbf{E}_{1}$,
where $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ are diagonal matrices with entries
in $\\{-1,1\\}$. Consider the node-arc incidence matrix

$\mathbf{D}:=\begin{bmatrix}\mathbf{E}\\\
-\mathbf{1}^{\top}\mathbf{E}\end{bmatrix}\left[\begin{array}[]{ll}\mathbf{P}_{2}^{-1}&\mathbf{0}\\\
\mathbf{0}&\mathbf{P}_{1}\end{array}\right].$

For $\mathbf{y}\in\mathbb{R}^{m}$, we have $\mathbf{D}\mathbf{y}=\mathbf{0}$
if and only if
$\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}\mathbf{y}=\mathbf{0}$
because

$\mathbf{E}\left[\begin{array}[]{ll}\mathbf{P}_{2}^{-1}&\mathbf{0}\\\
\mathbf{0}&\mathbf{P}_{1}\end{array}\right]=\begin{bmatrix}\mathbf{E}_{1}\mathbf{P}_{2}^{-1}~{}\mathbf{E}_{2}\mathbf{P}_{1}\end{bmatrix}=\mathbf{E}_{2}\mathbf{P}_{1}\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}.$
∎

Compared to [9], the extra steps to recognize the structure in Lemma 6 and
find the node-arc incidence matrix $\mathbf{D}$ can be done in polynomial
time. Thus, the extended formulation in Theorem 2.1 can be constructed in
polynomial time.

##  7 Future Directions

There are a few directions of future work that we find interesting.

  1. 1.

Theorem 2.1 requires that $\mathbf{b}\in\operatorname{span}(\mathbf{A})$. A
natural generalization is whether the result holds for general
$\mathbf{b}\in\mathbb{Z}^{m}$. To this end, one related question is to study
for $X\subseteq\\{1,\dotsc,m\\}$ the extended formulation for

$\mathcal{Q}(\mathbf{A},\mathbf{b})=\operatorname{conv}\left\\{\mathbf{y}\in\mathbb{Z}_{+}^{m}:\begin{array}[]{l}\begin{bmatrix}-\mathbf{A}_{N}\mathbf{A}_{B}^{-1}~{}\mathbf{I}_{m-n}\end{bmatrix}(\mathbf{y}-\mathbf{b})=0,\\\\[4.26773pt]
(\mathbf{y}-\mathbf{b})(X)\equiv 0\mod 2\end{array}\right\\}.$

  2. 2.

It is also natural to ask the main question for when $M(\mathbf{A}^{\top})$ is
cographic and $\mathbf{A}$ is $\Delta$-modular. Here, the main challenge will
be some method to generalize Lemma 5 to obtain an equivalent formulation as in
Lemma 6.

  3. 3.

This paper has not yet provided a complete characterization of the main
question that motivated our research. Indeed, the distinction between positive
and negative examples remains to be bridged. It is worth exploring other kinds
of matroid represented by bimodular matrices in more detail. This could
include matroids with a 2-separation, a 3-separation with a triangle, or a
triad. This study may also require possible generalizations of the other cases
in [9].

  4. 4.

To the best of our knowledge, the question whether a bimodular matrix can be
recognized in polynomial time remains open. On the other hand, it is possible
to do so for cographic matroids in polynomial time. Therefore, perhaps it is
possible to determine whether a bimodular matrix satisfying the conditions of
Theorem 2.1 can be recognized in polynomial time.

Acknowledgements. J. Paat was supported by a Natural Sciences and Engineering
Research Council of Canada Discovery Grant [RGPIN-2021-02475].

## References

  * [1] Artmann, S., Eisenbrand, F., Glanzer, C., Oertel, T., Vempala, S., Weismantel, R.: A note on non-degenerate integer programs with small sub-determinants. Operations Research Letters 44(5), 635–639 (2016)
  * [2] Artmann, S., Weismantel, R., Zenklusen, R.: A strongly polynomial algorithm for bimodular integer linear programming. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. pp. 1206–1219 (2017)
  * [3] Averkov, G., Schymura, M.: On the maximal number of columns of a $\Delta$-modular matrix. In: Aardal, K., L. Sanità, L. (eds.) Integer Programming and Combinatorial Optimization. pp. 29–42. Springer International Publishing, Cham (2022)
  * [4] Bixby, R.E., Cunningham, W.H.: Converting linear programs to network problems. Mathematics of Operations Research 5(3), 321–357 (1980)
  * [5] Camion, P.: Caractérisation des matrices unimodulaires. Cahiers Centre Études Rech. Opér. 5, 181–190 (1963)
  * [6] Celaya, M., Kuhlmann, S., Paat, J., Weismantel, R.: Improving the Cook et al. proximity bound given integral valued constraints. Proceedings of Integer Programming and Combinatorial Optimization (IPCO) (2022)
  * [7] Cevallos, A., Weltge, S., Zenklusen, R.: Lifting linear extension complexity bounds to the mixed-integer setting. Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms pp. 788 – 807 (2018)
  * [8] Conforti, M., Fiorini, S., Huynh, T., Joret, G., Weltge, S.: The stable set problem in graphs with bounded genus and bounded odd cycle packing number. In: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). p. 2896–2915. Society for Industrial and Applied Mathematics, USA (2020)
  * [9] Conforti, M., Fiorini, S., Huynh, T., Weltge, S.: Extended formulations for stable set polytopes of graphs without two disjoint odd cycles. Mathematical Programming 192(1), 547–566 (2022)
  * [10] Fiorini, S., Joret, G., Weltge, S., Yuditsky, Y.: Integer programs with bounded subdeterminants and two nonzeros per row. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). pp. 13–24 (2022)
  * [11] Glanzer, C., Weismantel, R., Zenklusen, R.: On the number of distinct rows of a matrix with bounded subdeterminants. SIAM Journal on Discrete Mathematics 32(3), 1706–1720 (2018)
  * [12] Gribanov, D., Shumilov, I., Malyshev, D., Pardalos, P.: On $\delta$-modular integer linear problems in the canonical form and equivalent problems. Journal of Global Optimization pp. 1–61 (2022)
  * [13] Grossman, J., Kulkarni, D., Schochetman, I.: On the minors of an incidence matrix and its Smith normal form. Linear Algebra and its Applications 218, 213–224 (1995)
  * [14] Jaeger, F.: Flows and generalized coloring theorems in graphs. Journal of Combinatorial Theory, Series B 26(2), 205–216 (1979)
  * [15] Lee, J., Paat, J., Stallknecht, I., Xu, L.: Improving Proximity Bounds Using Sparsity. In: Baïou, M., Gendron, B., Günlük, O., Mahjoub, A. (eds.) Combinatorial Optimization. pp. 115–127. Springer International Publishing, Cham (2020)
  * [16] Lee, J., Paat, J., Stallknecht, I., Xu, L.: Polynomial upper bounds on the number of differing columns of $\Delta$-modular integer programs. Mathematics of Operations Research (2022)
  * [17] Lenstra, H.: Integer programming with a fixed number of variables. Mathematics of Operations Research 8, 538 – 548 (1983)
  * [18] Nägele, M., Nöbel, C., Santiago, R., Zenklusen, R.: Advances on Strictly $\Delta$-Modular IPs. In: Del Pia, A., Kaibel, V. (eds.) Integer Programming and Combinatorial Optimization. pp. 393–407. Springer International Publishing (2023)
  * [19] Nakasawa, T.: Zur axiomatik der linearen abhängigkeit. i. Sci. Rep. Tokyo Bunrika Daigaku Sect. A 2, 129–149 (1935)
  * [20] Nägele, M., Santiago, R., Zenklusen, R.: Congruency-constrained TU problems beyond the bimodular case. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2743–2790 (2022)
  * [21] Oxley, J.: Matroid Theory. Oxford University Press, 2 edn. (Feb 2011)
  * [22] Oxley, J., Walsh, Z.: 2-modular matrices. SIAM Journal on Discrete Mathematics 36(2), 1231–1248 (2022)
  * [23] Paat, J., Schlöter, M., Weismantel, R.: The integrality number of an integer program. Mathematical Programming 192, 271–291 (2022)
  * [24] Paat, J., Stallknecht, I., Walsh, Z., Xu, L.: On the column number and forbidden submatrices for $\Delta$-modular matrices. To appear in SIAM Journal on Discrete Mathematics (2023)
  * [25] Schrijver, A.: Theory of linear and integer programming. John Wiley & Sons, Inc. New York, NY (1986)
  * [26] Seymour, P.: Matroid minors, Handbook of Combinatorics, vol. 1. North-Holland (Elsevier), Amsterdam (1995)
  * [27] Seymour, P.: Decomposition of regular matroids. Journal of Combinatorial Theory B 28, 305–359 (1980)
  * [28] Slilaty, D.C.: On cographic matroids and signed-graphic matroids. Discrete Mathematics 301(2), 207–217 (2005)
  * [29] Whitney, H.: On the abstract properties of linear dependence. American Journal of Mathematics 57, 63–87 (1935)