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 -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 -modular if the absolute value of the determinant of every square submatrix is at most . It is a fundamental open problem whether integer programs
with a totally -modular coefficient matrix can be solved in polynomial time for fixed . For , 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 . In earlier work, Shevchenko [36] explicitly conjectured that the problem is polynomial-time solvable for every fixed . However, the complexity status remains open for all and it is unclear which algorithmic paradigm might be suitable for solving these instances. Instead of focusing on all instances for some fixed , 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 -modular if and only if the largest size of an item is at most , 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 -modularity turns out to be equivalent to bounding the odd cycle packing number of the underlying graph (or its complement) by . 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 . Moreover, polynomial-time algorithms have been established for totally -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 , the following problems are polynomially solvable when restricted to instances for which the coefficient matrix of their natural integer programming formulation is totally -modular:
-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 -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 -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 -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 -CSPs for , 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 -shortest lattice vector problem can be solved in polynomial time for totally -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 and a positive integer , there exists a coloring such that for all . The problem is trivial for , and for it is equivalent to checking whether is bipartite. From now on, assume , for which the problem is NP-complete. A typical formulation of the problem as a (feasibility) integer program is
where the variable indicates whether vertex is colored with color for each and . 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 -modular, then contains at most vertex disjoint cycles.
Proof. Let be the edge-vertex-incidence matrix of . That is, if and otherwise. Collect the variables into one vector where for . Then we can rewrite (1) as
Let be an arbitrary cycle of with vertices . If has odd length, then the corresponding submatrix of (say in the first color) has determinant . If has even length, we find the incidence matrix of a cycle of length as a submatrix of the coefficient matrix of (1). As is odd, the resulting submatrix will have determinant of absolute value . To this end, select the columns corresponding to and the rows corresponding to in the first color, in the second color, in the third color, in the first color for , as well as the rows corresponding to in the matrix . The construction is illustrated in Figure 2.1. If 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 ). The curved edges represent the edges corresponding to the rows of the matrix . 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 .
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 of vertices that hits all cycles. For constant , we can efficiently enumerate all possible choices and potential colorings of . 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 and are undirected graphs with adjacency matrices and , respectively, note that and are isomorphic if and only if there exists a permutation matrix with , or, equivalently, . This gives rise to the following common (feasibility) integer programming formulation of the problem.
Lemma 3.1. If the coefficient matrix of (2) is totally -modular and has at least one edge, then the maximum degree of is at most .
Proof. We may assume that and have the same vertex set . For each , comparing the respective entries of and , the equation in (2) reads
where and denote the sets of neighbors of in and , respectively. Treating as a vector in we can rewrite the above constraints as , where is given by
By the assumption, is totally -modular. Let be a vertex in with neighbors in , and let denote a vertex in that has at least one neighbor in . Consider the submatrix of that consists of the rows corresponding to and and the columns corresponding to and for . The form of this submatrix is
where all unspecified entries are zero. By adding all rows to the first row, we obtain , 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 and a weight function , a straightforward integer programming formulation of the problems is
where 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 indicates whether the vertex is included in the solution.
We remark that, for fixed , it is known that a totally -modular matrix with columns has only polynomially many (in ) distinct rows (see [31]). Hence, in any totally -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 and , an -model in consists of a non-empty tree that is a subgraph of for each vertex , called a branch set, and an edge with one endpoint in and the other in for each edge , such that all branch sets are pairwise vertex-disjoint. has an -minor if and only if there is an -model in .
Lemma 4.1. For each , if a graph contains a -grid as a minor, then the coefficient matrix of (3) with being the set of all cycles in contains every non-singular -matrix of size as a submatrix.
Proof. Let be an arbitrary non-singular $0/1$-matrix of size . In particular, all rows of are distinct. We will first describe the case where contains a -grid as a subgraph, not only as a minor. Label the vertices of the grid as for where is the index of the grid row and 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, for . Then, for each row of the matrix , we construct a cycle that yields precisely this row in the submatrix. To this end, choose any path from to that intersects the first two grid rows only in its endpoints. Then, for each entry of for , construct a path from $v_{2,2i-1} to as follows. If , use the path joining and in the second grid row, thus avoiding . If , use the path , thus using . For , construct a path from to 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 .
Now, assume that has a -grid as a minor. Let be an -model in . Consider the selection of vertices and cycles in described above. For each selected cycle in , we obtain a corresponding cycle in by taking for each edge of the cycle and, for each vertex of the cycle, connecting the relevant endpoints by a path in . Concerning the selected vertices, some care is needed, since the branch set of a vertex may contain multiple vertices of , some of which might not be part of all lifted cycles through . However, note that the selected vertices in 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 in for each selected vertex that is contained in the selected cycles in if and only if is contained in the corresponding cycles in .
Note that there are -matrices of size with determinant exponential in . Hence, by the above lemma, any graph for which the formulation (3) is totally -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 such that the treewidth of every graph , for which the formulation (3) is totally -modular, is at most . 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 , totally -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 be an -model in a graph . We call an odd -model if the vertices of its branch sets admit a 2-coloring that is proper on each branch set and under which each edge is monochromatic. Accordingly, we say that is an odd minor of if contains an odd -model. It is easy to see that odd minors preserve the parity of cycles in the sense that every cycle in gives rise to a cycle of the same parity in 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 as the graph obtained from the -grid by adding a single parity-breaking edge in the center, see Figure 4.1 for an illustration of the case .
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 , if a graph contains a singly parity-breaking grid of order as an odd minor, then the coefficient matrix of (3) with being the set of all odd cycles in contains every non-singular 0/1-matrix of size 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 to 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 .
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 -modular, then the underlying graph does not contain a singly parity-breaking grid of order for a function 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 that has one vertex for each block and each cutvertex of a connected graph , where a block is adjacent to a cutvertex if , is a tree, called the block-cut tree of $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 if and only if its intersection with each block is an odd cycle transversal of that block.
Lemma 4.3. There is a function such that, for every positive integer , every block of a graph that does not contain the singly parity-breaking grid of order as an odd minor is bipartite or has treewidth at most .
Proof. Blocks that are not 2-connected are isomorphic to or 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 as an odd minor has treewidth at most .
We can now give a dynamic programming algorithm similar to [21 §7].
Lemma 4.4. Let be a fixed integer. For a graph each of whose blocks is bipartite or has treewidth at most , 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 is connected and has a cutvertex, as otherwise we can treat the components separately or is a single block. We compute the block-cut tree and root it at a cutvertex . Then each block has a parent in , and its children are the cutvertices in . The children of a cutvertex are the blocks with . For a cutvertex , let be the union of all blocks in the subtree of rooted at . In particular, we have . Let be the minimum weight of an odd cycle transversal of that does not contain , and let be the minimum weight of an odd cycle transversal of that contains . We compute these values bottom-up in and return .
Let be a cutvertex. For each child of , define weights on by for and otherwise. We claim that for , we have
where denotes the set of all odd cycle transversals of and denotes the characteristic vector of , i.e., if and otherwise. To see the correctness, note that the blocks of are the children of and the blocks of the graphs . Hence, a set is an odd cycle transversal of if and only if is one of and is one of for all and . Further, is the disjoint union of and, for each , the set and the sets with , and . Hence, given , the sets can be chosen independently for the children of , and once they are fixed, so can the sets , each optimally at cost . This proves the claim. Each of these minima can be computed by a weighted odd cycle transversal problem on , as the constraint can be dropped by setting if , so that adding to an odd cycle transversal not containing it yields one of smaller weight, and if , since then replacing by its neighbors in turns any odd cycle transversal containing into one of smaller weight. Thus, we obtain all values 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 , instances of the odd cycle transversal problem for which the coefficient matrix of (3) is totally -modular can be solved in polynomial time.
An alternative common integer programming formulation of the odd cycle transversal problem is given by
where , and indicate whether is assigned to the left side, assigned to the right side, or deleted, respectively.
Let be fixed. We show that every instance of the odd cycle transversal problem for which the coefficient matrix of (4) is totally -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 -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 for each . 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 -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 odd cycles has a totally unimodular coefficient matrix with respect to (3), but has a subdeterminant of absolute value with respect to (4). On the other hand, the singly parity-breaking grid of order has a totally -modular coefficient matrix with respect to (4), but has subdeterminants of absolute value exponential in 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 , where is the maximum number of vertex-disjoint odd cycles in the graph [22].
Dominating set
Given a graph and a weight function , the dominating set problem asks to find a subset of minimum weight such that every vertex in has a neighbor in . A natural integer programming formulation of the dominating set problem is given by
where denotes the set of neighbors of in .
We start by fixing some notation needed for our argument. The -star is the complete bipartite graph with one part of size one and the other of size , the -net is the graph consisting of a clique of size and a disjoint independent set of size joined to the clique by a perfect matching, and the -prism is a graph consisting of two disjoint cliques of size 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 -star, -net, and -prism for .
For a collection of graphs , we say that a graph is -free if it does not contain any graph from as an induced subgraph. Let be the collection consisting of the -star, -net, -prism, the disjoint union of claws, and the disjoint union of nets, where .
In the unweighted setting, Malyshev and Gribanov [28] proved polynomial-time solvability by showing that, after guessing a number of vertices depending only on , the problem reduces to an instance on -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 -free graphs is NP-hard.
Proof. Recall the NP-hard set cover problem: Given a set and a family of subsets of , the set cover problem asks to find a minimum-size subfamily such that every element in is contained in at least one set in .
To reduce an instance of set cover to a -free instance of weighted dominating set, create a graph with vertex set , such that and are cliques and there is an edge between and if and only if . Assign each vertex in a weight of and each vertex in a weight of 1. Then a minimum weight dominating set of corresponds to a minimum size set cover of the original instance and the resulting graph is -free, since it does not contain an independent set of size more than 2. □
While this shows restricting to -free graphs is not sufficient, they still play an important role in our proof. For a vertex , let denote the set of vertices at distance exactly from . We use the following property of -free graphs.
Lemma 5.2. Let be a -free graph, , and . Then contains no independent set of size at least 3.
Proof. We prove the claim by induction on . For , the claim is trivial. For , the claim follows from the fact that is claw-free. Let . First, consider any vertex , assume that there are two non-adjacent vertices , and let be a neighbor of in . Then induces a claw in . Therefore the set is a clique. Now, assume for contradiction that contains an independent set of size 3. Let be a neighbor of in for . Since is a clique, the must be pairwise distinct and is adjacent to if and only if . By the induction hypothesis, there is at least one edge among the . Moreover, if there are exactly two edges, say and , then induces a claw in . If there are three edges, then induces a net in . It remains to consider the case that there is exactly one edge among the , say . Let be a neighbor of in . If is not adjacent to , then induces a claw in . If is adjacent to and , pick a neighbor of in . Then induces a net in . If is adjacent to and , then and . In this case, induces a net in . □
Moreover, Malyshev and Gribanov [28] observed the following.
We will use this in combination with the notion of linear mim-width. Let be a graph. For disjoint sets of vertices, let denote the bipartite graph with vertex set and edge set . For , denotes the maximum size of an induced matching in . A linear ordering of is a permutation of . The mim-width of a linear ordering of is defined as . The linear mim-width of is the minimum mim-width over all linear orderings of .
Further, we write for the minimum integer such that every graph on vertices contains either an independent set of size or a clique of size . The classical theorem of Ramsey [32] implies that exists.
Lemma 5.4. The linear mim-width of an -free graph is at most
Moreover, a linear ordering with mim-width at most can be found in polynomial time.
Proof. Let be a maximal packing of induced subgraphs in , each isomorphic to the claw or the net, such that there is no edge between distinct members of . Note that such a packing can be found greedily in polynomial time. Set . Since is -free, contains at most claws (with 4 vertices each) and at most nets (with 6 vertices each) and hence . Let be the connected components of . For each , let be an arbitrary vertex in . Consider the linear ordering of obtained by first taking an arbitrary ordering of and then appending, for each connected component in order of increasing index, all vertices of in order of non-decreasing distance from in . The indexing of the connected components and the order of the vertices within with the same distance from can be chosen arbitrarily. Note that such an ordering can be computed in polynomial time. We claim that this ordering witnesses that has linear mim-width at most .
To this end, let be a prefix of the ordering and let denote a maximum induced matching in with and . Let and denote the size of a maximum independent set and a maximum clique in a graph , respectively. To prove the claim, it suffices to show that and .
Note that
Since does not contain a -star as an induced subgraph, for each . By the construction of the ordering, either is empty, in which case , or which means . In the latter case, let be the maximal index of a connected component such that and let be the maximal distance in from to any vertex in . Then, for any and its matched vertex , both and must be in and the distance from to must be or . By the definition of , the graph is -free. Hence, by Lemma 5.2, we have that since intersects at most two layers. Altogether, we have .
To show that , assume for contradiction that contains a clique of size with vertex set . Let be the set of vertices matched to in the induced matching. By the definition of , contains either an independent set of size or a clique of size . Denote the vertex set of the independent set, respectively the clique, by and let denote the set of vertices that are matched to vertices in . Then, induces a -net if induces an independent set, and a -prism if induces a clique, contradicting the fact that is -free. We conclude that .
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 -modular can be solved in polynomial time for each fixed .
Induced matching
Given a graph and a weight function , the maximum induced matching problem asks for a subset of maximum weight such that is a matching and the graph induced by all endpoints of edges in has no edges other than . There is a natural integer programming formulation of the maximum induced matching problem based on the line graph of . Recall that is the graph with vertex set in which are adjacent if and only if they share a common endpoint in . Then, the maximum induced matching problem has the following integer programming formulation:
Lemma 6.1. If the coefficient matrix of (6) is totally -modular, then the pathwidth of is at most .
Proof. Let denote the -subdivided claw, i.e., the graph obtained from the claw by subdividing each edge exactly once and let denote the disjoint union of copies of . Note that is a net and that if contains as a subgraph, then contains the disjoint union of 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 . By Lemma 5.3, if the coefficient matrix of (6) is totally -modular, then does not contain the disjoint union of nets as an induced subgraph and hence, by the argument above, does not contain as a subgraph.
Finally, since has maximum degree 3, if contains as a minor, then it also contains a subdivision of as a subgraph (see [13 Proposition 1.7.3]). Since every subdivision of contains as a subgraph, we conclude that does not contain the forest as a minor. By a result of Bienstock, Robertson, Seymour, and Thomas [3], this implies that the pathwidth of is at most . □
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 , totally -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 and a weight function , the cluster vertex deletion problem asks to find a subset of minimum weight such that is a cluster graph (a disjoint union of cliques). Here and in the following, denotes the induced subgraph of on the vertex set . It is not difficult to see that a graph is a cluster graph if and only if it does not contain an induced , where denotes the path on vertices. This yields the following integer programming formulation.
where is the set of all such that is isomorphic to , and indicates whether the vertex 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 such that, if the coefficient matrix of (7) is totally -modular, then there exists a set with such that is chordal.
Proof. We claim that any hole corresponds to a submatrix with determinant of absolute value at least and that for multiple holes, they combine to form a block diagonal matrix. This implies that has at most vertex-disjoint holes and, by the Erdős–Pósa theorem for holes [23, 25], we conclude that there is a set of size at most such that is chordal for some computable function .
It remains to show that any hole corresponds to a submatrix with determinant of absolute value at least . To this end, note that a sequence of induced ’s in the path with a sequence of vertices such that contains exactly two of the ’s, namely and , for all and where is the first vertex of the path and is the last vertex of the path gives rise to induced ’s in a hole of length and vertices in the hole by identifying and . Moreover, the corresponding submatrix is the incidence matrix of a cycle of length , which has determinant of absolute value if is odd. Therefore, it suffices to show that for any , there exist sequences as described above for with odd. We can give these sequences explicitly depending on the residue of modulo (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 's and the black vertices are the selected vertices.
: , , , and , , , ; , and
: , , , and , , , ; , and
: , , , and , , , ; , and
: , , , , , and , , , ; , and
Here, each case starts with a construction for , , or vertices and then extends the construction to by appending pairs of induced ’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 , if there exists a set of at most vertices such that 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 of at most vertices such that is chordal. Since it is possible to recognize chordal graphs in linear time [34], we can find such a set 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 be an optimal solution and let .
Clearly, hits all induced 's that lie completely in . Moreover, let be the set of vertices such that there is an induced with as an endpoint and the other two vertices in . Then must contain . Further, let for each where is the neighborhood of in . Observe that if are non-adjacent in , then is an induced of . Hence, must contain or . In other words, contains a vertex cover of (and thus also an inclusion-wise minimal vertex cover), where is the complement of .
We can therefore guess and a minimal vertex cover of for each . For each such guess we consider the remaining instance . For , it holds that is chordal: Clearly, is chordal since it is an induced subgraph of . Thus, if contains a hole, it must contain a vertex with two non-adjacent neighbors . However, we cannot have , since hits all induced 's that lie completely in . Further, we cannot have , since is a vertex cover of . Lastly, we cannot have that one of is in and the other in , since then the other is in . Consequently, is chordal. We can therefore check for each guess whether the remaining instance is chordal and, if so, solve the cluster vertex deletion problem on . For the correct guess of and the corresponding , taking the union of the solution on with 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 guesses for since . Moreover, note that a minimal vertex cover of corresponds to a maximal clique of via . Further, since is a chordal graph as an induced subgraph of , contains at most maximal cliques, and all maximal cliques of can be enumerated efficiently [20]. Thus, all minimal vertex covers of can be enumerated efficiently. Since we only have to guess many , 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 -modular for any constant .
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 with edge costs . 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 as a coefficient in the coefficient matrix. Similarly, the flow-based formulation by Gavish and Graves [19] contains as a coefficient in the coefficient matrix. Therefore, these formulations are totally -modular only for graphs with at most , respectively vertices.
More interesting are the formulations proposed by Dantzig, Fulkerson, and Johnson [12]. We denote by the set of edges with exactly one endpoint in and define . Both formulations share the constraints
where indicates whether the edge is included in the cycle. The first formulation has (8) and the additional constraints
the second has (8) and the additional constraints
where denotes the set of edges with both endpoints in . 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 -modularity.
Lemma 8.1. If the coefficient matrix of (8) and (9), respectively of (8) and (10), is totally -modular, then any cycle in has length at most .
Proof. Assume contains a cycle of length . Denote the vertices of the cycle by and the edges by for , where the indices are taken modulo .
Consider the submatrix that selects the columns corresponding to the edges for and three rows for each such . We claim that for a suitable choice of the rows, the resulting submatrix is a block-diagonal matrix with one block of determinant for each . First, select the row from (8) corresponding to the degree constraint of , then for (9) additionally select the rows corresponding to and to , respectively for (10) additionally select the rows corresponding to and to .
Since , the rows selected for have support in when restricted to the selected columns, so the resulting submatrix is block-diagonal and each block is equal to
which has determinant . We conclude that which implies that .
By Lemma 8.1, any feasible instance of the traveling salesman problem with a totally -modular coefficient matrix with regard to either of the formulations by Dantzig, Fulkerson, and Johnson has at most vertices. Therefore, for any fixed , 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 obtained from by replacing each edge by the two arcs , defining the cost of each arc as , and finding a directed cycle of minimum cost that visits each vertex exactly once in . The formulation selects an arbitrary vertex as a source and is given by
where , , and for all , and and denote the sets of outgoing and incoming arcs of , respectively. In the formulation, indicates whether the arc is included in the cycle and , is a unit flow from to for each .
Lemma 8.2. If the coefficient matrix of (11) is totally -modular, then any cycle in has length at most .
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 contains a cycle of length . Label the vertices of the cycle by in cyclic order. Since contains both orientations of every edge of , the arcs and are contained in for all . Moreover, since , we can fix two distinct vertices .
Consider the submatrix that selects the columns corresponding to the variables , , , , , , for and seven rows for each such . 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 . For each , select the row corresponding to the outdegree constraint of , the rows corresponding to the coupling constraints for , , and , and the rows corresponding to the flow conservation constraints for and . Each of these rows has nonzero entries only in variables of arcs incident to , and each column selected for corresponds to an arc of incident to . Since no two of the vertices are adjacent in , this means the resulting submatrix is block-diagonal and, with rows and columns ordered as listed above, each block is equal to
which has determinant 2. We conclude that which implies that .
By Lemma 8.2, any feasible instance of the traveling salesman problem with a totally -modular coefficient matrix with regard to (11) has at most 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 , a finite set of clauses, each of the form with distinct and a predicate , and a weight function . The problem then asks for an assignment that maximizes the total weight of the satisfied clauses, where a clause is satisfied by if .
For a predicate , we define . Up to replacing by or by , every predicate is of one of the following four types: AND (), OR (), XOR () or affine ( is an affine function over of and ). Note that in the affine case, is either constant or equal to or , up to negation. For each of these, we can give a description of by linear inequalities, which are given by the bounds and
With this notation, max 2-CSP can be formulated as the following integer program, where the containment in is expressed by the inequalities above, with and substituted for and appropriately.
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 of variables that appear in XOR clauses. To this end, let be the (multi)graph with vertex set that has an edge for each XOR clause , where we identify each edge with the corresponding clause. Note that, as in the classification above, XOR clauses include clauses in which or appear negated.
Lemma 9.1. If the coefficient matrix of (13) is totally -modular, then .
Proof. First, consider the case that is connected and let be a spanning tree of . Let be an ordering of the vertices of and let be an ordering of the edges of such that is a connected subtree of for all . We now iteratively construct a submatrix of the coefficient matrix with for .
For , let be the submatrix whose rows correspond to the two constraints in (12) of the clause and whose columns correspond to the variables and . Then, up to flipping the signs in the second column if appears negated in , we have
and, in any case, .
For , let arise from by additionally selecting the rows corresponding to the two constraints of the clause and the columns corresponding to the variables and . Note that the new columns are zero in all rows of and that . Therefore, has the block lower-triangular form
where, as before, the signs in the second column of are flipped if appears negated in , and .
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 vertices, this yields . Since each connected component has at least one edge, we have for each , and the claim follows. □
Lemma 9.2. For every instance of max -CSP and every assignment , the integer program obtained from (13) by fixing the variables in according to 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 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 with . For each such clause , we introduce two new variables and that indicate which of the two variables is responsible for satisfying the clause. Then, we substitute for in the objective and replace the constraints in (12) by the following constraints, where is replaced by or by consistently:
For fixed , the feasible values of under these constraints are precisely the values with . Thus, the resulting integer program is equivalent to the previous one via . 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
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 is replaced by or by in the clause, the signs of the corresponding entries are flipped.
It remains to show that for every square submatrix of the transformed matrix with , there is a square submatrix of the original matrix with . Let denote the first three rows of the transformed matrix and the first row of the original matrix, and call and the columns of and new. As long as a new row or column has exactly one nonzero entry in , we expand the determinant along it and replace by the resulting smaller square submatrix of the transformed matrix. Since this entry is , the absolute value of the determinant does not change. Afterwards, every new row and column in has at least two nonzero entries in . If 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 is a submatrix of the original matrix. Otherwise, contains a new column and hence both rows in which this column is nonzero, including . As is nonzero only in the new columns, contains both new columns and hence all new rows. Replacing by does not change and, regardless of the signs of the entries for and , yields a row that is zero in the new columns and coincides with in all other columns. Expanding along the two new columns, which now have exactly one nonzero entry each, shows that , where is the submatrix of the original matrix whose rows are and the rows of other than the new ones, and whose columns are those of 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.
If the coefficient matrix of (13) is totally -modular, then by Lemma 9.1, so there are at most assignments . Hence, by Lemma 9.2 and the result of [17], for any fixed , max 2-CSP can be solved in polynomial time on instances where the coefficient matrix of (13) is totally -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 -modular have at most non-isolated vertices and can be solved by enumerating the at most 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]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]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]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]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]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]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]Yixin Cao and Peng Li, “Cluster vertex deletion on chordal graphs”, arXiv preprint, 2026. arXiv: 2604.20475
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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



