Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns

In this paper, we show that solving integer linear programs is fixed-parameter tractable parameterized by the number of columns of $A$ with $1$-norm greater than $2$.

This reveals an entirely new class of ILPs that is FPT and adds to the story of parameterized ILPs and distance to triviality paradigm. To obtain this algorithm, we use a remainder guessing strategy introduced by Cslovjecsek et al. [12]. Central in this approach is modeling non-backdoor variables as polyhedral constraints on the backdoor variables. In [12], these polyhedral constraints may be exponentially complex, whereas we exploit the structure of matching problems and employ an efficient description of a global polyhedral constraint. To accomplish this, we study the convexity of degree sequences for which subgraphs with matching degrees exist. These systems have been studied previously, see [1], and are a well-known example of discrete systems known as jump systems [8, 39, 40, 35]. For our application, we prove a new result involving the lattice-convexity of a particular class of jump M-convex functions on the shifted lattice $2{\mathbb{Z}}^m+r$. See Section 2 for a technical overview of this algorithm.

As for the constraint backdoors, we show that matching-like ILPs are solvable in polynomial time with a randomized algorithm for a fixed number of additional complicating constraints if the constraints and the objective are encoded in unary. As Equation W can encode the NP-hard subset sum problem for $h=1$, we will need to assume that the coefficients of the constraint matrix are small. That is, we assume that they are bounded by $\mathrm{\Delta }$ in absolute value. The given randomized XP time algorithm unifies the known tractability in terms of membership in RP of multiple classes of constrained problems where the edges of a graph correspond to variables.

In this paper, the running time is measured in the number of arithmetic operations on numbers with encoding length polynomial in the encoding length of the instance. The $\widetilde{𝒪}$ hides polylogarithmic factors of the encoding length of the instance.

Camerini, Galbiati and Maffioli [10] already observed in 1992 that one can solve constrained flow, circulation and matching problems in randomized, pseudo-polynomial time. Theorem 3 differs in that it reveals the tractability of a generalized class of problems by removing the exponential dependency on the encoding length of $b$ that would appear in a purely pseudo-polynomial algorithm.

The randomized XP time algorithm is obtained through the use of a Graver augmentation framework, which has been effective in obtaining FPT algorithms for two-stage stochastic and $n$-fold ILP with small coefficients [17]. For those ILPs, the Graver complexity is bounded by a function of the parameters, resulting in FPT algorithms, whereas the XP time dependence on $h$ of Theorem 3 is the result of Equation W having a large Graver complexity and proximity. We provide upper and lower bounds for these respective quantities. See Sections 2.2 and 4. The latter section also reveals that Equation T has a similarly large Graver complexity even for binary matrices $T$, which motivates the use of the different technique.

We provide a W[1]-hardness result in terms of the number of additional constraints $h$ to match the randomized XP time algorithm in a complexity theoretic sense. The hardness persists even for binary constrained perfect matching on a restricted class of graphs. Theorem 4 additionally shows that parameterizing with $\mathrm{\Delta }$ in addition to the number of complicating constraints $h$ is unlikely to result in an FPT algorithm.

We like to conclude the introduction with noting that recent methodology used by Eisenbrand and Rothvoss [18] can be used to derive a similar results to Theorem 2 in a different way. This work was carried out independently to ours.

Before presenting the key components of the algorithms that solve the generalized matching problem with additional variables or constraints, we first discuss a reduction that modifies Equations T and W in a favorable way. By doing so, it suffices to give algorithms for such restricted instances, see Sections 2.2 and 2.3.

In particular, we show that Equations T and W can, in polynomial time, be transformed to equivalent ILPs where the generalized matching submatrix is transformed to the constraint matrix of the perfect $b$-matching problem. Such matrix $M$ is a binary matrix with unique columns that each have precisely two nonzero entries, and is the incidence matrix of a simple graph $G(M)$, the constraint graph, with vertices $[m]$. Since $M$ is the incidence matrix of $G(M)$, we may identify a variable $i\in [n]$ with the edge of $G(M)$ connecting the vertices $j_1,j_2$ such that $M_{i,j_1}=M_{i,j_2}=1$. Now, a perfect $b$-matching $x$ of $G(M)$ is a solution to the generalized matching ILP with constraint matrix $M$, nonnegative integral variables $x\in {\mathbb{Z}}_{\ge 0}^n$, and right-hand-side $b$. That is, $x$ assigns a value to every edge such that for every vertex $i$ the sum of $x_j$ over the incident edges $j$ is exactly $b_i$.

The used reduction is an extension of the reduction in [45] from generalized matching to $b$-matching. However, we show in Lemma 5 that we can also keep track of the additional general variables and constraints.

Here, parameters with primes are used to denote the parameters of the new instance and $u=\mathbf{\infty }$ denotes the absence of upper bounds on $x$. The proof transforms the constraint matrix and variable bounds to the intended form by creating additional constraints and variables. It consists of steps that individually treat columns with negative entries, columns with $1$-norm strictly less than $2$ and finite variable upper bounds. Most of these obstacles are circumvented by conceptually subdividing edges or adding redundant constraints. See [36] for the proof.

By virtue of Lemma 5, we can now restrict ourselves to finding algorithms for Equations T and W which represent perfect $b$-matching problems with additional variables or constraints.

We now focus on solving Equation T. We first motivate the main idea underlying the algorithm and present the algorithm itself, before we give an outline of remaining parts. The key idea is to treat the backdoor variables $y$ and the matching variables $x$ separately. Let us first consider the problem of determining the feasibility of Equation T. In essence, we replace the constraint $Ty+Mx=b$ and matching variables $x$ with a polyhedral constraint of the form $b-Ty\in P$ for some polyhedron $P$ that models that there must exist a $x\in {\mathbb{Z}}_{\ge 0}^n$ such that $Mx=b-Ty$, in other words, there must exist a perfect $(b-Ty)$-matching in $G(M)$. To construct such polyhedral constraint on $y$, the first idea may be to use the convex hull of all points $z\in {\mathbb{Z}}^m$ such that there exists a perfect $z$-matching–unfortunately, a naive execution of this strategy fails as when $G(M)=K_3$, the complete graph on $3$ vertices, we have that $z=(0,0,0)$, $z=(2,2,2)$ and the convex combination $z=(1,1,1)$ are in the hull, but the latter does not admit a perfect $z$-matching. Hence, we attempt to model a discrete set that is not lattice-convex on ${\mathbb{Z}}^3$ with a convex constraint, which is impossible.

To contrast this, the work by Cslovjecsek et al. [12] shows that, even for general matrices $M$, one can work around this issue by restricting $y$ to a fixed remainder $r\in {\mathbb{Z}}^m$ modulo some large integer $B$. That is, one can construct a polyhedron $P_r$ such that for all $y\in B{\mathbb{Z}}^m+r$, we have that $\{Mx=b-Ty,x\in {\mathbb{Z}}_{\ge 0}^n\}$ is feasible if and only if $b-Ty\in P_r$. Note that through an affine transformation, this may equivalently be posed as a polyhedral constraint directly on $y$. Their choice of $B$ may grow with the dimensions of $M$, which calls for a more problem specific approach to solve Equation T in FPT time. When $M$ is the incidence matrix of a simple graph, we show that we may restrict the modulus $B$ to be the constant $2$, which paves the way for an FPT algorithm. In addition, we show that one may optimize over a linear objective function by encoding the objective contribution of the matching part of the ILP in an additional dimension of $P_r$. The required convexity property to make this work translates to a lattice-convexity property, see Lemma 7, of the function $f_{c,M}$ from Definition 6.

We use modular congruence on vectors to denote component-wise modular congruence. Next, we show in which way Lemma 7 allows us to reformulate Equation T. First, we perform a binary search on the objective to obtain the problem of finding a feasible point of Equation T subject to an additional linear constraint $a^{\top }y+c^{\top }x\le {\omega }^{\ast }$. We guess the remainder vector $t$ of $y$ in an optimal solution modulo $2$. It then suffices to search for an integer point $y$ restricted to $y\equiv t(mod2)$ in the box $e\le y\le g$ subject to the constraint that there is a perfect $(b-Ty)$-matching with cost at most ${\omega }^{\ast }-a^{\top }y$. This is equivalent to finding a point in the set

In particular, as the parity of $b-Ty\equiv r(mod2)$ is constant for $y\equiv t(mod2)$, Lemma 7 shows that there exists a convex set $P_r$ such that the constraint $f_{c,M}(b-Ty)\le {\omega }^{\ast }-a^{\top }y$ may be replaced with $({\omega }^{\ast }-a^{\top }y,b-Ty)\in P_r$. When we obtain a good representation of $P_r$, we use the algorithm by Reis and Rothvoss [44] to solve the integer program in FPT time. After guessing all $2^p$ parity vectors $t$, an optimal solution to Equation T is found.

We now discuss the missing ingredients needed to make the previously discussed algorithm work. First, we explain how Lemma 7 is derived. To do so, we consider jump systems, where degree sequences of graphs and functions such as $f_{c,M}$ have been studied exhaustively [8, 39, 40, 35]. Murota [40] observed that $f_{c,M}$ describes a jump M-convex function, which is a valuated generalization of jump systems. In fact, recent work on the general factor problem [35] reveals that a similar jump M-convex function defined for weighted graph factorizations has additional exploitable properties. Informally, small steps, as in Definition 8, connecting points in the effective domain of such function may be rearranged in any order. For this reason, Kobayashi defines strongly base orderable (SBO) jump systems and a valuated extension. Our function $f_{c,M}$ defined over weighted uncapacitated perfect $b$-matchings can be seen to also satisfy the properties of Definition 9. As Lemma 7 holds for general SBO jump M-convex functions, we discuss our proof in terms of this abstract property. We use $⊑$ to denote the conformal partial order defined by $x⊑y$ if and only if $|x_i|\le |y_i|$ and $x_i{y}_i\ge 0$ for all $i$.

The alternating path argument employed by Kobayashi [35] to show that $\mathrm{𝟏}$-capacitated perfect $b$-matchings satisfy Definition 9 can be adapted to show the SBO jump M-convexity of $f_{c,M}$. For this, we use a known gadget construction that relates $b$-matchings to perfect matchings [45]. See [36] for the full proof.

Lemma 7 is derived by first showing that a $2$-step decomposition of a difference $z^{(2)}-z^{(1)}$ can be used to construct a small even step ${\sum }_{k\in I}{p}^{(k)}\in {\{-2,0,2\}}^m$ by combining some of the steps. Such an even, small step can be used to modify a pair of points $z^{(2)},z^{(1)}$ closer to each other while remaining on the lattice $2{\mathbb{Z}}^m+r$ and without increasing the sum of the function values on these points. Such pairwise modifications may then be exhaustively performed to move the points appearing in a convex combination towards the target $z$ as in Lemma 7 and obtain the required result. The proof of Lemma 7 is provided in Section 3.

The final ingredient needed to implement the FPT algorithm for Equation T is a good characterization of a suitable polyhedron $P_r$ that models the matching part of the ILP. We obtain this by letting $P_r$ be the convex hull of the vectors $(\omega ,z)\in ℝ\times (2{\mathbb{Z}}^m+r)$ for which $f_{c,M}(z)\le \omega$ and $z$ is in some bounding box. That is, $P_r$ is the epigraph of a natural convex extension of $f_{c,M}$ restricted to a bounding box. Since proximity arguments allow us to assume that $e$ and $g$ are finite, it is possible to bound $z$, see [11]. We obtain a polynomial time separation oracle for $P_r$ through the ellipsoid method [27] and by noting that $P_r$ can efficiently be optimized over³³3We note that it may be possible to derive a combinatorial separation algorithm, but this is not needed to establish the fixed-parameter tractability of Equation T. For a closely related separation problem, see [46].. This follows from the fact that weights associated with a vertex $i$ may be transferred to the edge weights of the incident edges, which shows that optimizing over $(\omega ,z)\in P_r$ corresponds to solving a minimum cost parity constrained $b$-matching problem. The parity constraints can straightforwardly be translated into constraints compatible with the polynomially solvable generalized matching problem [45, 15].

The randomized XP time algorithm for solving Equation W is obtained through a series of reductions. As a key intermediate step, we will employ a pseudo-polynomial reduction in [45] that transforms the minimum cost perfect $b$-matching to the minimum cost perfect matching problem on a graph with a total of ${\Vert b\Vert }_1$ vertices. In order to prevent an exponential blow-up in terms of the encoding size of $b$, we split the solution process up into parts in which $b$ may be bounded through the use of the Graver augmentation framework [17]. This is an exact local search framework which iteratively improves a primal solution to an ILP by taking smaller steps solving a similar, but slightly easier ILP. In these easier ILPs, the variable domains may be bounded by a function of the Graver complexity of the constraint matrix of the ILP. By Lemma 5, bounds on the variable domains translate into bounds on the right-hand side $b$. Before providing the required bounds, we first introduce the Graver augmentation framework and relevant definitions.

The Graver complexity of $A$ refers to norm bounds on $𝒢(A)$, and we are interested in $g_{\mathrm{\infty }}(A)=\max \{{\Vert g\Vert }_{\mathrm{\infty }}|g\in 𝒢(A)\}$ and $g_1(A)=\max \{{\Vert g\Vert }_1|g\in 𝒢(A)\}$, referring to the $\mathrm{\infty }$-norm and $1$-norm respectively. An oracle that can compute a single small improving step, used in the local search framework, is called a Graver-best oracle.

Such an oracle can be implemented by solving an ILP over variable domains of size at most $𝒪(g_{\mathrm{\infty }}(A))$, which we show to be polynomially bounded for fixed $h$ for Equation W. In this case, we may employ Lemma 5 to find that implementing a Graver-best oracle can by done by finding a minimum cost constrained $b$-matching where ${\Vert b\Vert }_1\le n{\Vert b\Vert }_{\mathrm{\infty }}=𝒪(n{g}_{\mathrm{\infty }}(A))$ is polynomially bounded. Theorem 12 concludes with how this Graver-best oracle can be used to optimize an ILP.

By constructing an auxiliary ILP with a trivial feasible solution to an ILP of the form W as done in [30], we can use Theorem 12 to find a feasible solution as well as optimize such solution. For this reason, we will assume that we are given a feasible solution to Equation W.

The polynomial bound on $g_{\mathrm{\infty }}(A)$ for fixed $h$ follows from literature: Berndt, Mnich and Stamm [7] show that the Graver basis elements of a matrix $M$ with ${\Vert M\Vert }_1\le 2$ are small.

Note that we may assume that $m=𝒪(n)$ after preprocessing. Lemma 3 in [16], which proves a Graver complexity bound for $n$-fold ILPs, reveals that Theorem 13 suffices to yield a polynomial bound on the Graver complexity of the composite matrix appearing in Equation W.

The number of Graver-best steps that need to be computed in Theorem 12 can be polynomially bounded by computing a solution to the LP relaxation of Equation W and using Theorem 3.14 in [29], which shows that the proximity of an ILP is bounded by $n$ times the obtained Graver bound from Corollary 14.

Thus, we may restrict the search of an optimal solution to Equation W to a polynomially bounded domain, which results in the needed bound on $c^{\top }x-c^{\top }{x}^{\ast }$ to apply Theorem 12. Now, after applying the pseudo-polynomial reduction to a perfect matching problem [45], which is compatible with additional constraints as noted in [10], we find that solving Equation W can be polynomially reduced to finding a minimum cost constrained perfect matching in a graph with polynomially many vertices. As all variables in this resulting problem are binary, we can condense all $h$ constraints into a single constraint by encoding the constraints in base-$B$ for sufficiently large $B$. This generalizes the reduction steps used in [6, 43] and only increases the coefficient size of the constraint matrix polynomially for fixed $h$. The resulting constrained perfect matching problem can then be solved with a randomized pseudo-polynomial algorithm such as the one by Mulmuley, Vazirani and Vazirani [38]. Combining all steps and binary searching on the values of the variables in an optimal solution yields the randomized XP time algorithm from Theorem 3.

To the best of our knowledge, the complexity of constrained matching where the objective is encoded in binary is still open. It is worth noting that the reduction chain shows that Equation W is polynomially equivalent to the exact matching problem, which aims to find a perfect matching in a graph with exactly a given target weight. Finding a deterministic pseudo-polynomial algorithm for this problem has been a central and intensively studied open problem for over four decades.

Finally, to complement the XP time complexity of the algorithm from Theorem 3, we reveal the W[1]-hardness of solving Equation W parameterized by $h$ in Theorem 4. This result is obtained through a parameterized reduction from the ILP problem, which is strongly W[1]-hard when parameterized by the number of constraints [13].

The essence of the reduction is to split every variable $x_i$ into $u_i$ many binary variables. The resulting binary variables can then be duplicated and linked through graph cycles to reduce the unary sized coefficients in $W$ and obtain a binary constraint matrix.