betaFeedback

WorksComputer Science

Combinatorial optimization with bounded subdeterminants

Abstract

We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally ΔΔ-modular if every square submatrix has determinant of absolute value at most ΔΔ. For every fixed ΔΔ, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally ΔΔ-modular. We extend this list by showing that the same holds for many other problems, including the weighted versions of maximum cut, the traveling salesman problem, feedback vertex set, odd cycle transversal, dominating set, max 2-sat, induced matching, and cluster vertex deletion, as well as for kk-colorability and graph isomorphism. Our proofs reveal several new ways in which bounded subdeterminants impose combinatorial structure: they bound the size or maximum degree of the input graph, bound packings of cycles and other obstructions, or yield decompositions into tractable graph classes such as forests, chordal graphs, graphs of bounded treewidth, and graphs of bounded linear mim-width.

Introduction

An integer matrix is totally Δ\Delta-modular if the absolute value of the determinant of every square submatrix is at most Δ\Delta. It is a fundamental open problem whether integer programs

max⁡{cTx:Ax≤b, x∈Zn}\max\{c^{T}x : Ax \le b,\ x \in\mathbb{Z}^{n}\}

with a totally Δ\Delta-modular coefficient matrix AA can be solved in polynomial time for fixed Δ\Delta. For Δ=1\Delta= 1, i.e., for totally unimodular matrices, the answer is well-known to be affirmative. Artmann, Weismantel, and Zenklusen [1] showed that polynomial-time solvability continues to hold for Δ=2\Delta= 2. In earlier work, Shevchenko [36] explicitly conjectured that the problem is polynomial-time solvable for every fixed Δ\Delta. However, the complexity status remains open for all Δ≥3\Delta\ge3 and it is unclear which algorithmic paradigm might be suitable for solving these instances. Instead of focusing on all instances for some fixed Δ\Delta, we follow a complementary, problem-oriented viewpoint and propose a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations.

Among the list of classical combinatorial optimization problems, a first natural candidate for this study is the knapsack problem, which has an immediate integer programming formulation. This formulation is totally Δ\Delta-modular if and only if the largest size of an item is at most Δ\Delta, in which case the problem is well-known to be solvable in polynomial time by dynamic programming. While this provides a simple sanity check for the perspective we advocate, it is certainly limited in insight.

Moving beyond single constraints, graph-theoretic problems provide a significantly richer landscape for this perspective. Natural candidates are the stable set, vertex cover, and max clique problems, which have indeed been investigated in this context. For these problems, total Δ\Delta-modularity turns out to be equivalent to bounding the odd cycle packing number of the underlying graph (or its complement) by log⁡2Δ\log_2 \Delta. Initiated by Bock, Faenza, Moldenhauer, and Ruiz-Vargas [4], a series of works [9, 10, 17, 30] has shown that the weighted versions of these problems are actually polynomially solvable for any fixed Δ\Delta. Moreover, polynomial-time algorithms have been established for totally Δ\Delta-modular instances of the total matching problem by Ferrarini, Fiorini, Kober, and Yuditsky [15] and the unweighted dominating set problem by Malyshev and Gribanov [28]. In this work, we extend the latter result to weighted instances and give polynomial-time algorithms for several other problems.

Theorem 1.1. For every constant Δ\Delta, the following problems are polynomially solvable when restricted to instances for which the coefficient matrix of their natural integer programming formulation is totally Δ\Delta-modular:

  • kk-colorability

  • graph isomorphism

  • feedback vertex set

  • odd cycle transversal

  • dominating set

  • induced matching

  • cluster vertex deletion

  • traveling salesman problem

  • 2-constraint satisfaction problem

Except for kk-colorability and graph isomorphism, we refer to the weighted optimization versions of the above problems. By the 2-constraint satisfaction problem (max 2-CSP) we mean its Boolean version, which includes maximum cut, maximum directed cut, and max 2-SAT. As the above result depends on the actual representations of the problems as integer programs, we explicitly state the most common formulations for each problem in the respective section of this paper.

The purpose of this work is to illustrate various new ways in which subdeterminants are linked to structural graph parameters and to highlight different algorithmic approaches needed to exploit the arising structure. Specifically, we will see that total Δ\Delta-modularity can force the input graph to be small or of bounded degree, bound the size of a packing of cycles or other obstructions, and admit decompositions into tractable graph classes such as forests, chordal graphs, graphs of bounded treewidth, and graphs of bounded linear mim-width. We view the diversity of our results as evidence that, should a general polynomial-time algorithm for integer programs with bounded subdeterminants exist, it is unlikely to arise from a single black-box theorem in integer programming. Instead, it may have to bring together a wide range of combinatorial arguments and algorithmic techniques.

In fact, we believe that a broader study of classical (hard) combinatorial optimization problems through the maximum subdeterminants of their integer programming formulations gives valuable insights for Shevchenko’s conjecture. Beyond the problems addressed in this work, there are many other problems whose complexity status under bounded subdeterminants remains open and which we believe deserve further investigation. A particular example is the uncapacitated facility location problem (where the client-facility graph is not complete) as there is a direct reduction from vertex cover that preserves maximum total Δ\Delta-modularity. As the minimum cluster vertex deletion problem can be phrased as a particular covering problem whose coefficient matrix has three nonzeros per row (see § 7), exploring other covering problems with three nonzeros per row (e.g., hitting all triangles of a graph) presents a promising direction. Another natural question is whether our result can be extended to kk-CSPs for k≥3k \ge3, or at least 3-SAT.

It would also be interesting to explore algorithmic implications of bounded subdeterminants for problems beyond the traditional scope of combinatorial optimization. First steps in this direction have been taken by Kuhlmann and Weismantel [26] who show that the ℓ1\ell_1-shortest lattice vector problem can be solved in polynomial time for totally Δ\Delta-modular instances.

The remainder of this paper is devoted to the proof of Theorem 1.1 by treating the above problems in separate sections.

k-colorability

This problem asks whether, for a given undirected graph G=(V,E)G=(V,E) and a positive integer kk, there exists a coloring c:V→[k]c:V\to[k] such that c(u)≠c(v)c(u)\ne c(v) for all {u,v}∈E\{u,v\}\in E. The problem is trivial for k=1k=1, and for k=2k=2 it is equivalent to checking whether GG is bipartite. From now on, assume k≥3k\ge3, for which the problem is NP-complete. A typical formulation of the problem as a (feasibility) integer program is

xv,i+xu,i≤1∀{u,v}∈E, i∈[k]∑i=1kxv,i=1∀v∈Vxv,i∈{0,1}∀v∈V, i∈[k](1)\begin{aligned} x_{v,i}+x_{u,i} &\le1 && \forall\{u,v\}\in E,\ i\in[k]\\ \sum_{i=1}^{k}x_{v,i} &= 1 && \forall v\in V\\ x_{v,i} &\in\{0,1\} && \forall v\in V,\ i\in[k] \tag*{(1)} \end{aligned}

where the variable xv,ix_{v,i} indicates whether vertex vv is colored with color ii for each v∈Vv\in V and i∈[k]i\in[k]. Under the assumption of bounded subdeterminants, we only have to consider input graphs with the following property.

Lemma 2.1. If the coefficient matrix of (1) is totally Δ\Delta-modular, then GG contains at most ⌊log⁡2Δ⌋\lfloor\log_2\Delta\rfloor vertex disjoint cycles.

Proof. Let B∈{0,1}E×VB \in\{0,1\}^{E \times V} be the edge-vertex-incidence matrix of GG. That is, B{u,v},w=1B_{\{u,v\},w}=1 if w∈{u,v}w \in\{u,v\} and 00 otherwise. Collect the variables into one vector x=(x(1),…,x(k))x=(x^{(1)},\ldots,x^{(k)}) where x(i)=(xv,i)v∈Vx^{(i)}=(x_{v,i})_{v\in V} for i∈[k]i\in[k]. Then we can rewrite (1) as

(B0⋯00B⋯0⋮⋮⋱⋮00⋯B)x≤1(II⋯I)x=1x∈{0,1}V×[k].\begin{aligned} \begin{pmatrix} B & \mathbf{0} & \cdots& \mathbf{0}\\ \mathbf{0} & B & \cdots& \mathbf{0}\\ \vdots& \vdots& \ddots& \vdots\\ \mathbf{0} & \mathbf{0} & \cdots& B \end{pmatrix}x &\le1\\ \begin{pmatrix} I & I & \cdots& I \end{pmatrix}x &=1\\ x&\in\{0,1\}^{V\times[k]}. \end{aligned}

Let CC be an arbitrary cycle of GG with vertices v1,…,vℓv_1,\ldots,v_\ell. If CC has odd length, then the corresponding submatrix of BB (say in the first color) has determinant ±2\pm2. If CC has even length, we find the incidence matrix of a cycle of length ℓ+3\ell+3 as a submatrix of the coefficient matrix of (1). As ℓ+3\ell+3 is odd, the resulting submatrix will have determinant of absolute value 22. To this end, select the columns corresponding to xv1,1,xv2,1,xv2,2,xv3,2,xv3,3,xv4,3,xv4,1,…,xvℓ,1x_{v_1,1},x_{v_2,1},x_{v_2,2},x_{v_3,2},x_{v_3,3},x_{v_4,3},x_{v_4,1},\ldots,x_{v_\ell,1} and the rows corresponding to {v1,v2}\{v_1,v_2\} in the first color, {v2,v3}\{v_2,v_3\} in the second color, {v3,v4}\{v_3,v_4\} in the third color, {vi,vi+1}\{v_i,v_{i+1}\} in the first color for i=4,…,ℓ−1i=4,\ldots,\ell-1, as well as the rows corresponding to v2,v3,v4v_2,v_3,v_4 in the matrix (I I … I)(I\ I\ \ldots\ I). The construction is illustrated in Figure 2.1. If C1,…,CtC_1,\ldots,C_t are

Figure 2.1. Illustration of the proof of Lemma 2.1: An even cycle in the original graph (left) and a corresponding odd cycle whose incidence matrix we find as a submatrix of the coefficient matrix (right). The dashed edge represents a path of even length (possibly zero, in which case v1=v5v_1=v_5). The curved edges represent the edges corresponding to the rows of the matrix (I I … I)(I\ I\ \ldots\ I). The shape of the vertices on the right together with the labels indicate the respective chosen columns.

vertex-disjoint cycles, we can apply the above construction to each of these cycles. Since the rows selected for any of the cycles have 0 entries in the columns selected for the other cycles, the determinant of the resulting submatrix is the product of the determinants of the submatrices corresponding to the individual cycles and hence ±2t\pm2^t.

In view of Theorem 1.1, we can exploit the above statement as follows. By the Erdős-Pósa theorem [14], there is a set UU of O(log⁡Δlog⁡log⁡Δ)O(\log\Delta\log\log\Delta) vertices that hits all cycles. For constant Δ\Delta, we can efficiently enumerate all possible choices and potential colorings of UU. For each of these choices, the remaining problem is a list coloring problem (a coloring problem in which each vertex has a list of allowed colors) in a forest. This can be solved in linear time by an algorithm due to Jansen and Scheffler [24] [83].

Graph isomorphism

The graph isomorphism problem asks whether two given graphs are equal up to a relabeling of the vertices. In other words, is there a bijection between the vertex sets of the two graphs that preserves adjacency and nonadjacency? Graph isomorphism is not known to be solvable in polynomial time nor known to be NP-complete. Babai [2] showed that it can be solved in quasipolynomial time.

If GG and G′G' are undirected graphs with adjacency matrices AA and A′A', respectively, note that GG and G′G' are isomorphic if and only if there exists a permutation matrix PP with A=PA′PTA = PA'P^{\mathsf{T}}, or, equivalently, AP=PA′AP = PA'. This gives rise to the following common (feasibility) integer programming formulation of the problem.

AX=XA′(2)AX = XA' \tag*{(2)}
∑u∈Vxuv=1∀v∈V\sum_{u \in V} x_{uv} = 1 \qquad\forall v \in V
∑v∈Vxuv=1∀u∈V\sum_{v \in V} x_{uv} = 1 \qquad\forall u \in V
xuv∈{0,1}∀u,v∈Vx_{uv} \in\{0,1\} \qquad\forall u,v \in V

Lemma 3.1. If the coefficient matrix of (2) is totally Δ\Delta-modular and G′G' has at least one edge, then the maximum degree of GG is at most Δ+1\Delta+ 1.

Proof. We may assume that GG and G′G' have the same vertex set VV. For each (u,v)∈V2(u,v) \in V^2, comparing the respective entries of AXAX and XA′XA', the equation in (2) reads

∑w∈N(u)xwv−∑w∈N′(v)xuw=0,\sum_{w \in N(u)} x_{wv} - \sum_{w \in N'(v)} x_{uw} = 0,

where N(w)N(w) and N′(w)N'(w) denote the sets of neighbors of ww in GG and G′G', respectively. Treating xx as a vector in {0,1}V2\{0,1\}^{V^2} we can rewrite the above constraints as Bx=0Bx = 0, where B∈{−1,0,1}V2×V2B \in\{-1,0,1\}^{V^2 \times V^2} is given by

B(u,v),(w,z)={+1if z=v and w∈N(u),−1if w=u and z∈N′(v),0otherwise.B_{(u,v),(w,z)} = \begin{cases} +1 & \text{if } z=v \text{ and } w \in N(u),\\ -1 & \text{if } w=u \text{ and } z \in N'(v),\\ 0 & \text{otherwise.} \end{cases}

By the assumption, BB is totally Δ\Delta-modular. Let uu be a vertex in GG with neighbors v1,…,vdv_1,\ldots,v_d in GG, and let ww denote a vertex in G′G' that has at least one neighbor zz in G′G'. Consider the submatrix of BB that consists of the rows corresponding to (u,w)(u,w) and (vi,z)(v_i,z) and the columns corresponding to (u,z)(u,z) and (vi,w)(v_i,w) for i=1,…,di=1,\ldots,d. The form of this submatrix is

D=(−11⋯11−1⋮⋱1−1)D = \begin{pmatrix} -1 & 1 & \cdots& 1\\ 1 & -1 \\ \vdots& & \ddots\\ 1 & & & -1 \end{pmatrix}

where all unspecified entries are zero. By adding all rows to the first row, we obtain d−1=∣det⁡D∣≤Δd - 1 = \lvert\det D \rvert\le\Delta, which yields the claim.

Lemma 3.1 allows us to reduce the problem to the isomorphism problem for graphs of bounded degree, which was shown to be polynomially solvable by Luks [27].

Feedback vertex set and odd cycle transversal

The feedback vertex set problem asks to find a minimum-weight set of vertices that intersects every cycle in a given graph, or equivalently, such that the graph obtained by deleting these vertices is a forest. Similarly, the odd cycle transversal problem asks to find a minimum-weight set of vertices that intersects every odd cycle in a given graph, or equivalently, such that the graph obtained by deleting these vertices is bipartite. Given a graph G=(V,E)G=(V,E) and a weight function w:V→Qw:V\to\mathbb{Q}, a straightforward integer programming formulation of the problems is

min⁡∑v∈Vw(v)xvs.t.∑v∈V(C)xv≥1∀C∈Cxv∈{0,1}∀v∈V(3)\begin{aligned} \min\quad& \sum_{v\in V} w(v)x_v\\ \text{s.t.}\quad& \sum_{v\in V(C)} x_v \ge1 && \forall C\in\mathcal{C}\\ & x_v\in\{0,1\} && \forall v\in V \tag*{(3)} \end{aligned}

where C\mathcal{C} is the set of all cycles for the feedback vertex set problem, respectively, the set of all odd cycles for the odd cycle transversal problem, and xvx_v indicates whether the vertex vv is included in the solution.

We remark that, for fixed Δ\Delta, it is known that a totally Δ\Delta-modular matrix with nn columns has only polynomially many (in nn) distinct rows (see [31]). Hence, in any totally Δ\Delta-modular instance, (3) has only polynomially many distinct constraints. However, we do not see how this alone implies that the problem can be solved in polynomial time. Instead, we will use that restricting feedback vertex set instances to those with bounded subdeterminants excludes large grid minors, which allows us to bound the treewidth of the input graph. We then extend this approach to the odd cycle transversal problem.

Feedback vertex set

To formalize the grid minor argument, let us first fix the minor terminology we use. Given graphs GG and HH, an HH-model MM in GG consists of a non-empty tree M(v)M(v) that is a subgraph of GG for each vertex v∈V(H)v\in V(H), called a branch set, and an edge M({u,v})∈E(G)M(\{u,v\})\in E(G) with one endpoint in M(u)M(u) and the other in M(v)M(v) for each edge {u,v}∈E(H)\{u,v\}\in E(H), such that all branch sets are pairwise vertex-disjoint. GG has an HH-minor if and only if there is an HH-model in GG.

Lemma 4.1. For each k≥2k\ge2, if a graph GG contains a (2k×2k)(2k\times2k)-grid as a minor, then the coefficient matrix of (3) with C\mathcal{C} being the set of all cycles in GG contains every non-singular 0/10/1-matrix of size k×kk\times k as a submatrix.

Proof. Let AA be an arbitrary non-singular $0/1$-matrix of size k×kk\times k. In particular, all rows of AA are distinct. We will first describe the case where GG contains a (2k×2k)(2k\times2k)-grid as a subgraph, not only as a minor. Label the vertices of the grid as vi,jv_{i,j} for i,j∈[2k]i,j\in[2k] where ii is the index of the grid row and jj is the index of the grid column. We build our submatrix by selecting the columns corresponding to vertices in the first grid row with odd grid column index, that is, v1,2ℓ−1v_{1,2\ell-1} for ℓ∈[k]\ell\in[k]. Then, for each row a∈{0,1}ka\in\{0,1\}^k of the matrix AA, we construct a cycle that yields precisely this row in the submatrix. To this end, choose any path from v2,1v_{2,1} to v2,2kv_{2,2k} that intersects the first two grid rows only in its endpoints. Then, for each entry aia_i of aa for i∈[k−1]i\in[k-1], construct a path from $v_{2,2i-1} to v2,2i+1v_{2,2i+1} as follows. If ai=0a_i = 0, use the path joining v2,2i−1v_{2,2i-1} and v2,2i+1v_{2,2i+1} in the second grid row, thus avoiding v1,2i−1v_{1,2i-1}. If ai=1a_i = 1, use the path v2,2i−1,v1,2i−1,v1,2i,v2,2i,v2,2i+1v_{2,2i-1}, v_{1,2i-1}, v_{1,2i}, v_{2,2i}, v_{2,2i+1}, thus using v1,2i−1v_{1,2i-1}. For aka_k, construct a path from v2,2k−1v_{2,2k-1} to v2,2kv_{2,2k} by using an analogous construction. By joining all these paths, we obtain a cycle that intersects the selected vertices in the first grid row precisely in the vertices corresponding to the 1-entries of aa.

Now, assume that GG has a (2k×2k)(2k \times2k)-grid HH as a minor. Let MM be an HH-model in GG. Consider the selection of vertices and cycles in HH described above. For each selected cycle in HH, we obtain a corresponding cycle in GG by taking M(e)M(e) for each edge ee of the cycle and, for each vertex vv of the cycle, connecting the relevant endpoints by a path in M(v)M(v). Concerning the selected vertices, some care is needed, since the branch set M(v)M(v) of a vertex v∈V(H)v \in V(H) may contain multiple vertices of GG, some of which might not be part of all lifted cycles through M(v)M(v). However, note that the selected vertices in HH all have degree at most 3. A helpful fact is that in any tree and for any three (not necessarily distinct) vertices of that tree, there is a unique vertex that is contained in all three paths between any two of the three vertices. Using this fact, we can select a vertex v′v' in M(v)M(v) for each selected vertex vv that is contained in the selected cycles in GG if and only if vv is contained in the corresponding cycles in HH.

Note that there are 0/10/1-matrices of size k×kk \times k with determinant exponential in kk. Hence, by the above lemma, any graph for which the formulation (3) is totally Δ\Delta-modular cannot contain a large grid as a minor. The grid minor theorem of Robertson and Seymour [33] states that such graphs have bounded treewidth (see [13 §12] for a definition of treewidth).

More concretely, we conclude that there exists a function ff such that the treewidth of every graph GG, for which the formulation (3) is totally Δ\Delta-modular, is at most f(Δ)f(\Delta). Moreover, the feedback vertex set problem can be solved in polynomial time on graphs of bounded treewidth (see [18]). This shows that, for each fixed Δ\Delta, totally Δ\Delta-modular instances of the feedback vertex set problem can be solved in polynomial time.

Odd cycle transversal

In order to show the corresponding result for the odd cycle transversal problem, we adapt the approach for the feedback vertex set problem using the techniques of [21]. Namely, we replace minors and grids by suitable variants to control the parity of cycles.

Let MM be an HH-model in a graph GG. We call MM an odd HH-model if the vertices of its branch sets admit a 2-coloring that is proper on each branch set M(v)M(v) and under which each edge M(e)M(e) is monochromatic. Accordingly, we say that HH is an odd minor of GG if GG contains an odd HH-model. It is easy to see that odd minors preserve the parity of cycles in the sense that every cycle in HH gives rise to a cycle of the same parity in GG with the natural lifting described in the proof of Lemma 4.1.

The role of grids in the case of the feedback vertex set problem is taken over by singly parity-breaking grids. We define such a grid of order kk as the graph obtained from the (2k×2k)(2k \times2k)-grid by adding a single parity-breaking edge in the center, see Figure 4.1 for an illustration of the case k=3k = 3.

Figure 4.1. The singly parity-breaking grid of order 3.

We obtain the following lemma which corresponds to Lemma 4.1.

Lemma 4.2. For each k≥3k \ge3, if a graph GG contains a singly parity-breaking grid of order kk as an odd minor, then the coefficient matrix of (3) with CC being the set of all odd cycles in GG contains every non-singular 0/1-matrix of size k×kk \times k as a submatrix.

Proof. The proof is completely analogous to the proof of Lemma 4.1. The only difference is that we choose the path from v2,1v_{2,1} to v2,2kv_{2,2k} such that it uses the parity-breaking edge exactly once, making the cycle odd. This is possible since the parity-breaking edge lies outside the first two rows for k≥3k \ge3.

Since there are 0/1-matrices with determinant exponential in their size, Lemma 4.2 implies that if the coefficient matrix of (3) for odd cycle transversal is totally Δ\Delta-modular, then the underlying graph does not contain a singly parity-breaking grid of order k(Δ)k(\Delta) for a function k(Δ)=O(log⁡Δ)k(\Delta) = O(\log\Delta) as an odd minor.

Graphs without such an odd minor are well-structured in terms of their blocks. To make this precise, define a cutvertex of a graph to be a vertex whose removal increases the number of connected components and a block of a graph as a maximal connected subgraph without a cutvertex. Note that a block is either a maximal 2-connected subgraph, a single edge, or an isolated vertex. By a classical result of [37] the graph Tbc(G)T_{bc}(G) that has one vertex for each block and each cutvertex of a connected graph GG, where a block XX is adjacent to a cutvertex vv if v∈V(X)v \in V(X), is a tree, called the block-cut tree of $G. Tbc(G)T_{bc}(G) can be computed in linear time (see [35]). Note that every cycle is contained in a single block, and hence a vertex set is an odd cycle transversal of GG if and only if its intersection with each block is an odd cycle transversal of that block.

Lemma 4.3. There is a function gg such that, for every positive integer kk, every block of a graph that does not contain the singly parity-breaking grid of order kk as an odd minor is bipartite or has treewidth at most g(k)g(k).

Proof. Blocks that are not 2-connected are isomorphic to K1K_1 or K2K_2 and hence bipartite. Since an odd model in a subgraph is also an odd model in the whole graph, the claim follows from [21 Lemma 5.6], which implies that every non-bipartite 2-connected graph without the singly parity-breaking grid of order kk as an odd minor has treewidth at most g(k)g(k).

We can now give a dynamic programming algorithm similar to [21 §7].

Lemma 4.4. Let ℓ\ell be a fixed integer. For a graph GG each of whose blocks is bipartite or has treewidth at most ℓ\ell, a minimum-weight odd cycle transversal can be computed in polynomial time.

Proof. On a single block, the problem can be solved in polynomial time. For bipartite graphs, the problem is trivial and for graphs of bounded treewidth the polynomial-time algorithm developed in [16 §3] can directly be extended to the weighted case.

We may assume that GG is connected and has a cutvertex, as otherwise we can treat the components separately or GG is a single block. We compute the block-cut tree Tbc(G)T_{\mathrm{bc}}(G) and root it at a cutvertex rr. Then each block XX has a parent pX∈V(X)p_X \in V(X) in Tbc(G)T_{\mathrm{bc}}(G), and its children CXC_X are the cutvertices in V(X)∖{pX}V(X) \setminus\{p_X\}. The children CvC_v of a cutvertex vv are the blocks XX with pX=vp_X = v. For a cutvertex vv, let GvG_v be the union of all blocks in the subtree of Tbc(G)T_{\mathrm{bc}}(G) rooted at vv. In particular, we have Gr=GG_r = G. Let opt⁡v(0)\operatorname{opt}_v(0) be the minimum weight of an odd cycle transversal of GvG_v that does not contain vv, and let opt⁡v(1)\operatorname{opt}_v(1) be the minimum weight of an odd cycle transversal of GvG_v that contains vv. We compute these values bottom-up in Tbc(G)T_{\mathrm{bc}}(G) and return min⁡{opt⁡r(0),opt⁡r(1)}\min\{\operatorname{opt}_r(0),\operatorname{opt}_r(1)\}.

Let vv be a cutvertex. For each child XX of vv, define weights on V(X)∖{v}V(X) \setminus\{v\} by wX(x)=opt⁡x(1)−opt⁡x(0)w_X(x) = \operatorname{opt}_x(1) - \operatorname{opt}_x(0) for x∈CXx \in C_X and wX(x)=w(x)w_X(x) = w(x) otherwise. We claim that for b∈{0,1}b \in\{0,1\}, we have

opt⁡v(b)=b⋅w(v)+∑X∈Cv(min⁡{wX(S∖{v}):S∈TX, χS(v)=b}+∑x∈CXopt⁡x(0)).\operatorname{opt}_v(b) = b \cdot w(v) + \sum_{X \in C_v} \left(\min\{w_X(S \setminus\{v\}) : S \in\mathcal{T}_X,\ \chi_S(v) = b\} + \sum_{x \in C_X} \operatorname{opt}_x(0)\right).

where TX\mathcal{T}_X denotes the set of all odd cycle transversals of XX and χS\chi_S denotes the characteristic vector of SS, i.e., χS(x)=1\chi_S(x) = 1 if x∈Sx \in S and χS(x)=0\chi_S(x) = 0 otherwise. To see the correctness, note that the blocks of GvG_v are the children of vv and the blocks of the graphs GxG_x. Hence, a set S⊆V(Gv)S \subseteq V(G_v) is an odd cycle transversal of GvG_v if and only if S∩V(X)S \cap V(X) is one of XX and S∩V(Gx)S \cap V(G_x) is one of GxG_x for all X∈CvX \in C_v and x∈CXx \in C_X. Further, V(Gv)V(G_v) is the disjoint union of {v}\{v\} and, for each X∈CvX \in C_v, the set V(X)∖(CX∪{v})V(X) \setminus(C_X \cup\{v\}) and the sets V(Gx)V(G_x) with x∈CXx \in C_X, and V(Gx)∩V(X)={x}V(G_x) \cap V(X) = \{x\}. Hence, given χS(v)=b\chi_S(v) = b, the sets S∩V(X)S \cap V(X) can be chosen independently for the children XX of vv, and once they are fixed, so can the sets S∩V(Gx)S \cap V(G_x), each optimally at cost opt⁡x(χS(x))=opt⁡x(0)+χS(x)⋅wX(x)\operatorname{opt}_x(\chi_S(x)) = \operatorname{opt}_x(0) + \chi_S(x) \cdot w_X(x). This proves the claim. Each of these minima can be computed by a weighted odd cycle transversal problem on XX, as the constraint χS(v)=b\chi_S(v) = b can be dropped by setting wX(v)=−1w_X(v) = -1 if b=1b = 1, so that adding vv to an odd cycle transversal not containing it yields one of smaller weight, and wX(v)=1+∑x∈NX(v)max⁡{0,wX(x)}w_X(v) = 1 + \sum_{x \in N_X(v)} \max\{0,w_X(x)\} if b=0b = 0, since then replacing vv by its neighbors in XX turns any odd cycle transversal containing vv into one of smaller weight. Thus, we obtain all values opt⁡v(b)\operatorname{opt}_v(b) by solving two odd cycle transversal problems per block. An optimal solution can be recovered by standard backtracking. □

By Lemma 4.2 and the remark following it, and Lemmas 4.3 and 4.4, we conclude that, for each fixed Δ\Delta, instances of the odd cycle transversal problem for which the coefficient matrix of (3) is totally Δ\Delta-modular can be solved in polynomial time.

An alternative common integer programming formulation of the odd cycle transversal problem is given by

min⁡∑v∈Vw(v)xvds.t.xvl+xvr+xvd=1∀v∈Vxvl+xul≤1∀{u,v}∈Exvr+xur≤1∀{u,v}∈Exvl,xvr,xvd∈{0,1}∀v∈V(4)\begin{aligned} \min\quad& \sum_{v\in V} w(v)x_{vd}\\ \text{s.t.}\quad& x_{vl}+x_{vr}+x_{vd}=1 && \forall v\in V\\ & x_{vl}+x_{ul}\le1 && \forall\{u,v\}\in E\\ & x_{vr}+x_{ur}\le1 && \forall\{u,v\}\in E\\ & x_{vl},x_{vr},x_{vd}\in\{0,1\} && \forall v\in V \tag*{(4)} \end{aligned}

where xvlx_{vl}, xvrx_{vr} and xvdx_{vd} indicate whether vv is assigned to the left side, assigned to the right side, or deleted, respectively.

Let Δ\Delta be fixed. We show that every instance of the odd cycle transversal problem for which the coefficient matrix of (4) is totally Δ\Delta-modular can be also solved in polynomial time. To this end, we make use of a result by Fiorini, Joret, Weltge, and Yuditsky [17] stating that totally Δ\Delta-modular integer programs with at most two variables per inequality can be solved in polynomial time. Note that the equality constraints in the above formulation imply xvd=1−xvl−xvrx_{vd}=1-x_{vl}-x_{vr} for each v∈Vv\in V. Substituting this in the objective and all constraints (including the bounds) yields an equivalent integer program with at most two variables per inequality. Its coefficient matrix is a submatrix of the coefficient matrix of (4), so it is totally Δ\Delta-modular if (4) is. Hence, we can apply [17] to obtain the claimed polynomial-time algorithm.

Interestingly, the two different formulations for the odd cycle transversal problem yield two incomparable graph classes when restricted to bounded subdeterminants. On the one hand, the disjoint union of kk odd cycles has a totally unimodular coefficient matrix with respect to (3), but has a subdeterminant of absolute value 4k4^{k} with respect to (4). On the other hand, the singly parity-breaking grid of order kk has a totally 44-modular coefficient matrix with respect to (4), but has subdeterminants of absolute value exponential in kk with respect to (3). This can be seen by Lemma 4.2 and the fact that the largest absolute value of a subdeterminant of the edge-vertex incidence matrix of a graph is equal to 2k2^{k}, where kk is the maximum number of vertex-disjoint odd cycles in the graph [22].

Dominating set

Given a graph G=(V,E)G=(V,E) and a weight function w:V→Qw:V\to\mathbb{Q}, the dominating set problem asks to find a subset D⊆VD\subseteq V of minimum weight such that every vertex in V∖DV\setminus D has a neighbor in DD. A natural integer programming formulation of the dominating set problem is given by

min⁡∑v∈Vw(v)xvs.t.xv+∑u∈N(v)xu≥1∀v∈Vxv∈{0,1}∀v∈V(5)\begin{aligned} \min\quad& \sum_{v\in V} w(v)x_v\\ \text{s.t.}\quad& x_v+\sum_{u\in N(v)}x_u\ge1 && \forall v\in V\\ & x_v\in\{0,1\} && \forall v\in V \tag*{(5)} \end{aligned}

where N(v)N(v) denotes the set of neighbors of vv in GG.

We start by fixing some notation needed for our argument. The kk-star is the complete bipartite graph with one part of size one and the other of size kk, the kk-net is the graph consisting of a clique of size kk and a disjoint independent set of size kk joined to the clique by a perfect matching, and the kk-prism is a graph consisting of two disjoint cliques of size kk joined by a perfect matching. See Figure 5.1 for an illustration. The 3-star is also known as the claw, and the 3-net as the net.

Figure 5.1. The kk-star, kk-net, and kk-prism for k=5k = 5.

For a collection of graphs H\mathcal{H}, we say that a graph GG is H\mathcal{H}-free if it does not contain any graph from H\mathcal{H} as an induced subgraph. Let HΔ\mathcal{H}_{\Delta} be the collection consisting of the (Δ+2)(\Delta+ 2)-star, (Δ+2)(\Delta+ 2)-net, (Δ+1)(\Delta+ 1)-prism, the disjoint union of tΔt_{\Delta} claws, and the disjoint union of tΔt_{\Delta} nets, where tΔ=⌈log⁡2Δ⌉+1t_{\Delta} = \lceil\log_{2}\Delta\rceil+ 1.

In the unweighted setting, Malyshev and Gribanov [28] proved polynomial-time solvability by showing that, after guessing a number of vertices depending only on Δ\Delta, the problem reduces to an instance on {claw,net}\{\mathrm{claw},\mathrm{net}\}-free graphs. The latter problem was shown to be solvable in polynomial time by Brandstädt and Dragan [5]. However, as the following proposition shows, this approach does not extend to the weighted case.

Proposition 5.1. The weighted version of the dominating set problem on {claw,net}\{\mathrm{claw},\mathrm{net}\}-free graphs is NP-hard.

Proof. Recall the NP-hard set cover problem: Given a set UU and a family F\mathcal{F} of subsets of UU, the set cover problem asks to find a minimum-size subfamily F′⊆F\mathcal{F}' \subseteq\mathcal{F} such that every element in UU is contained in at least one set in F′\mathcal{F}'.

To reduce an instance of set cover to a {claw,net}\{\mathrm{claw},\mathrm{net}\}-free instance of weighted dominating set, create a graph GG with vertex set U∪FU \cup\mathcal{F}, such that G[U]G[U] and G[F]G[\mathcal{F}] are cliques and there is an edge between u∈Uu \in U and F∈FF \in\mathcal{F} if and only if u∈Fu \in F. Assign each vertex in UU a weight of ∣U∣+1|U| + 1 and each vertex in F\mathcal{F} a weight of 1. Then a minimum weight dominating set of GG corresponds to a minimum size set cover of the original instance and the resulting graph is {claw,net}\{\mathrm{claw},\mathrm{net}\}-free, since it does not contain an independent set of size more than 2. □

While this shows restricting to {claw,net}\{\mathrm{claw},\mathrm{net}\}-free graphs is not sufficient, they still play an important role in our proof. For a vertex vv, let Nk(v)N_k(v) denote the set of vertices at distance exactly kk from vv. We use the following property of {claw,net}\{\mathrm{claw},\mathrm{net}\}-free graphs.

Lemma 5.2. Let HH be a {claw,net}\{\mathrm{claw},\mathrm{net}\}-free graph, k≥0k \ge0, and r∈V(H)r \in V(H). Then H[Nk(r)]H[N_k(r)] contains no independent set of size at least 3.

Proof. We prove the claim by induction on kk. For k=0k = 0, the claim is trivial. For k=1k = 1, the claim follows from the fact that HH is claw-free. Let k≥2k \ge2. First, consider any vertex u∈Nk−1(r)u \in N_{k-1}(r), assume that there are two non-adjacent vertices x,y∈N(u)∩Nk(r)x,y \in N(u) \cap N_k(r), and let zz be a neighbor of uu in Nk−2(r)N_{k-2}(r). Then {u,x,y,z}\{u,x,y,z\} induces a claw in HH. Therefore the set N(u)∩Nk(r)N(u) \cap N_k(r) is a clique. Now, assume for contradiction that H[Nk(r)]H[N_k(r)] contains an independent set {v1,v2,v3}\{v_1,v_2,v_3\} of size 3. Let uiu_i be a neighbor of viv_i in Nk−1(r)N_{k-1}(r) for i∈{1,2,3}i \in\{1,2,3\}. Since N(ui)∩Nk(r)N(u_i) \cap N_k(r) is a clique, the uiu_i must be pairwise distinct and uiu_i is adjacent to vjv_j if and only if i=ji=j. By the induction hypothesis, there is at least one edge among the uiu_i. Moreover, if there are exactly two edges, say {u1,u2}\{u_1,u_2\} and {u2,u3}\{u_2,u_3\}, then {u1,u2,u3,v2}\{u_1,u_2,u_3,v_2\} induces a claw in HH. If there are three edges, then {u1,u2,u3,v1,v2,v3}\{u_1,u_2,u_3,v_1,v_2,v_3\} induces a net in HH. It remains to consider the case that there is exactly one edge among the uiu_i, say {u1,u2}\{u_1,u_2\}. Let ww be a neighbor of u1u_1 in Nk−2(r)N_{k-2}(r). If ww is not adjacent to u2u_2, then {w,u1,u2,v1}\{w,u_1,u_2,v_1\} induces a claw in HH. If ww is adjacent to u2u_2 and k≥3k \ge3, pick a neighbor ss of ww in Nk−3(r)N_{k-3}(r). Then {s,w,u1,u2,v1,v2}\{s,w,u_1,u_2,v_1,v_2\} induces a net in HH. If ww is adjacent to u2u_2 and k=2k=2, then u3∈N1(r)=N(r)u_3 \in N_1(r)=N(r) and w=rw=r. In this case, {r,u1,u2,u3,v1,v2}\{r,u_1,u_2,u_3,v_1,v_2\} induces a net in HH. □

Moreover, Malyshev and Gribanov [28] observed the following.

Lemma 5.3 ([28 Lemma 1]). If the coefficient matrix of (5) is totally Δ\Delta-modular, then GG is HΔ\mathcal{H}_{\Delta}-free.

We will use this in combination with the notion of linear mim-width. Let G=(V,E)G=(V,E) be a graph. For disjoint sets A,B⊆VA,B \subseteq V of vertices, let G[A,B]G[A,B] denote the bipartite graph with vertex set A∪BA \cup B and edge set {{a,b}∈E:a∈A and b∈B}\{\{a,b\} \in E : a \in A \text{ and } b \in B\}. For A⊆VA \subseteq V, mim⁡G(A)\operatorname{mim}_G(A) denotes the maximum size of an induced matching in G[A,V∖A]G[A,V \setminus A]. A linear ordering of GG is a permutation of VV. The mim-width of a linear ordering (v1,…,vn)(v_1,\ldots,v_n) of GG is defined as max⁡1≤i≤n{mim⁡G({v1,…,vi})}\max_{1 \le i \le n}\{\operatorname{mim}_G(\{v_1,\ldots,v_i\})\}. The linear mim-width of GG is the minimum mim-width over all linear orderings of GG.

Further, we write R(s,t)R(s,t) for the minimum integer NN such that every graph on NN vertices contains either an independent set of size ss or a clique of size tt. The classical theorem of Ramsey [32] implies that R(s,t)R(s,t) exists.

Lemma 5.4. The linear mim-width of an HΔ\mathcal{H}_{\Delta}-free graph is at most

f(Δ)=R(10⌈log⁡2Δ⌉(Δ+1)+5,R(Δ+2,Δ+1))−1.f(\Delta)=R(10\lceil\log_2\Delta\rceil(\Delta+1)+5,R(\Delta+2,\Delta+1))-1.

Moreover, a linear ordering with mim-width at most f(Δ)f(\Delta) can be found in polynomial time.

Proof. Let P\mathcal{P} be a maximal packing of induced subgraphs in GG, each isomorphic to the claw or the net, such that there is no edge between distinct members of P\mathcal{P}. Note that such a packing P\mathcal{P} can be found greedily in polynomial time. Set P=⋃Q∈PV(Q)P=\bigcup_{Q\in\mathcal{P}}V(Q). Since GG is HΔ\mathcal{H}_{\Delta}-free, P\mathcal{P} contains at most (tΔ−1)(t_{\Delta}-1) claws (with 4 vertices each) and at most (tΔ−1)(t_{\Delta}-1) nets (with 6 vertices each) and hence ∣P∣≤10(tΔ−1)|P| \le10(t_{\Delta}-1). Let K1,…,KtK_1,\ldots,K_t be the connected components of G[V∖N[P]]G[V \setminus N[P]]. For each i∈[t]i \in[t], let rir_i be an arbitrary vertex in KiK_i. Consider the linear ordering of GG obtained by first taking an arbitrary ordering of N[P]N[P] and then appending, for each connected component KiK_i in order of increasing index, all vertices of KiK_i in order of non-decreasing distance from rir_i in KiK_i. The indexing of the connected components KiK_i and the order of the vertices within KiK_i with the same distance from rir_i can be chosen arbitrarily. Note that such an ordering can be computed in polynomial time. We claim that this ordering witnesses that GG has linear mim-width at most R(∣P∣(Δ+1)+5,R(Δ+2,Δ+1))−1≤R(10⌈log⁡2Δ⌉(Δ+1)+5,R(Δ+2,Δ+1))−1R(|P|(\Delta+1)+5,R(\Delta+2,\Delta+1))-1 \le R(10\lceil\log_2\Delta\rceil(\Delta+1)+5,R(\Delta+2,\Delta+1))-1.

To this end, let SS be a prefix of the ordering and let {{a1,b1},…,{aℓ,bℓ}}\{\{a_1,b_1\},\ldots,\{a_\ell,b_\ell\}\} denote a maximum induced matching in G[S,V∖S]G[S,V\setminus S] with A={a1,…,aℓ}⊆SA=\{a_1,\ldots,a_\ell\}\subseteq S and B={b1,…,bℓ}⊆V∖SB=\{b_1,\ldots,b_\ell\}\subseteq V\setminus S. Let α(Q)\alpha(Q) and ω(Q)\omega(Q) denote the size of a maximum independent set and a maximum clique in a graph QQ, respectively. To prove the claim, it suffices to show that α(G[A])≤∣P∣(Δ+1)+4\alpha(G[A])\le|P|(\Delta+1)+4 and ω(G[A])≤R(Δ+2,Δ+1)−1\omega(G[A])\le R(\Delta+2,\Delta+1)-1.

Note that

α(G[A])≤α(G[A∩N[P]])+α(G[A∖N[P]])≤∑v∈Pα(G[N[v]])+α(G[A∖N[P]]).\alpha(G[A])\le\alpha(G[A\cap N[P]])+\alpha(G[A\setminus N[P]])\le\sum_{v\in P}\alpha(G[N[v]])+\alpha(G[A\setminus N[P]]).

Since GG does not contain a (Δ+2)(\Delta+2)-star as an induced subgraph, α(G[N[v]])≤Δ+1\alpha(G[N[v]])\le\Delta+1 for each v∈Pv\in P. By the construction of the ordering, either S∖N[P]S\setminus N[P] is empty, in which case α(G[A∖N[P]])=0\alpha(G[A\setminus N[P]])=0, or N[P]⊆SN[P]\subseteq S which means B⊆V∖N[P]B\subseteq V\setminus N[P]. In the latter case, let j∗j^* be the maximal index of a connected component Kj∗K_{j^*} such that A∩V(Kj∗)≠∅A\cap V(K_{j^*})\ne\varnothing and let k∗k^* be the maximal distance in Kj∗K_{j^*} from rj∗r_{j^*} to any vertex in A∩V(Kj∗)A\cap V(K_{j^*}). Then, for any a∈A∖N[P]a\in A\setminus N[P] and its matched vertex b∈Bb\in B, both aa and bb must be in Kj∗K_{j^*} and the distance from rj∗r_{j^*} to aa must be k∗k^* or k∗−1k^*-1. By the definition of PP, the graph G[V∖N[P]]G[V\setminus N[P]] is {claw,net}\{\text{claw},\text{net}\}-free. Hence, by Lemma 5.2, we have that α(G[A∖N[P]])≤2⋅2\alpha(G[A\setminus N[P]])\le2\cdot2 since A∖N[P]A\setminus N[P] intersects at most two layers. Altogether, we have α(G[A])≤∣P∣(Δ+1)+4\alpha(G[A])\le|P|(\Delta+1)+4.

To show that ω(G[A])≤R(Δ+2,Δ+1)−1\omega(G[A])\le R(\Delta+2,\Delta+1)-1, assume for contradiction that G[A]G[A] contains a clique of size R(Δ+2,Δ+1)R(\Delta+2,\Delta+1) with vertex set A′A'. Let B′B' be the set of vertices matched to A′A' in the induced matching. By the definition of R(Δ+2,Δ+1)R(\Delta+2,\Delta+1), G[B′]G[B'] contains either an independent set of size Δ+2\Delta+2 or a clique of size Δ+1\Delta+1. Denote the vertex set of the independent set, respectively the clique, by B′′B'' and let A′′⊆A′A''\subseteq A' denote the set of vertices that are matched to vertices in B′′B''. Then, A′′∪B′′A''\cup B'' induces a (Δ+2)(\Delta+2)-net if B′′B'' induces an independent set, and a (Δ+1)(\Delta+1)-prism if B′′B'' induces a clique, contradicting the fact that GG is HΔH_\Delta-free. We conclude that ω(G[A])≤R(Δ+2,Δ+1)−1\omega(G[A])\le R(\Delta+2,\Delta+1)-1.

Bui-Xuan, Telle, and Vatshelle [6] showed that on graphs with bounded mim-width unweighted dominating set can be solved in polynomial time, provided that a branch decomposition of bounded mim-width is given as part of the input, and noted that the same framework can be used for the weighted case with only minor modifications and without affecting the running time. Since a linear ordering can be transformed in linear time into a caterpillar branch decomposition of the same mim-width, their result also yields a polynomial-time algorithm for the weighted dominating set problem given a linear ordering of bounded mim-width.

Thus, by Lemmas 5.3 and 5.4, instances of the weighted dominating set problem for which the coefficient matrix of (5) is totally Δ\Delta-modular can be solved in polynomial time for each fixed Δ\Delta.

Induced matching

Given a graph G=(V,E)G=(V,E) and a weight function w:E→Qw:E\to\mathbb{Q}, the maximum induced matching problem asks for a subset M⊆EM\subseteq E of maximum weight such that MM is a matching and the graph induced by all endpoints of edges in MM has no edges other than MM. There is a natural integer programming formulation of the maximum induced matching problem based on the line graph L(G)L(G) of GG. Recall that L(G)L(G) is the graph with vertex set EE in which e,f∈Ee, f \in E are adjacent if and only if they share a common endpoint in GG. Then, the maximum induced matching problem has the following integer programming formulation:

max⁡∑e∈Ew(e)xes.t.xe+∑f∈NL(G)(e)xf≤1∀e∈Exe∈{0,1}∀e∈E(6)\begin{aligned} \max\quad& \sum_{e\in E} w(e)x_e\\ \text{s.t.}\quad& x_e+\sum_{f\in N_{L(G)}(e)}x_f\le1 && \forall e\in E\\ & x_e\in\{0,1\} && \forall e\in E \tag*{(6)} \end{aligned}

Lemma 6.1. If the coefficient matrix of (6) is totally Δ\Delta-modular, then the pathwidth of GG is at most 7⌈log⁡2Δ⌉+57\lceil\log_2\Delta\rceil+5.

Proof. Let HH denote the 11-subdivided claw, i.e., the graph obtained from the claw by subdividing each edge exactly once and let FF denote the disjoint union of ⌈log⁡2Δ⌉+1\lceil\log_2\Delta\rceil+1 copies of HH. Note that L(H)L(H) is a net and that if GG contains FF as a subgraph, then L(G)L(G) contains the disjoint union of ⌈log⁡2Δ⌉+1\lceil\log_2\Delta\rceil+1 nets as an induced subgraph. Moreover, observe that the coefficient matrix of (6) is the same as the coefficient matrix of (5) for the graph L(G)L(G). By Lemma 5.3, if the coefficient matrix of (6) is totally Δ\Delta-modular, then L(G)L(G) does not contain the disjoint union of ⌈log⁡2Δ⌉+1\lceil\log_2\Delta\rceil+1 nets as an induced subgraph and hence, by the argument above, GG does not contain FF as a subgraph.

Finally, since FF has maximum degree 3, if GG contains FF as a minor, then it also contains a subdivision of FF as a subgraph (see [13 Proposition 1.7.3]). Since every subdivision of HH contains HH as a subgraph, we conclude that GG does not contain the forest FF as a minor. By a result of Bienstock, Robertson, Seymour, and Thomas [3], this implies that the pathwidth of GG is at most ∣V(F)∣−2=7⌈log⁡2Δ⌉+5|V(F)|-2=7\lceil\log_2\Delta\rceil+5. □

By the algorithm of Dallard, Milanič, and Štorgel [11 Corollary 7.4] for weighted maximum independent packing, the weighted maximum induced matching problem can be solved in polynomial time on graphs of bounded pathwidth. We conclude that, for any fixed Δ\Delta, totally Δ\Delta-modular instances of the induced matching problem can be solved in polynomial time.

Cluster vertex deletion

As already mentioned before, integer programs with at most two non-zero entries per row and bounded subdeterminants can be solved in polynomial time [17]. A natural follow-up question is whether this result can be extended to integer programs with a bounded number of non-zero entries per row. In this section, we will consider a problem which naturally falls into the case of at most three non-zero entries per row, namely the cluster vertex deletion problem.

Given a graph G=(V,E)G=(V,E) and a weight function w:V→Qw:V\to\mathbb{Q}, the cluster vertex deletion problem asks to find a subset S⊆VS\subseteq V of minimum weight such that G−SG-S is a cluster graph (a disjoint union of cliques). Here and in the following, G−SG-S denotes the induced subgraph of GG on the vertex set V(G)∖SV(G) \setminus S. It is not difficult to see that a graph is a cluster graph if and only if it does not contain an induced P3P_3, where PmP_m denotes the path on mm vertices. This yields the following integer programming formulation.

min⁡∑v∈Vw(v)xvs.t.xa+xb+xc≥1∀{a,b,c}∈Pxv∈{0,1}∀v∈V(7)\begin{aligned} \min\quad& \sum_{v\in V} w(v)x_v\\ \text{s.t.}\quad& x_a+x_b+x_c\ge1 && \forall\{a,b,c\}\in\mathcal{P}\\ & x_v\in\{0,1\} && \forall v\in V \tag*{(7)} \end{aligned}

where P\mathcal{P} is the set of all {a,b,c}⊆V\{a,b,c\}\subseteq V such that G[{a,b,c}]G[\{a,b,c\}] is isomorphic to P3P_3, and xvx_v indicates whether the vertex vv is included in the cluster vertex deletion set.

An induced cycle of length at least four is called a hole. A graph is chordal if it does not contain any holes. The following lemma shows a connection between the cluster vertex deletion problem and chordal graphs.

Lemma 7.1. There exists a computable function ff such that, if the coefficient matrix of (7) is totally Δ\Delta-modular, then there exists a set X⊆VX\subseteq V with ∣X∣≤f(Δ)|X|\le f(\Delta) such that G−XG-X is chordal.

Proof. We claim that any hole corresponds to a submatrix with determinant of absolute value at least 22 and that for multiple holes, they combine to form a block diagonal matrix. This implies that GG has at most ⌊log⁡2Δ⌋\lfloor\log_2\Delta\rfloor vertex-disjoint holes and, by the Erdős–Pósa theorem for holes [23, 25], we conclude that there is a set X⊆VX\subseteq V of size at most f(Δ)f(\Delta) such that G−XG-X is chordal for some computable function ff.

It remains to show that any hole corresponds to a submatrix with determinant of absolute value at least 22. To this end, note that a sequence r0,…,rℓ−1r_0,\ldots,r_{\ell-1} of induced P3P_3’s in the path PmP_m with a sequence c0,c1,…,cℓc_0,c_1,\ldots,c_\ell of vertices such that rir_i contains exactly two of the cjc_j’s, namely cic_i and ci+1c_{i+1}, for all i∈{0,…,ℓ−1}i\in\{0,\ldots,\ell-1\} and where c0c_0 is the first vertex of the path and cℓc_\ell is the last vertex of the path gives rise to ℓ\ell induced P3P_3’s in a hole of length m−1m-1 and ℓ\ell vertices in the hole by identifying c0c_0 and cℓc_\ell. Moreover, the corresponding submatrix is the incidence matrix of a cycle of length ℓ\ell, which has determinant of absolute value 22 if ℓ\ell is odd. Therefore, it suffices to show that for any m≥5m\ge5, there exist sequences as described above for PmP_m with ℓ\ell odd. We can give these sequences explicitly depending on the residue rr of mm modulo 44 (see also the illustration in Figure 7.1):

Figure 7.1. Illustration of the proof of Lemma 7.1. The shaded regions represent the selected induced P3P_3's and the black vertices are the selected vertices.

r=1r=1: {1,2,3}\{1,2,3\}, {2,3,4}\{2,3,4\}, {3,4,5}\{3,4,5\}, and {5,6,7}\{5,6,7\}, {7,8,9}\{7,8,9\}, …\ldots, {m−2,m−1,m}\{m-2,m-1,m\}; 1,2,4,51,2,4,5, and 7,9,…,m7,9,\ldots,m

r=2r=2: {1,2,3}\{1,2,3\}, {2,3,4}\{2,3,4\}, {4,5,6}\{4,5,6\}, and {6,7,8}\{6,7,8\}, {8,9,10}\{8,9,10\}, …\ldots, {m−2,m−1,m}\{m-2,m-1,m\}; 1,2,4,61,2,4,6, and 8,10,…,m8,10,\ldots,m

r=3r=3: {1,2,3}\{1,2,3\}, {3,4,5}\{3,4,5\}, {5,6,7}\{5,6,7\}, and {7,8,9}\{7,8,9\}, {9,10,11}\{9,10,11\}, …\ldots, {m−2,m−1,m}\{m-2,m-1,m\}; 1,3,5,71,3,5,7, and 9,11,…,m9,11,\ldots,m

r=0r=0: {1,2,3}\{1,2,3\}, {2,3,4}\{2,3,4\}, {3,4,5}\{3,4,5\}, {5,6,7}\{5,6,7\}, {6,7,8}\{6,7,8\}, and {8,9,10}\{8,9,10\}, {10,11,12}\{10,11,12\}, …\ldots, {m−2,m−1,m}\{m-2,m-1,m\}; 1,2,4,5,7,81,2,4,5,7,8, and 10,12,…,m10,12,\ldots,m

Here, each case starts with a construction for 55, 66, 77 or 88 vertices and then extends the construction to mm by appending pairs of induced P3P_3’s which intersect in their endpoints.

Clearly, for pairwise vertex-disjoint holes the submatrices combine to form a block diagonal matrix.

Lemma 7.2. For any fixed kk, if there exists a set XX of at most kk vertices such that G−XG-X is chordal, then the cluster vertex deletion problem can be reduced to a polynomial number of cluster vertex deletion problems on chordal graphs.

Proof. By assumption there is a set XX of at most kk vertices such that G−XG-X is chordal. Since it is possible to recognize chordal graphs in linear time [34], we can find such a set XX in polynomial time.

Our algorithm will work by guessing some part of the solution such that the remaining instance is chordal and such that there is a polynomial number of possible guesses. To this end, let Y∗Y^* be an optimal solution and let Y=Y∗∩XY=Y^*\cap X.

Clearly, YY hits all induced P3P_3's that lie completely in XX. Moreover, let ZYZ_Y be the set of vertices z∈V∖Xz\in V\setminus X such that there is an induced P3P_3 with zz as an endpoint and the other two vertices in X∖YX\setminus Y. Then Y∗Y^* must contain ZYZ_Y. Further, let Nx=NG(x)∖XN_x=N_G(x)\setminus X for each x∈X∖Yx\in X\setminus Y where NG(x)N_G(x) is the neighborhood of xx in GG. Observe that if z1,z2∈Nxz_1,z_2\in N_x are non-adjacent in GG, then z1,x,z2z_1,x,z_2 is an induced P3P_3 of GG. Hence, Y∗Y^* must contain z1z_1 or z2z_2. In other words, Y∗Y^* contains a vertex cover of G[Nx]‾\overline{G[N_x]} (and thus also an inclusion-wise minimal vertex cover), where G‾\overline{G} is the complement of GG.

We can therefore guess YY and a minimal vertex cover ZxZ_x of G[Nx]‾\overline{G[N_x]} for each x∈X∖Yx\in X\setminus Y. For each such guess we consider the remaining instance G′=G−(Y∪ZY∪⋃x∈X∖YZx)G'=G-(Y\cup Z_Y\cup\bigcup_{x\in X\setminus Y}Z_x). For Y=Y∗∩XY=Y^*\cap X, it holds that G′G' is chordal: Clearly, G′−XG'-X is chordal since it is an induced subgraph of G−XG-X. Thus, if G′G' contains a hole, it must contain a vertex x∈X∩V(G′)=X∖Yx\in X\cap V(G')=X\setminus Y with two non-adjacent neighbors z1,z2∈V(G′)z_1,z_2\in V(G'). However, we cannot have z1,z2∈Xz_1,z_2\in X, since YY hits all induced P3P_3's that lie completely in XX. Further, we cannot have z1,z2∈V(G′)∖Xz_1,z_2\in V(G')\setminus X, since ZxZ_x is a vertex cover of G[Nx]‾\overline{G[N_x]}. Lastly, we cannot have that one of z1,z2z_1,z_2 is in XX and the other in V(G′)∖XV(G')\setminus X, since then the other is in ZYZ_Y. Consequently, G′G' is chordal. We can therefore check for each guess whether the remaining instance G′G' is chordal and, if so, solve the cluster vertex deletion problem on G′G'. For the correct guess of YY and the corresponding ZxZ_x, taking the union of the solution on G′G' with Y∪ZY∪⋃x∈X∖YZxY\cup Z_Y\cup\bigcup_{x\in X\setminus Y}Z_x yields an optimal solution. Thus, enumerating all guesses and returning the best solution among them yields an optimal solution for the original instance.

There are only 2k2^k guesses for YY since ∣X∣≤k|X| \le k. Moreover, note that a minimal vertex cover ZxZ_x of G[Nx]G[N_x] corresponds to a maximal clique KK of G[Nx]G[N_x] via Zx=Nx∖KZ_x = N_x \setminus K. Further, since G[Nx]G[N_x] is a chordal graph as an induced subgraph of G−XG-X, G[Nx]G[N_x] contains at most ∣Nx∣|N_x| maximal cliques, and all maximal cliques of G[Nx]G[N_x] can be enumerated efficiently [20]. Thus, all minimal vertex covers of G[Nx]G[N_x] can be enumerated efficiently. Since we only have to guess ∣X∖Y∣≤∣X∣|X \setminus Y| \le|X| many ZxZ_x, we can enumerate all guesses jointly in polynomial time.

By Lemmas 7.1 and 7.2, and a recent result of Cao and Li [7] who show that the cluster vertex deletion problem can be solved in polynomial time on chordal graphs, we can solve the cluster vertex deletion problem in polynomial time on instances where the coefficient matrix of the formulation (7) is totally Δ\Delta-modular for any constant Δ\Delta.

Traveling salesman problem

The traveling salesman problem asks to find a cycle of minimum cost that visits each vertex exactly once in a given graph G=(V,E)G = (V,E) with edge costs c:E→Qc : E \to\mathbb{Q}. Several prominent integer programming formulations can be found in the literature. First, we want to mention the formulation by Miller, Tucker, and Zemlin [29], which contains ∣V∣|V| as a coefficient in the coefficient matrix. Similarly, the flow-based formulation by Gavish and Graves [19] contains ∣V∣−1|V| - 1 as a coefficient in the coefficient matrix. Therefore, these formulations are totally Δ\Delta-modular only for graphs with at most Δ\Delta, respectively Δ+1\Delta+ 1 vertices.

More interesting are the formulations proposed by Dantzig, Fulkerson, and Johnson [12]. We denote by δ(S)\delta(S) the set of edges with exactly one endpoint in SS and define δ(v)=δ({v})\delta(v) = \delta(\{v\}). Both formulations share the constraints

min⁡∑e∈Ec(e)xes.t.∑e∈δ(v)xe=2∀v∈Vxe∈{0,1}∀e∈E(8)\begin{aligned} \min\quad& \sum_{e \in E} c(e)x_e\\ \text{s.t.}\quad& \sum_{e \in\delta(v)} x_e = 2 && \forall v \in V\\ & x_e \in\{0,1\} && \forall e \in E \tag*{(8)} \end{aligned}

where xex_e indicates whether the edge ee is included in the cycle. The first formulation has (8) and the additional constraints

∑e∈δ(S)xe≥2∀∅≠S⊊V,(9)\sum_{e \in\delta(S)} x_e \ge2 \qquad\forall\varnothing\ne S \subsetneq V, \tag*{(9)}

the second has (8) and the additional constraints

∑e∈E(S)xe≤∣S∣−1∀∅≠S⊊V,(10)\sum_{e \in E(S)} x_e \le|S| - 1 \qquad\forall\varnothing\ne S \subsetneq V, \tag*{(10)}

where E(S)E(S) denotes the set of edges with both endpoints in SS. Note that (9) and (10) are equivalent in the sense that one arises from the other by adding, respectively subtracting, some constraints of (8), and dividing by 2. However, this operation does not preserve subdeterminants, and therefore the two formulations are not directly equivalent in the context of total Δ\Delta-modularity.

Lemma 8.1. If the coefficient matrix of (8) and (9), respectively of (8) and (10), is totally Δ\Delta-modular, then any cycle in GG has length at most max⁡{4,4log⁡2Δ+3}\max\{4, 4\log_2\Delta+3\}.

Proof. Assume GG contains a cycle CC of length ℓ≥5\ell\ge5. Denote the vertices of the cycle by V(C)={v0,…,vℓ−1}V(C)=\{v_0,\ldots,v_{\ell-1}\} and the edges by ei={vi,vi+1}e_i=\{v_i,v_{i+1}\} for i∈{0,…,ℓ−1}i\in\{0,\ldots,\ell-1\}, where the indices are taken modulo ℓ\ell.

Consider the submatrix that selects the columns corresponding to the edges ea,ea+1,ea+3e_a,e_{a+1},e_{a+3} for a∈{0,4,…,4(⌊ℓ/4⌋−1)}a\in\{0,4,\ldots,4(\lfloor\ell/4\rfloor-1)\} and three rows for each such aa. We claim that for a suitable choice of the rows, the resulting submatrix is a block-diagonal matrix with one block of determinant 22 for each aa. First, select the row from (8) corresponding to the degree constraint of va+1v_{a+1}, then for (9) additionally select the rows corresponding to S={va+2,va+3}S=\{v_{a+2},v_{a+3}\} and to S={va+1,va+2,va+3}S=\{v_{a+1},v_{a+2},v_{a+3}\}, respectively for (10) additionally select the rows corresponding to S={va+1,…,va+4}S=\{v_{a+1},\ldots,v_{a+4}\} and to S={va,va+1,va+3,va+4}S=\{v_a,v_{a+1},v_{a+3},v_{a+4}\}.

Since ℓ≥5\ell\ge5, the rows selected for aa have support in ea,ea+1,ea+3e_a,e_{a+1},e_{a+3} when restricted to the selected columns, so the resulting submatrix is block-diagonal and each block is equal to

(110011101)\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}

which has determinant 22. We conclude that 2⌊ℓ/4⌋≤Δ2^{\lfloor\ell/4\rfloor}\le\Delta which implies that ℓ≤4log⁡2Δ+3\ell\le4\log_2\Delta+3.

By Lemma 8.1, any feasible instance of the traveling salesman problem with a totally Δ\Delta-modular coefficient matrix with regard to either of the formulations by Dantzig, Fulkerson, and Johnson has at most max⁡{4,4log⁡2Δ+3}\max\{4,4\log_2\Delta+3\} vertices. Therefore, for any fixed Δ\Delta, the traveling salesman problem can be solved in polynomial time by brute force on such instances.

Finally, Claus [8] proposed a formulation which is based on the idea of considering the directed graph D=(V,A)D=(V,A) obtained from GG by replacing each edge {u,v}∈E\{u,v\}\in E by the two arcs (u,v),(v,u)∈A(u,v),(v,u)\in A, defining the cost of each arc (u,v)∈A(u,v)\in A as c(u,v)=c(v,u)=c({u,v})c(u,v)=c(v,u)=c(\{u,v\}), and finding a directed cycle of minimum cost that visits each vertex exactly once in DD. The formulation selects an arbitrary vertex s∈Vs\in V as a source and is given by

min⁡∑a∈Ac(a)xas.t.∑a∈δ+(v)xa=1∀v∈V∑a∈δ−(v)xa=1∀v∈Vyat−xa≤0∀a∈A,t∈V∖{s}∑a∈δ+(v)yat−∑a∈δ−(v)yat=bvt∀v∈V,t∈V∖{s}xa∈{0,1}∀a∈Ayat∈{0,1}∀a∈A,t∈V∖{s}(11)\begin{aligned} \min\quad&\sum_{a\in A}c(a)x_a\\ \text{s.t.}\quad&\sum_{a\in\delta^+(v)}x_a=1 &&\forall v\in V\\ &\sum_{a\in\delta^-(v)}x_a=1 &&\forall v\in V\\ &y_a^t-x_a\le0 &&\forall a\in A,t\in V\setminus\{s\}\\ &\sum_{a\in\delta^+(v)}y_a^t-\sum_{a\in\delta^-(v)}y_a^t=b_v^t &&\forall v\in V,t\in V\setminus\{s\}\\ &x_a\in\{0,1\} &&\forall a\in A\\ &y_a^t\in\{0,1\} &&\forall a\in A,t\in V\setminus\{s\} \tag*{(11)} \end{aligned}

where bst=1b_s^t=1, btt=−1b_t^t=-1, and bvt=0b_v^t=0 for all v∈V∖{s,t}v\in V\setminus\{s,t\}, and δ+(v)\delta^+(v) and δ−(v)\delta^-(v) denote the sets of outgoing and incoming arcs of vv, respectively. In the formulation, xax_a indicates whether the arc aa is included in the cycle and ft:A→{0,1}f_t: A \to\{0,1\}, ft(a)=yatf_t(a) = y_a^t is a unit flow from ss to tt for each t∈V∖{s}t \in V \setminus\{s\}.

Lemma 8.2. If the coefficient matrix of (11) is totally Δ\Delta-modular, then any cycle in GG has length at most 2log⁡2Δ+12\log_2 \Delta+ 1.

Proof. We refer to the constraint families (in the order they appear in (11)) as the outdegree constraints, the indegree constraints, the coupling constraints, and the flow conservation constraints.

Assume GG contains a cycle CC of length ℓ\ell. Label the vertices of the cycle by v0,…,vℓ−1v_0,\ldots,v_{\ell-1} in cyclic order. Since AA contains both orientations of every edge of GG, the arcs (vi,vi+1)(v_i,v_{i+1}) and (vi+1,vi)(v_{i+1},v_i) are contained in AA for all ii. Moreover, since ∣V∣≥ℓ≥3|V| \ge\ell\ge3, we can fix two distinct vertices t1,t2∈V∖{s}t_1,t_2 \in V \setminus\{s\}.

Consider the submatrix that selects the columns corresponding to the variables x(vi−1,vi)x_{(v_{i-1},v_i)}, x(vi,vi+1)x_{(v_i,v_{i+1})}, x(vi,vi−1)x_{(v_i,v_{i-1})}, y(vi−1,vi)t1y_{(v_{i-1},v_i)}^{t_1}, y(vi,vi+1)t1y_{(v_i,v_{i+1})}^{t_1}, y(vi−1,vi)t2y_{(v_{i-1},v_i)}^{t_2}, y(vi,vi−1)t2y_{(v_i,v_{i-1})}^{t_2} for i∈{0,2,…,2(⌊ℓ/2⌋−1)}i \in\{0,2,\ldots,2(\lfloor\ell/2 \rfloor-1)\} and seven rows for each such ii. We claim that for a suitable choice of the rows, the resulting submatrix is a block-diagonal matrix with one block of determinant 2 for each ii. For each ii, select the row corresponding to the outdegree constraint of viv_i, the rows corresponding to the coupling constraints for ((vi−1,vi),t1)((v_{i-1},v_i),t_1), ((vi,vi+1),t1)((v_i,v_{i+1}),t_1), ((vi−1,vi),t2)((v_{i-1},v_i),t_2) and ((vi,vi−1),t2)((v_i,v_{i-1}),t_2), and the rows corresponding to the flow conservation constraints for (vi,t1)(v_i,t_1) and (vi,t2)(v_i,t_2). Each of these rows has nonzero entries only in variables of arcs incident to viv_i, and each column selected for ii corresponds to an arc of CC incident to viv_i. Since no two of the vertices viv_i are adjacent in CC, this means the resulting submatrix is block-diagonal and, with rows and columns ordered as listed above, each block is equal to

(0110000−10010000−100100−100001000−10001000−110000000−11)\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 & 1 \end{pmatrix}

which has determinant 2. We conclude that 2⌊ℓ/2⌋≤Δ2^{\lfloor\ell/2 \rfloor} \le\Delta which implies that ℓ≤2log⁡2Δ+1\ell\le2\log_2 \Delta+ 1.

By Lemma 8.2, any feasible instance of the traveling salesman problem with a totally Δ\Delta-modular coefficient matrix with regard to (11) has at most 2log⁡2Δ+12\log_2 \Delta+ 1 vertices and can thus be solved in polynomial time by brute force.

2-constraint satisfaction problem

We consider the Boolean version of the 2-constraint satisfaction problem in the weighted optimization variant (max 2-CSP). An instance consists of a finite set of variables XX, a finite set CC of clauses, each of the form ((x,y),P)((x,y),P) with distinct x,y∈Xx,y \in X and a predicate P:{0,1}2→{0,1}P:\{0,1\}^2 \to\{0,1\}, and a weight function w:C→Q≥0w:C \to\mathbb{Q}_{\ge0}. The problem then asks for an assignment σ:X→{0,1}\sigma:X \to\{0,1\} that maximizes the total weight of the satisfied clauses, where a clause ((x,y),P)((x,y),P) is satisfied by σ\sigma if P(σ(x),σ(y))=1P(\sigma(x),\sigma(y))=1.

For a predicate PP, we define QP=conv⁡{(x,y,z)∈{0,1}3:z≤P(x,y)}Q_P = \operatorname{conv}\{(x,y,z) \in\{0,1\}^{3}: z \le P(x,y)\}. Up to replacing xx by (1−x)(1-x) or yy by (1−y)(1-y), every predicate is of one of the following four types: AND (P(x,y)=x∧yP(x,y)=x \wedge y), OR (P(x,y)=x∨yP(x,y)=x \vee y), XOR (P(x,y)=x⊕yP(x,y)=x \oplus y) or affine (P(x,y)P(x,y) is an affine function over R\mathbb{R} of xx and yy). Note that in the affine case, PP is either constant or equal to xx or yy, up to negation. For each of these, we can give a description of QPQ_P by linear inequalities, which are given by the bounds 0≤x,y,z≤10 \le x,y,z \le1 and

AND:z−x≤0,z−y≤0,OR:z−x−y≤0,XOR:z−x−y≤0,z+x+y≤2,affine:z−P(x,y)≤0.(12)\begin{aligned} \text{AND:}\quad&z-x \le0,\quad z-y \le0, &\text{OR:}\quad&z-x-y \le0,\\ \text{XOR:}\quad&z-x-y \le0,\quad z+x+y \le2, &\text{affine:}\quad&z-P(x,y) \le0. \tag*{(12)} \end{aligned}

With this notation, max 2-CSP can be formulated as the following integer program, where the containment in QPQ_P is expressed by the inequalities above, with (1−x)(1-x) and (1−y)(1-y) substituted for xx and yy appropriately.

max⁡∑c∈Cw(c)zcs.t.(x,y,zc)∈QP∀c=((x,y),P)∈Cx∈{0,1}∀x∈Xzc∈{0,1}∀c∈C(13)\begin{aligned} \max\quad&\sum_{c\in C} w(c)z_c\\ \text{s.t.}\quad&(x,y,z_c)\in Q_P &&\forall c=((x,y),P)\in C\\ &x\in\{0,1\} &&\forall x\in X\\ &z_c\in\{0,1\} &&\forall c\in C \tag*{(13)} \end{aligned}

Max 2-CSP includes max 2-SAT, max cut, and directed max cut as special cases. Further, the formulation (13) generalizes these problems on the level of integer programming, i.e., specializing it to the respective problems yields a natural integer programming formulation for each of them.

For a first structural result, we examine the set X⊕⊆XX_{\oplus} \subseteq X of variables that appear in XOR clauses. To this end, let GG be the (multi)graph with vertex set X⊕X_{\oplus} that has an edge {x,y}\{x,y\} for each XOR clause ((x,y),P)∈C((x,y),P)\in C, where we identify each edge with the corresponding clause. Note that, as in the classification above, XOR clauses include clauses in which xx or yy appear negated.

Lemma 9.1. If the coefficient matrix of (13) is totally Δ\Delta-modular, then ∣X⊕∣≤2log⁡2Δ|X_{\oplus}| \le2\log_2\Delta.

Proof. First, consider the case that GG is connected and let TT be a spanning tree of GG. Let v1,…,vnv_1,\ldots,v_n be an ordering of the vertices of TT and let e1,…,en−1e_1,\ldots,e_{n-1} be an ordering of the edges of TT such that Ti=({v1,…,vi},{e1,…,ei−1})T_i=(\{v_1,\ldots,v_i\},\{e_1,\ldots,e_{i-1}\}) is a connected subtree of TT for all 2≤i≤n2\le i\le n. We now iteratively construct a submatrix AiA_i of the coefficient matrix with ∣det⁡(Ai)∣=2i−1|\det(A_i)|=2^{i-1} for i=2,…,ni=2,\ldots,n.

For i=2i=2, let A2A_2 be the submatrix whose rows correspond to the two constraints in (12) of the clause e1={v1,v2}e_1=\{v_1,v_2\} and whose columns correspond to the variables ze1z_{e_1} and v2v_2. Then, up to flipping the signs in the second column if v2v_2 appears negated in e1e_1, we have

A2=(1−111),A_2=\begin{pmatrix}1&-1\\1&1\end{pmatrix},

and, in any case, ∣det⁡(A2)∣=2|\det(A_2)|=2.

For i>2i>2, let AiA_i arise from Ai−1A_{i-1} by additionally selecting the rows corresponding to the two constraints of the clause ei−1e_{i-1} and the columns corresponding to the variables zei−1z_{e_{i-1}} and viv_i. Note that the new columns are zero in all rows of Ai−1A_{i-1} and that vi∈ei−1v_i\in e_{i-1}. Therefore, AiA_i has the block lower-triangular form

Ai=(Ai−10BC),C=(1−111),A_i=\begin{pmatrix}A_{i-1}&0\\B&C\end{pmatrix},\qquad C=\begin{pmatrix}1&-1\\1&1\end{pmatrix},

where, as before, the signs in the second column of CC are flipped if viv_i appears negated in ei−1e_{i-1}, and ∣det⁡(Ai)∣=∣det⁡(Ai−1)∣⋅∣det⁡(C)∣=2i−2⋅2=2i−1|\det(A_i)|=|\det(A_{i-1})|\cdot|\det(C)|=2^{i-2}\cdot2=2^{i-1}.

In general, each connected component can be handled separately in the way described above. Since the resulting submatrices use disjoint rows and columns, combining them yields a block diagonal matrix whose determinant is the product of the determinants of the blocks. If these components have n1,…,nkn_1,\ldots,n_k vertices, this yields 2(n1−1)+⋯+(nk−1)≤Δ2^{(n_1-1)+\cdots+(n_k-1)}\leq\Delta. Since each connected component has at least one edge, we have nj−1≥nj/2n_j-1\geq n_j/2 for each jj, and the claim follows. □

Lemma 9.2. For every instance of max 22-CSP and every assignment τ:X⊕→{0,1}\tau:X_{\oplus}\to\{0,1\}, the integer program obtained from (13) by fixing the variables in X⊕X_{\oplus} according to τ\tau is equivalent to an integer program with at most two nonzero entries per row. Moreover, this integer program can be computed in linear time and the largest absolute value of a subdeterminant of its coefficient matrix is at most that of the coefficient matrix of (13).

Proof. Fixing the variables in X⊕X_{\oplus} corresponds to deleting their columns from the coefficient matrix of (13) and adjusting the right-hand side, so every subdeterminant of the resulting coefficient matrix is a subdeterminant of the coefficient matrix of (13). Since both variables of every XOR clause are fixed, by (12), the only rows of the resulting coefficient matrix that have more than two nonzero entries are those corresponding to OR clauses ((x,y),P)((x,y),P) with x,y∉X⊕x,y\notin X_{\oplus}. For each such clause c=((x,y),P)c=((x,y),P), we introduce two new variables zc,xz_{c,x} and zc,yz_{c,y} that indicate which of the two variables is responsible for satisfying the clause. Then, we substitute zc,x+zc,yz_{c,x}+z_{c,y} for zcz_c in the objective and replace the constraints in (12) by the following constraints, where xx is replaced by (1−x)(1-x) or yy by (1−y)(1-y) consistently:

zc,x−x≤0,zc,y−y≤0,zc,x+zc,y≤1,zc,x,zc,y∈{0,1}.(14)z_{c,x}-x\leq0,\qquad z_{c,y}-y\leq0,\qquad z_{c,x}+z_{c,y}\leq1,\qquad z_{c,x},z_{c,y}\in\{0,1\}. \tag*{(14)}

For fixed x,y∈{0,1}x,y\in\{0,1\}, the feasible values of zc,x+zc,yz_{c,x}+z_{c,y} under these constraints are precisely the values zc∈{0,1}z_c\in\{0,1\} with zc≤P(x,y)z_c\leq P(x,y). Thus, the resulting integer program is equivalent to the previous one via zc=zc,x+zc,yz_c=z_{c,x}+z_{c,y}. Clearly, its coefficient matrix has at most two nonzero entries per row and the transformation can be computed in linear time.

Moreover, we claim that the largest absolute value of a subdeterminant of the coefficient matrix does not increase by this transformation. To this end, consider the coefficient matrices without the rows corresponding to the bounds on the variables, which do not affect the largest absolute value of a subdeterminant. Then the effect of the transformation for a single OR clause is to replace

(1−1−100∗∗∗)by(10−100010−101100000∗∗∗)\begin{pmatrix} 1 & -1 & -1 & 0\\ 0 & * & * & * \end{pmatrix} \quad\text{by}\quad \begin{pmatrix} 1 & 0 & -1 & 0 & 0\\ 0 & 1 & 0 & -1 & 0\\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & * & * & * \end{pmatrix}

where the columns are labeled by the corresponding variables, the unlabeled columns correspond to the remaining variables, and the entries marked by * denote submatrices that remain unchanged. The rows appear in the order of appearance in (14) with the

remaining rows below. If xx is replaced by 1−x1-x or yy by 1−y1-y in the clause, the signs of the corresponding entries are flipped.

It remains to show that for every square submatrix M′M' of the transformed matrix with det⁡(M′)≠0\det(M') \ne0, there is a square submatrix MM of the original matrix with ∣det⁡(M)∣=∣det⁡(M′)∣|\det(M)| = |\det(M')|. Let r1,r2,r3r_1,r_2,r_3 denote the first three rows of the transformed matrix and rr the first row of the original matrix, and call r1,r2,r3r_1,r_2,r_3 and the columns of zc,xz_{c,x} and zc,yz_{c,y} new. As long as a new row or column has exactly one nonzero entry in M′M', we expand the determinant along it and replace M′M' by the resulting smaller square submatrix of the transformed matrix. Since this entry is ±1\pm1, the absolute value of the determinant does not change. Afterwards, every new row and column in M′M' has at least two nonzero entries in M′M'. If M′M' contains no new column, it thus contains no new row either, as each new row has at most one nonzero entry outside the new columns, so M′M' is a submatrix of the original matrix. Otherwise, M′M' contains a new column and hence both rows in which this column is nonzero, including r3r_3. As r3r_3 is nonzero only in the new columns, M′M' contains both new columns and hence all new rows. Replacing r3r_3 by r3−r1−r2r_3-r_1-r_2 does not change det⁡(M′)\det(M') and, regardless of the signs of the entries for xx and yy, yields a row that is zero in the new columns and coincides with −r-r in all other columns. Expanding along the two new columns, which now have exactly one nonzero entry each, shows that ∣det⁡(M′)∣=∣det⁡(M)∣|\det(M')|=|\det(M)|, where MM is the submatrix of the original matrix whose rows are rr and the rows of M′M' other than the new ones, and whose columns are those of M′M' other than the new ones.

Since the OR clauses can be transformed one at a time and the above argument does not depend on the unchanged part of the matrix, this proves the claim.

□\square

If the coefficient matrix of (13) is totally Δ\Delta-modular, then ∣X⊕∣≤2log⁡2Δ|X_{\oplus}| \le2\log_2\Delta by Lemma 9.1, so there are at most Δ2\Delta^2 assignments τ:X⊕→{0,1}\tau:X_{\oplus}\to\{0,1\}. Hence, by Lemma 9.2 and the result of [17], for any fixed Δ\Delta, max 2-CSP can be solved in polynomial time on instances where the coefficient matrix of (13) is totally Δ\Delta-modular by solving the integer program from Lemma 9.2 for each such assignment and taking the best solution. As mentioned before, this applies in particular to max 2-SAT, max cut, and directed max cut as special cases of max 2-CSP. For directed max cut, all clauses are AND clauses, so the coefficient matrix of (13) already has at most two nonzero entries per row and the result of [17] applies directly. For max cut, all clauses are XOR clauses and there is an XOR clause for each edge. Hence, by Lemma 9.1, instances where the coefficient matrix of (13) is totally Δ\Delta-modular have at most 2log⁡2Δ2\log_2\Delta non-isolated vertices and can be solved by enumerating the at most Δ2\Delta^2 assignments of these vertices. Finally, for max 2-SAT, all clauses are OR or affine clauses and the transformation from Lemma 9.2 is needed to apply the result of [17].

Acknowledgements

JPG was supported in part by the Slovenian Research and Innovation Agency (research project N1-0370). TH, OK, and SO were supported by the Institute for Basic Science (IBS-R029-C1). OK was also supported by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Science and ICT (No. RS-2023-00211670). RS was supported by the Young Scientist Fellowship of the Institute for Basic Science (IBS-R029-Y8).

References

References

  1. [1]Stephan Artmann, Robert Weismantel, and Rico Zenklusen, “A strongly polynomial algorithm for bimodular integer linear programming”, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ser. STOC 2017, pp. 1206–1219, Montreal, Canada: Association for Computing Machinery, 2017. DOI: 10.1145/3055399.3055473 MR: 3678264DOI
  2. [2]László Babai, “Graph isomorphism in quasipolynomial time”, in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ser. STOC 2016, pp. 684–697, Cambridge, MA, USA: Association for Computing Machinery, 2016. DOI: 10.1145/2897518.2897542 arXiv: 1512.03547 MR: 3536606DOI
  3. [3]Dan Bienstock, Neil Robertson, Paul Seymour, and Robin Thomas, “Quickly excluding a forest”, J. Combin. Theory Ser. B, 52(2):274–283, 1991. DOI: 10.1016/0095-8956(91)90068-U MR: 1110475
  4. [4]Adrian Bock, Yuri Faenza, Carsten Moldenhauer, and Andres Jacinto Ruiz-Vargas, “Solving the stable set problem in terms of the odd cycle packing number”, in 34th International Conference on Foundations of Software Technology and Theoretical Computer Science, ser. LIPIcs. Leibniz Int. Proc. Inform. Vol. 29, pp. 187–198, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014. DOI: 10.4230/LIPIcs.FSTTCS.2014.187 MR: 3344993DOI
  5. [5]Andreas Brandstädt and Feodor F. Dragan, “On linear and circular structure of (claw, net)-free graphs”, Discrete Appl. Math., 129(2):285–303, 2003. DOI: 10.1016/S0166-218X(02)00571-1 MR: 1997353DOI
  6. [6]Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle, “Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems”, Theoret. Comput. Sci., 511:66–76, 2013. DOI: 10.1016/j.tcs.2013.01.009 MR: 3126918
  7. [7]Yixin Cao and Peng Li, “Cluster vertex deletion on chordal graphs”, arXiv preprint, 2026. arXiv: 2604.20475
  8. [8]A. Claus, “A new formulation for the travelling salesman problem”, SIAM J. Algebraic Discrete Methods, 5(1):21–25, 1984. DOI: 10.1137/0605004 MR: 731852DOI
  9. [9]Michelle Conforti, Samuel Fiorini, Tony Huynh, Gwenaël Joret, and Stefan Weltge, “The stable set problem in graphs with bounded genus and bounded odd cycle packing number”, in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2896–2915, SIAM, 2020. DOI: 10.1137/1.9781611975994.176 arXiv: 1908.06300 MR: 4141358DOI
  10. [10]Michelle Conforti, Samuel Fiorini, Tony Huynh, and Stefan Weltge, “Extended formulations for stable set polytopes of graphs without two disjoint odd cycles”, Math. Program., 192(1):547–566, 2022. DOI: 10.1007/s10107-021-01635-0 arXiv: 1911.12179 MR: 4391781DOI
  11. [11]Clément Dallard, Martin Milanič, and Kenny Storgel, “Treewidth versus clique number. II. Tree-independence number”, J. Combin. Theory Ser. B, 164:404–442, 2024. DOI: 10.1016/j.jctb.2023.10.006 arXiv: 2111.04543 MR: 4664382DOI
  12. [12]George Dantzig, Delbert Ray Fulkerson, and Selmer Johnson, “Solution of a large-scale traveling-salesman problem”, J. Oper. Res. Soc. Amer., 2(4):393–410, 1954. DOI: 10.1287/opre.2.4.393 MR: 70932DOI
  13. [13]Reinhard Diestel, Graph Theory (Graduate Texts in Mathematics), 6th ed. Berlin, Heidelberg: Springer, 2025. DOI: 10.1007/978-3-662-70107-2 MR: 4874150DOI
  14. [14]Paul Erdős and Lajos Pósa, “On independent circuits contained in a graph”, Canad. J. Math., 17:347–352, 1965. DOI: 10.4153/CJM-1965-035-8 MR: 175810DOI
  15. [15]Luca Ferrarini, Samuel Fiorini, Stefan Kober, and Yelena Yuditsky, “Total matching and subdeterminants”, in Combinatorial Optimization (ISCO 2024), pp. 192–204, Springer, 2024. DOI: 10.1007/978-3-031-60924-4_15 arXiv: 2312.17630 MR: 4763858DOI
  16. [16]Samuel Fiorini, Nadia Hardy, Bruce Reed, and Adrian Vetta, “Planar graph bipartization in linear time”, Discrete Appl. Math., 156(7):1175–1180, 2008. DOI: 10.1016/j.dam.2007.08.013 MR: 2404231DOI
  17. [17]Samuel Fiorini, Gwenaël Joret, Stefan Weltge, and Yelena Yuditsky, “Integer programs with bounded subdeterminants and two nonzeros per row”, J. ACM, 72(1):Art. No. 3, Jan. 2025. DOI: 10.1145/3695985 arXiv: 2106.05947 MR: 4857283DOI
  18. [18]Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh, “Representative families of product families”, ACM Trans. Algorithms, 13(3):Art. No. 36, Mar. 2017. DOI: 10.1145/3039243 arXiv: 1402.3909 MR: 3689364DOI
  19. [19]BezaleI Gavish and Stephen C. Graves, “The travelling salesman problem and related problems,” Massachusetts Institute of Technology, Operations Research Center, Working Paper OR 078-78, Jul. 1978. [Online]. Available: http://hdl.handle.net/1721.1/5363
  20. [20]Fănică Gavril, “Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph”, SIAM J. Comput., 1(2):180–187, 1972. DOI: 10.1137/0201013 MR: 327580DOI
  21. [21]J. Pascal Gollin and Sebastian Wiederrecht, “Structure and algorithms for graphs excluding grids with small parity breaks as odd-minors”, arXiv preprint, 2023. arXiv: 2304.04504arxiv.org/abs/2304.04504
  22. [22]Jerrold W. Grossman, Devadatta M. Kulkarni, and Irwin E. Schochetman, “On the minors of an incidence matrix and its Smith normal form”, Linear Algebra Appl., 218:213–224, 1995. DOI: 10.1016/0024-3795(93)00173-W MR: 1324059DOI
  23. [23]Tony Huynh and O-Joung Kwon, “On the Erdős–Pósa property for long holes in C₄-free graphs”, SIAM J. Discrete Math., 38(1):19–42, 2024. DOI: 10.1137/21M1435239 arXiv: 2105.11799 MR: 4683959
  24. [24]Klaus Jansen and Petra Scheffler, “Generalized coloring for tree-like graphs”, Discrete Appl. Math., 75(2):135–155, 1997. DOI: 10.1016/S0166-218X(96)00085-6 MR: 1451958DOI
  25. [25]Eun Jung Kim and O-Joung Kwon, “Erdős–Pósa property of chordless cycles and its applications”, J. Combin. Theory Ser. B, 145:65–112, 2020. DOI: 10.1016/j.jctb.2020.05.002 arXiv: 1711.00667 MR: 4101471
  26. [26]Stefan Kuhlmann and Robert Weismantel, “A threshold phenomenon for the shortest lattice vector problem in the infinity norm”, in Integer Programming and Combinatorial Optimization (IPCO 2026), pp. 188–203, Springer, 2026. DOI: 10.1007/978-3-032-28691-8_13 arXiv: 2508.02249 MR: 5087318DOI
  27. [27]Eugene M. Luks, “Isomorphism of graphs of bounded valence can be tested in polynomial time”, J. Comput. System Sci., 25(1):42–65, 1982. DOI: 10.1016/0022-0000(82)90009-5 MR: 685360DOI
  28. [28]D. S. Malyshev and D. V. Gribanov, “The computational complexity of dominating set problems for instances with bounded minors of constraint matrices”, Discrete Optim., 29:103–110, 2018. DOI: 10.1016/j.disopt.2018.03.002 MR: 3834907DOI
  29. [29]Clair E. Miller, Albert W. Tucker, and Richard A. Zemlin, “Integer programming formulation of traveling salesman problems”, J. ACM, 7(4):326–329, 1960. DOI: 10.1145/321043.321046 MR: 149964
  30. [30]Sarah Morell, Ina Seidel, and Stefan Weltge, “Minimum-cost integer circulations in given homology classes”, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2725–2738, SIAM, 2021. DOI: 10.1137/1.9781611976465.162 arXiv: 1911.10912 MR: 4262595DOI
  31. [31]Joseph Paat, Ingo Stallknecht, Zach Walsh, and Luze Xu, “On the column number and forbidden submatrices for Δ-modular matrices”, SIAM J. Discrete Math., 38(1):1–18, 2024. DOI: 10.1137/22M1539927 arXiv: 2212.03819 MR: 4683958DOI
  32. [32]F. P. Ramsey, “On a problem of formal logic”, Proc. London Math. Soc. (2), 30(1):264–286, 1930. DOI: 10.1112/plms/s2-30.1.264 MR: 1576401DOI
  33. [33]Neil Robertson and Paul D. Seymour, “Graph minors. V. Excluding a planar graph”, J. Combin. Theory Ser. B, 41(1):92–114, 1986. DOI: 10.1016/0095-8956(86)90030-4 MR: 854606DOI
  34. [34]Donald J. Rose, R. Endre Tarjan, and George S. Lueker, “Algorithmic aspects of vertex elimination on graphs”, SIAM J. Comput., 5(2):266–283, 1976. DOI: 10.1137/0205021 MR: 408312DOI
  35. [35]Jens M. Schmidt, “A simple test on 2-vertex- and 2-edge-connectivity”, Inform. Process. Lett., 113(7):241–244, 2013. DOI: 10.1016/j.ipl.2013.01.016 arXiv: 1209.0700 MR: 3017986DOI
  36. [36]V. N. Shevchenko, Qualitative Topics in Integer Linear Programming (Translations of Mathematical Monographs). Providence, RI: American Mathematical Society, 1997, vol. 156, Translated from the Russian by H. H. McFadden. DOI: 10.1090/mmono/156 MR: 1414900DOI
  37. [37]W. T. Tutte, Connectivity in graphs (Mathematical Expositions). University of Toronto Press, Toronto, ON; Oxford University Press, London, 1966, vol. 15. DOI: 10.3138/9781487584863 MR: 210617DOI

Paper details

vlnc:W_pyfsyx73
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents