# Hard Problems In Box-Totally Dual Integral Polyhedra

Patrick Chervet, Roland Grappe, Mathieu Lacroix, Francesco Pisanu, Roberto
Wolfler Calvo

<figure><img src="image_1.png" /></figure>

## To cite this version:

Patrick Chervet, Roland Grappe, Mathieu Lacroix, Francesco Pisanu, Roberto Wolfler Calvo. Hard Problems In Box-Totally Dual Integral Polyhedra. 2023. hal-03932335

HAL Id: hal-03932335

https://hal.science/hal-03932335

Preprint submitted on 23 Jan 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Hard Problems In Box-Totally Dual Integral Polyhedra*

Patrick Chervet<fnref n="1" />, Roland Grappe<fnref n="2" />[0000-0002-7093-2175], Mathieu Lacroix<fnref n="2" />[0000-0001-8385-3890], Francesco Pisanu<fnref n="2" />[0000-0003-0799-5760], and Roberto Wolfler Calvo<fnref n="2" />[0000-0002-5459-5797]

**Abstract.** In this paper, we study the complexity of some fundamental questions regarding box-totally dual integral (box-TDI) polyhedra. First, although box-TDI polyhedra have strong integrality properties, we prove that Integer Programming over box-TDI polyhedra is NP-complete, that is, finding an integer point optimizing a linear function over a box-TDI polyhedron is hard. Second, we complement the result of Ding et al. [10] who proved that deciding whether a given system is box-TDI is co-NP-complete: we prove that recognizing whether a polyhedron is box-TDI is co-NP-complete.

To derive these complexity results, we exhibit new classes of totally equimodular matrices — a generalization of totally unimodular matrices — by characterizing the total equimodularity of incidence matrices of graphs.

**Keywords:** Box-TDI polyhedron · Totally equimodular matrix · Incidence matrix

## 1 Introduction

Totally dual integral systems were introduced in the late 70's and are strongly connected to min-max relations in combinatorial optimization [23]. A rational system of linear inequalities $Ax \le b$ is totally dual integral (TDI) if the minimization problem in the linear programming duality relation:

$$ \max\{c^\top x: Ax \le b\} = \min\{b^\top y: A^\top y = c, y \ge 0\} $$

admits an integer optimal solution for each integer vector $c$ such that the maximum is finite. Such systems describe integer polyhedra when $b$ is integer [13].

A stronger property is the box-total dual integrality, where a system $Ax \le b$ is box-totally dual integral (box-TDI) if $Ax \le b, \ell \le x \le u$ is TDI for all rational

<footnote n="1">¹ Lycée Olympe de Gouges, rue de Montreuil à Claye, 93130, Noisy le Sec, France.</footnote>

<footnote n="2">² Université Sorbonne Paris Nord, LIPN, CNRS UMR 7030, F-93430, Villetaneuse, France.</footnote>

<footnote>`{grappe,lacroix,pisanu,wolfler}@lipn.fr`</footnote>

<footnote>* This work has been partially supported by the PGMO project Matrices Totalement Équimodulaires.</footnote>
vectors $\ell$ and $u$ (with possible infinite components). General properties of such
systems can be found in Cook [6] and Chapter 22.4 of Schrijver [23].

Box-TDI systems characterize totally unimodular matrices. A matrix is *total-
ly unimodular (TU)* if every subset of linearly independent rows forms a unimo-
dular matrix, a matrix being *unimodular* if it has full row rank and all its nonzero
maximal minors have value $\pm 1$. A matrix $A$ is TU if and only if the system $Ax \le b$
is box-TDI for each rational vector $b$ [23, Page 318].

Until recently, the vast majority of known box-TDI systems were systems
associated with TU matrices. For instance, König's Theorem [21] can be seen as
a consequence of the fact that the vertex-edge incidence matrix of a graph is TU
if and only if the graph is bipartite [17].

In the last two decades, several new box-TDI systems were exhibited. Chen,
Ding, and Zang [10] characterized box-Mengerian matroid ports. In [3], they
provided a box-TDI system describing the 2-edge-connected spanning subgraph
polyhedron for series-parallel graphs. Ding, Tan, and Zang [11] characterized the
graphs for which the TDI system of Cunningam and Marsh [9] describing the
matching polytope is actually box-TDI. Ding, Zang, and Zhao [12] introduced
new subclasses of box-perfect graphs. Cornaz, Grappe, and Lacroix [8] provided
several box-TDI systems in series-parallel graphs. More recently, these graphs
have also been characterized by the box-TDIness of their flow cone [2] and that
of their *k*-edge-connected polyhedron [1]. These last two results use characteriza-
tions of box-TDI polyhedra given by Chervet, Grappe, and Robert [4].

Box-TDI systems do not describe all rational polyhedra, while TDI systems
do [14]. A polyhedron that can be described by a box-TDI system is a *box-TDI
polyhedron*, and every TDI system describing it is actually box-TDI [7]. Box-TDI
polyhedra characterize the following generalization of TU matrices. A matrix is
*totally equimodular (TE)* if every subset of linearly independent rows forms an
equimodular matrix, a matrix being *equimodular* if it has full row rank and all
its nonzero maximal minors have the same absolute value. A matrix *A* is TE if
and only if the polyhedron {*x*: *Ax* ≤ *b*} is box-TDI for each rational vector *b* [4].

Several complexity results relative to TDIness and box-TDIness are known.
Deciding whether a system $Ax \le b$ is TDI or whether it is box-TDI are two
co-NP-complete problems [10]. The first problem remains co-NP-complete even
for conic systems [22], that is, when $b = 0$. A tractable case for the recognition
of box-TDI systems is when $A$ is TU, since total unimodularity can be checked
in polynomial time [24]. We continue this line of work by providing two new
hardness results.

*Contributions.* In this paper, we prove that the problem of deciding whether a given polyhedron is box-TDI is co-NP-complete. Our proof builds upon the hardness result of Ding et al. [10] about the recognition of box-TDI systems.

We also prove that the edge-vertex incidence matrix of any graph is TE.
This implies that the edge relaxation of the stable set problem is a box-TDI
polyhedron. From the NP-hardness of the maximum stable set problem, it follows
that optimizing a linear function over {$x \in \mathbb{Z}^n : Ax \le 1$} is NP-hard when A is
TE. Since the latter problem is polynomial when $A$ is TU, this unveils a major
difference between TE and TU matrices. Moreover, this hardness result also
implies that integer optimization over box-TDI polyhedra is NP-hard.

Another difference between TE and TU matrices is that the transpose of
a TE matrix is not always TE. We highlight this fact by characterizing the
equimodularity and the total equimodularity of the vertex-edge incidence matrix
of a graph.

*Outline.* In Section 2, we provide the definitions and some results needed throughout the paper. In Section 3, we characterize the equimodularity and the total equimodularity of the edge-vertex and of the vertex-edge incidence matrix of a graph. Based on these results, in Section 4, we characterize the box-TDIness of the stable set polytope and that of the edge cover dominant polyhedron of a graph. As a consequence, we prove that Integer Programming over box-TDI polyhedra is NP-complete and that recognizing whether a polyhedron is box-TDI is co-NP-complete.

## 2 Preliminaries

### 2.1 Matrices and polyhedra

In a given matrix, a *minor* is the determinant of any square submatrix. When the latter has maximal size, the associated minor is *maximal*.

Recall that an integer matrix is unimodular if it has full row rank and all its nonzero maximal minors are $\pm 1$. More generally, a rational matrix is equimodular if it has full row rank and all its nonzero maximal minors have the same absolute value. As noticed in [4], checking equimodularity can be done in polynomial time. Indeed, equimodular matrices are TU up to a basis change, and checking total unimodularity can be done in polynomial time [24].

A *face* of a polyhedron $P = \{x: Ax \le b\}$ is the polyhedron obtained by imposing equality on some inequalities in the description of $P$. A matrix $M$ is *face-defining* for a face $F$ of $P$ if it has full row rank and the affine space generated by $F$ can be written as $\{x: Mx = d\}$ for some vector $d$ of appropriate size. These matrices characterize box-TDI polyhedra as follows.

**Theorem 1 (Chervet et al. [4]).** A polyhedron $P$ is box-TDI if and only if every face-defining matrix of $P$ is equimodular.

In our proofs, we will use Theorem 1 combined with the following observation.

**Observation 2 (Chervet et al. [4]).** A full row rank matrix $M$ is face-defining for a face $F$ of a polyhedron $P \subseteq \mathbb{R}^n$ if and only if there exist a vector $d$ and a set $H \subseteq F \cap \{x: Mx = d\}$ of $\dim(F) + 1$ affinely independent points such that $|H| + \text{rank}(M) = n + 1$.

Recall that a matrix is TE if every subset of linearly independent rows
forms an equimodular matrix. By Theorem 1, every polyhedron whose constraint
matrix is TE is box-TDI. It turns out that this characterizes TE matrices.
**Theorem 9.** The edge-vertex incidence matrix of a graph is totally equimodular.

*Proof.* Let $G = (V, E)$ be a graph and let $M$ be a full row rank matrix formed by a subset of $k$ rows of the edge-vertex incidence matrix of $G$. Let us prove that $M$ is equimodular by induction on its number of rows: the base case is when $M$ has one row, and then $M$ is equimodular since a row has only values in $\{0, 1\}$. The matrix $M$ encodes a subgraph $H = (V, F)$ of $G$ with $k = |F|$ edges.

We have $|V(F)| \geq |F|$, as otherwise $M$ would have too many columns of zeros to have full row rank. If $|V(F)| = |F|$, then $M$ has exactly one nonsingular $k \times k$ submatrix, hence $M$ is equimodular. If $|V(F)| > |F|$, then $H$ has a vertex $u$ of degree one. Indeed, if every vertex of $V(F)$ had degree at least two we would have $2|F| = \sum_{w \in V(F)} d_H(w) \geq 2|V(F)|$, a contradiction.

The column of $u$ in $M$ contains a single one, in $uv$'s row, where $v$ is the neighbor of $u$ in $H$. Let $M'$ be the matrix obtained from $M$ by removing $uv$'s row. Note that $M'$ has full row rank since $M$ has it. A nonsingular $k \times k$ submatrix $N$ of $M$ has to contain at least one of $u$ and $v$, as otherwise it has only zeros in $uv$'s row. When $N$ contains exactly one of them, then develop with respect to $uv$'s row. When $N$ contains both of them, then develop with respect to $u$'s column. In both cases, the determinant of $N$ is equal to a maximal minor of $M'$, up to the sign. By the induction hypothesis, $M'$ is equimodular, so all these determinants are equal in absolute value. Therefore, so are the nonzero $k \times k$ determinants of $M$, and $M$ is equimodular. $\square$

In [15], the authors proved that the problem of determining the maximum absolute value of a minor of a given incidence matrix is NP-hard. Hence, Theorem 9 implies the following.

**Corollary 10.** Determining the maximum absolute value of a minor of a totally equimodular matrix is NP-hard.

## 3.2 Vertex-edge incidence matrices

In contrast to edge-vertex incidence matrices, vertex-edge incidence matrices of graphs are rarely TE. We characterize below the classes of graphs for which they are. We also characterize when these matrices are equimodular. Note that when the graph $G$ is bipartite the incidence matrix of $G$ has no full row rank by Theorem 5.

**Theorem 11.** The vertex-edge incidence matrix of a connected nonbipartite graph $G = (V, E)$ is equimodular if and only if $G$ has no two vertex-disjoint odd circuits.

*Proof.* Note that every maximal square submatrix of a vertex-edge incidence matrix induces a spanning subgraph of $G$ having $|V|$ edges. Since a spanning tree of $G$ has $|V| - 1$ edges, this subgraph contains a circuit.

(⇒) Suppose that $G$ has two vertex-disjoint odd circuits $C_1$ and $C_2$, and let $e_1$ and $e_2$ be edges of $C_1$ and $C_2$, respectively. Since $G$ is connected, there exists a
spanning tree $T$ of $G$ containing $C_1 \cup C_2 \setminus \{e_1, e_2\}$. Since $C_1$ and $C_2$ are vertex-disjoint, there exists an edge $e$ of $T$ whose removal splits $T$ into two trees $T_1$ and $T_2$ with $C_1 \setminus \{e_1\} \subseteq T_1$ and $C_2 \setminus \{e_2\} \subseteq T_2$.

By Theorem 5, $|\det(A_{T_i \cup \{e_i\}}^\top)| = |\det(A_{T \cup \{e_i\}}^\top)| = 2$, for $i = 1, 2$. By construction, $|\det(A_{T \cup \{e_1, e_2\} \setminus \{e\}}^\top)| = |\det(A_{T_1 \cup \{e_1\}}^\top) \det(A_{T_2 \cup \{e_2\}}^\top)| = 4$. The determinants of the maximal nonsingular square submatrices $A_{T \cup \{e_1, e_2\} \setminus \{e\}}^\top$ and $A_{T \cup \{e_1\}}^\top$ of $A_G^\top$ differ in absolute value, thus $A_G^\top$ is not equimodular.

(=$\Leftarrow$) Suppose that $G$ is not bipartite and has no two vertex-disjoint odd circuits. Note that since $G$ is connected, it contains a nonbipartite connected spanning subgraph $H$ with $|V|$ edges. By Theorem 5, we have $|\det(A_H^\top)| = 2$ and $A_G^\top$ has full row rank. This holds for every nonbipartite connected spanning subgraph with $|V|$ edges. The other spanning subgraphs of $G$ with $|V|$ edges are either connected and bipartite or a product of smaller minors corresponding to connected subgraphs. In the first case, the associated minor is zero by Theorem 5. In the second case, by Theorem 5 and the fact that $G$ has no two vertex-disjoint odd circuits, one of these smaller minors is zero. Therefore, every maximal minor of $A_G^\top$ belongs to $\{-2, 0, 2\}$, and $A_G^\top$ is equimodular. $\square$

Theorem 11 gives a matricial characterization of graphs having two vertex-disjoint odd circuits. A graph-theoretic characterization of these graphs was given by Lovász [25] (a proof can be found in [19]), and they also appear in the context of extended formulations [5] and unimodular covers [16]. In particular, since equimodularity can be checked in polynomial time [4], Theorem 11 provides another polynomial-time algorithm for their recognition [20].

**Theorem 12.** The vertex-edge incidence matrix of a connected graph $G = (V, E)$ is totally equimodular if and only if $G$ is an odd hole or a bipartite graph.

*Proof.* ($\Rightarrow$) Suppose that $G$ is neither bipartite nor an odd hole. Then, $G$ contains an odd hole $C$ and two edges $uv$ and $uw$ in $C$ and $\delta(V(C))$, respectively.

The submatrix of $A_G^\top$ restricted to the rows associated with $V(C)$ can be reordered such that the first $|C| + 1$ columns form the matrix $[A_C, \chi^u]$. By Lemma 7, it has full row rank but is not equimodular. This implies that $A_G^\top$ is not TE.

(=$\Leftarrow$) If $G$ is bipartite, then $A_G^\top$ is TU by Theorem 6, and hence TE. Now, if $G$ is an odd hole, then $A_G^\top$ is also the edge-vertex incidence matrix of an odd hole, and hence is TE by Theorem 9. $\square$

By Theorem 12, deciding whether a vertex-edge incidence matrix is TE can be done in polynomial time. This might be a first step towards the complexity of recognizing TE matrices, which is an open problem raised in [4].

# 4 Box-TDIness and complexity consequences

In this section, we provide several complexity results based on the characterization of total equimodularity of incidence matrices devised in the previous section.
## 4.1 Edge relaxation of the stable set polytope

Given a graph $G = (V, E)$, a stable set is a set of pairwise nonadjacent vertices. The polytope $\{x \in \mathbb{R}^V: A_Gx \le 1, x \ge 0\}$ is called the edge relaxation of the stable set polytope of $G$ and its integer points are precisely the characteristic vectors of the stable sets of $G$.

By Theorems 3 and 9, every polyhedron of the form $\{x \in \mathbb{R}^V: A_Gx \le b\}$ with $b$ rational is box-TDI. As adding $x \ge 0$ preserves box-TDIness, we have the following.

**Corollary 13.** *The edge relaxation of the stable set polytope is box-TDI.*

Since finding a maximum stable set in a given graph is NP-hard [18], Corollary 13 implies that integer programming over a box-TDI polyhedron is NP-hard.

**Corollary 14.** *Given a box-TDI polyhedron $P$ and a cost vector $c$, finding an integer point $x$ maximizing $c^\top x$ over $P$ is NP-hard.*

## 4.2 Edge relaxation of the edge cover dominant

Since multiplying a row by $-1$ preserves total equimodularity, by Theorems 3 and 12, when $G$ is an odd hole or a bipartite graph, the polyhedron $\{x \in \mathbb{R}^E: A_G^\top x \ge 1\}$ is box-TDI. It turns out that the converse holds.

**Theorem 15.** *Given a connected graph $G = (V, E)$, the polyhedron $\{x \in \mathbb{R}^E: A_G^\top x \ge 1\}$ is box-TDI if and only if $G$ is an odd hole or a bipartite graph.*

*Proof.* To prove the remaining direction, suppose that $G$ is neither an odd hole nor a bipartite graph. Let us build a subgraph $H = (V, F)$ of $G$ for which the polytope is not box-TDI. Since $\{x \in \mathbb{R}^F: A_H^\top x \ge 1\}$ is the projection onto $F$ of $\{x \in \mathbb{R}^E: A_G^\top x \ge 1\}$ intersected with the box $\{x_e = 0, \text{ for all } e \in E \setminus F\}$, this will imply that $\{x \in \mathbb{R}^E: A_G^\top x \ge 1\}$ is not box-TDI.

Since $G$ is connected, it contains an odd hole $C$ with $\delta(V(C))$ nonempty. Denote by $U$ the set of vertices whose neighbors are all in $V(C)$. Let $S$ be a subset of $\delta(U)$ such that each vertex of $U$ is covered by exactly one edge of $S$. Let $F = (E \setminus \delta(U)) \cup S$ and $H = (V, F)$.

Let $M$ be the $|V(C)| \times |F|$ matrix formed by the rows of $A_H^\top$ associated with the vertices of $V(C)$. By considering the columns of $M$ associated to $C$ and an edge of $\delta(V(C))$, observe that $M$ contains a matrix of the type $[A_C^\top, \chi^u]$ for some $u \in V(C)$. Therefore, by Lemma 7, $M$ has full row rank but is not equimodular.

We now show that $M$ is face-defining for $P = \{x \in \mathbb{R}^F: A_H^\top x \ge 1\}$. Since $M$ has full row rank, by Observation 2 it is sufficient to exhibit $|F| - |V(C)| + 1$ affinely independent points of the face $Q = P \cap \{x: Mx = 1\}$ of $P$. Let $K = F \setminus (C \cup \delta(C))$, we define:

$$p^0 = \frac{1}{2}\chi^C + \chi^{S \cup K} + \frac{1}{2}\sum_{u \in V(C)} |\delta(u) \cap S|(\chi^{L_u} - \chi^{C \setminus L_u}),$$

where $L_u$ is the unique perfect matching of the path $C \setminus \delta(u)$. Then, we define two types of points:
• $p^e = p^0 + \chi^e$, for each $e \in K$,

• $q^{uv} = p^0 + \chi^{uv} + \frac{1}{2}(\chi^{L_u} - \chi^{C\setminus L_u})$, for each $uv \in \delta(V(C))$ with $u \in V(C)$.

Together with $p^0$, the points $p$ are affinely independent because $p^e - p^0 = \chi^e$, for each $e$ in $K$. Adding the points $q$ maintains affine independency since $q^{uv}$ is the only point with $uv$'s coordinate different from 1.

Moreover, all these points belong to $Q$ since they satisfy $x(\delta(u)) = 1$ for all $u \in V(C)$ and $x(\delta(v)) \ge 1$ for all $v \in V \setminus V(C)$. To see this, note that for each $u$ in $V(C)$, $\chi^{L_u} - \chi^{C\setminus L_u}$ satisfies $x(\delta(u)) = -2$ and $x(\delta(v)) = 0$ for all $v \ne u$. The number of points $p$ is $|K| + 1 = |F| - |V(C)| - |\delta(V(C))| + 1$ and the number of points $q$ is $|\delta(V(C))|$, hence $M$ is face-defining for $F$.

The matrix $M$ is nonequimodular and face-defining for $\{x \in \mathbb{R}^F : A_H^\top x \ge \mathbf{1}\}$. Therefore, the latter is not box-TDI by Theorem 1, and neither is $\{x \in \mathbb{R}^E : A_G^\top x \ge \mathbf{1}\}$. $\square$

Given a graph $G = (V, E)$, an edge cover is a set of edges covering each vertex. The polytope $\{x \in \mathbb{R}^E : A_G^\top x \ge \mathbf{1}, x \ge \mathbf{0}\}$ is called the edge relaxation of the edge cover dominant of $G$ and its binary points are precisely the characteristic vectors of the edge covers of $G$.

By Theorem 15, the edge relaxation of the edge cover dominant of an odd hole or a bipartite graph is box-TDI. The converse does not hold, because adding $x \ge \mathbf{0}$ might cut off faces defined by nonequimodular matrices, such as the one given in the proof of Theorem 15. The following result gives the larger class of graphs to be considered to get the converse.

**Theorem 16.** The edge relaxation of the edge cover dominant of a connected graph $G$ is box-TDI if and only if $G$ is an odd hole or a quasi-bipartite graph different from $K_4$.

*Proof.* Let $P_G$ denote the edge relaxation of the edge cover dominant of $G$. (=$) By Theorem 8, if $G$ is a quasi-bipartite graph different from $K_4$, then the system $A_G^\top x \ge \mathbf{1}, x \ge \mathbf{0}$ is box-TDI, hence $P_G$ is box-TDI.

If $G$ is an odd hole, $P_G$ is the intersection of the polyhedron stated in Theorem 15 with the box $\{x : x \ge \mathbf{0}\}$. Theorem 15 and the definition of box-TDI polyhedra imply that $P_G$ is box-TDI.

(=$) Let us show that $P_{K_4}$ is not box-TDI. By definition, $P_{K_4} = \{x : A_{K_4}^\top x \ge \mathbf{1}, x \ge \mathbf{0}\}$, where

$$A_{K_4}^\top = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{bmatrix}.$$

The full row rank matrix formed by the last three rows of $A_{K_4}^\top$, say $B$, is not equimodular because the determinant of the first three columns is 1, whereas that of the last three is 2. Moreover, the four points $z_1 = (1, 0, 0, 0, 0, 1)^\top$, $z_2 = (0, 1, 0, 0, 0, 1)^\top$, $z_3 = (0, 0, 1, 1, 0, 0)^\top$ and $z_4 = (1, 1, 1, 0, 0, 0)^\top$ belong to $P_G$,
satisfy $Bx = \mathbf{1}$, and are affinely independent. Therefore, by Observation 2, $B$ is a
face-defining matrix of $P_{K_4}$. This implies that $P_{K_4}$ is not box-TDI by Theorem 1.

To complete the proof there remains to show that $P_G$ is not box-TDI when $G$ is neither quasi-bipartite nor an odd hole. In this case, there exists an odd circuit $C$ such that $G \setminus V(C)$ is nonempty and has no isolated vertices. If $C$ has a chord $e$, then $C \cup \{e\}$ contains a smaller odd circuit $C'$. Since $C \setminus C'$ is a path of length at least two, $G \setminus V(C')$ has no isolated vertices. Therefore, we may assume that $C$ is an odd hole.

Let $M$ be the submatrix of $A_G^\top$ formed by the rows associated with the vertices of $V(C)$. By construction, $\delta(V(C))$ is nonempty, hence $M$ contains $[A_C^\top, \chi^u]$, for some $u \in V(C)$. By Lemma 7, $M$ is not equimodular.

We show that $M$ is face-defining for $P_G$. Since $M$ has full row rank, by Observation 2 it is sufficient to exhibit $|E| - |V(C)| + 1$ affinely independent points of the face $F = P_G \cap \{x: Mx = \mathbf{1}\}$ of $P_G$. We exhibit the same points as in the proof of Theorem 15, the difference is that, here, the set $U$ is empty since there are no isolated vertices when removing $V(C)$:

$p^0 = \frac{1}{2}\chi^C + \chi^K,$

$p^e = p^0 + \chi^e$, for each $e \in K,$

$q^{uv} = \chi^{uv} + \chi^{L_u} + \chi^K$, for each $uv \in \delta(V(C))$ with $u \in V(C).$

As shown in the proof of Theorem 15, these points are affinely independent and satisfy $A_G^\top x \ge \mathbf{1}, Mx = \mathbf{1}$. Since these points also satisfy $x \ge \mathbf{0}$, they belong to the face $P_G \cap \{x: Mx = \mathbf{1}\}$ for which $M$ is a face-defining matrix. By Theorem 1, $P_G$ is not box-TDI. $\square$

Theorem 16 implies that recognizing box-TDI polyhedra is co-NP-complete since recognizing quasi-bipartite graphs is [10].

**Corollary 17.** *Recognizing box-TDI polyhedra is co-NP-complete.*

Conclusion

In this paper, we provide two hardness results regarding box-TDI polyhedra, and their proofs are based on the exhibition of new classes of binary TE matrices. A natural subsequent question is the characterization of binary TE matrices.

References

1. Barbato, M., Grappe, R., Lacroix, M., Lancini, E.: Box-total dual integrality and edge-connectivity. Mathematical Programming (2022)

2. Barbato, M., Grappe, R., Lacroix, M., Lancini, E., Wolfler Calvo, R.: The Schrijver system of the flow cone in series-parallel graphs. Discrete Applied Mathematics **308**, 162–167 (2022)

3. Chen, X., Ding, G., Zang, W.: The box-TDI system associated with 2-edge connected spanning subgraphs. Discrete Applied Mathematics **157**(1), 118–125 (2009)
4. Chervet, P., Grappe, R., Robert, L.: Box-total dual integrality, box-integrality, and equimodular matrices. Mathematical Programming **188**(1), 319–349 (2021)

5. Conforti, M., Fiorini, S., Huynh, T., Weltge, S.: Extended formulations for stable set polytopes of graphs without two disjoint odd cycles. In: Bienstock, D., Zambelli, G. (eds.) Integer Programming and Combinatorial Optimization. pp. 104–116. Springer International Publishing, Cham (2020)

6. Cook, W.J.: Operations that preserve total dual integrality. Operations Research Letters **2**(1), 31–35 (1983)

7. Cook, W.J.: On box totally dual integral polyhedra. Mathematical Programming **34**(1), 48–61 (1986)

8. Cornaz, D., Grappe, R., Lacroix, M.: Trader multiflow and box-TDI systems in series-parallel graphs. Discrete Optimization **31**(1) (2019)

9. Cunningham, W.H., Marsh, A.B.: A primal algorithm for optimum matching, pp. 50–72. Springer Berlin Heidelberg, Berlin, Heidelberg (1978)

10. Ding, G., Feng, L., Zang, W.: The complexity of recognizing linear systems with certain integrality properties. Mathematical Programming **114**(2), 321–334 (2008)

11. Ding, G., Tan, L., Zang, W.: When is the matching polytope box-totally dual integral? Mathematics in Operations Research **43**(1), 64–99 (2018)

12. Ding, G., Zang, W., Zhao, Q.: On box-perfect graphs. Journal of Combinatorial Theory, Series B **128**, 17–46 (2018)

13. Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. In: Hammer, P., Johnson, E., Korte, B., Nemhauser, G. (eds.) Studies in Integer Programming, Annals of Discrete Mathematics, vol. 1, pp. 185–204. Elsevier (1977)

14. Giles, F., Pulleyblank, W.: Total dual integrality and integer polyhedra. Linear Algebra and its Applications **25**, 191–196 (1979)

15. Grossman, J.W., Kulkarni, D.M., Schochetman, I.E.: On the minors of an incidence matrix and its smith normal form. Linear Algebra and its Applications **218**, 213–224 (1995)

16. Haase, C., Paffenholz, A., Piechnik, L., Santos, F.: Existence of unimodular triangulations - positive results. Memoirs of the American Mathematical Society **270** (2014)

17. Hoffman, A.J., Kruskal, J.B.: Integral Boundary Points of Convex Polyhedra, pp. 49–76. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)

18. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85–103. Springer US, Boston, MA (1972)

19. Kawarabayashi, K., Ozeki, K.: A simpler proof for the two disjoint odd cycles theorem. Journal of Combinatorial Theory, Series B **103**(3), 313–319 (2013)

20. Kawarabayashi, K., Reed, B.: Odd cycle packing. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing. p. 695–704. STOC ’10, Association for Computing Machinery, New York, NY, USA (2010)

21. König, D.: Gráfok és mátrixok. Matematikai és Fizikai Lapok **38**, 116–119 (1931)

22. Pap, J.: Recognizing conic TDI systems is hard. Mathematical Programming **128**(1), 43–48 (2011)

23. Schrijver, A.: Theory of linear and integer programming. In: Wiley-Interscience series in discrete mathematics and optimization (1999)

24. Seymour, P.D.: Decomposition of regular matroids. Journal of Combinatorial Theory. Series B **28**(3), 305–359 (1980)

25. Seymour, P.D.: Matroid minors. In: Handbook of Combinatorics. pp. 527–550. Elsevier, Amsterdam (1995)