Faster Algorithms on Linear Delta-Matroids

As with matroids, an important class of delta-matroids are linear delta-matroids. A matrix $A$ is skew-symmetric if $A^T=-A$. Let $A$ be a skew-symmetric matrix with rows and columns indexed by a set $V$. Then $A$ defines a delta-matroid $𝐃(A)=(V,ℱ)$ where for $S\subseteq V$ we have $S\in ℱ$ if and only if the principal submatrix of $A$ indexed by $S$, denoted by $A[S]$, is non-singular. We refer to $𝐃(A)$ as a directly represented linear delta-matroid. More generally, the twist of a delta-matroid $D=(V,ℱ)$ by a set $S\subseteq V$, denoted $D\mathrm{\Delta }S$, is the delta-matroid with feasible sets

It is easy to check that $D\mathrm{\Delta }S$ is a delta-matroid. The twisting operation is also known as partial dualization, since the twist $D^{\ast }:=D\mathrm{\Delta }V$ corresponds to the dualization $M^{\ast }$ of a matroid $M$. A general representation of a linear delta-matroid is given as $D=𝐃(A)\mathrm{\Delta }S$ for some skew-symmetric matrix $A$ and twisting set $S$. A delta-matroid $D$ is even if all feasible sets have the same cardinality modulo 2; all linear delta-matroids are even. In addition, we consider projected linear delta-matroids, which is a delta-matroid $D=(V,ℱ)$ defined via existential projection over a set $X$ from a larger linear delta-matroid $D^{\prime }=𝐃(A)\mathrm{\Delta }S$ over ground set $V\cup X$. We denote this $D=D^{\prime }|X$, where $D$ has the feasible set

As a canonical example, the matching delta-matroid of a graph $G$ is directly represented by the Tutte matrix over $G$. The set of bases of a linear matroid forms a linear delta-matroid, and the independent sets form a projected linear delta-matroid, under natural representations (see Section 3.1 of the full version of the paper).

Underpinning algorithms on linear delta-matroids are a number of fundamental operations on skew-symmetric matrices. For a skew-symmetric matrix $A$ indexed by $V$ and a set $S\subseteq V$ such that $A[S]$ is non-singular, there is a pivoting operation that constructs a new skew-symmetric matrix $A^{\prime }=A\ast S$ such that for any $U\subseteq V$, $A^{\prime }[U]$ is non-singular if and only if $A[S\mathrm{\Delta }U]$ is. Via this operation, linear delta-matroids are closed under the contraction operation $D/T$ as well as deletion $D\setminus T$ (see Section 2 for the definitions). Another fundamental property of skew-symmetric matrices is the Pfaffian, defined as follows. Let $A$ be a skew-symmetric matrix with rows and columns indexed by $V$. The support graph of $A$ is the graph $G=(V,E)$ where $uv\in E$ if and only if $A[u,v]\ne 0$. Then the Pfaffian of $A$ is defined as

where $M$ ranges over all perfect matchings in $G$ and $\sigma (M)\in \{1,-1\}$ is a sign term. It holds that $detA={(\mathrm{Pf}A)}^2$, thus $A$ is non-singular if and only if $\mathrm{Pf}A\ne 0$. Via this connection to matchings, the Pfaffian forms a link between the combinatorial and algebraic aspects of linear delta-matroids, in a way that is often exploited in this paper. The Pfaffian also enjoys some useful algebraic properties, such as the Pfaffian sum formula and the Ishikawa-Wakayama formula, with clear combinatorial interpretations. See Section 2 for details.

Our first result, which supports the others, is the introduction of a new representation for linear delta-matroids. Recall that a linear delta-matroid $D=(V,ℱ)$ is represented as $D=𝐃(A)\mathrm{\Delta }S$ for a skew-symmetric matrix $A$ with rows and columns indexed by $V$. We refer to this as a twist representation. Although this representation is intimately connected to the structure of delta-matroids, it is less convenient for algorithmic purposes. For this, we introduce the contraction representation, representing a linear delta-matroid $D=(V,ℱ)$ as $D=𝐃(A)/T$ for a skew-symmetric matrix $A$ indexed by $V\cup T$. Thus, a set $F\subseteq V$ is feasible in $D$ if and only if $A[F\cup T]$ is non-singular.

We show that the representations are equivalent, and given a representation in one form, we can efficiently and deterministically construct one in the other; see Section 3.1. Thus contraction representations do not change the class of representable delta-matroids; however, we find that the contraction representation is more compatible with the algorithmic methods of linear algebra.

Next, we consider two methods of composing linear delta-matroids. Let $D_1=(V,{ℱ}_1)$ and $D_2=(V,{ℱ}_2)$ be given delta-matroids (padding the ground sets with dummy elements if necessary so that they are defined over the same ground set $V$). The union $D_1\cup D_2$ is the delta-matroid $D=(V,ℱ)$ where

i.e., the feasible sets in $D$ are the disjoint unions of feasible sets in $D_1$ and $D_2$. Additionally, the delta-sum $D_1\mathrm{\Delta }{D}_2$ is defined as the delta-matroid $D=(V,ℱ)$ with feasible sets

where $\mathrm{\Delta }$ denotes symmetric difference. Bouchet [2] and Bouchet and Schwärzler [4] showed that $D_1\cup D_2$ and $D_1\mathrm{\Delta }{D}_2$ are delta-matroids. Using properties of Pfaffians and the contraction representation, we show that furthermore, the union and delta-sum of linear delta-matroids are linear delta-matroids.

The construction is randomized, and takes an error parameter $\epsilon >0$ which controls the size of the field that the output delta-matroid is represented over. For this purpose, we say that an algorithm constructs an $\epsilon$-approximate representation of a delta-matroid $D=(V,ℱ)$ if it constructs a representation of a delta-matroid $D^{\prime }=(V,{ℱ}^{\prime })$ where ${ℱ}^{\prime }\subseteq ℱ$ and for every $F\in ℱ$ the probability that $F\in {ℱ}^{\prime }$ is at least $1-\epsilon$. Setting $\epsilon =O(1/2^n)$ where $n=|V|$ gives a representation that with good probability is correct for all subsets. However, this leads to a prohibitive field size, with significant overhead cost per field operation. Thus, for algorithmic applications, a smaller value of $\epsilon$ may be faster and sufficient.

As a warm-up, we first consider the problem of finding a max-weight feasible set in a given delta-matroid $D=(V,ℱ)$ with element weights $w:V\to ℝ$. Note that the weights may be negative, and since not all feasible sets have the same cardinality, unlike in matroids, they cannot simply be raised to be non-negative. Bouchet [3, 1] showed that there is a variant of greedy algorithm that solves this problem using only separation oracle calls. However, this requires $O(n)$ separation oracle calls, each of which requires $O(n^{\omega })$ field operations in linear representation. We show that, using the contraction representation, the max-weight feasible set problem in a linear delta-matroid reduces to finding a max-weight column basis of an $O(n)\times O(n)$ matrix, which can be done significantly faster.

For more intricate questions, the literature contains a range of problems over delta-matroids [3, 17, 29]. The most important are arguably the following.

• $\mathrm{■}$

  DM Intersection: Given delta-matroids $D_1=(V,{ℱ}_1)$ and $D_2=(V,{ℱ}_2)$, find a common feasible set $F\in {ℱ}_1\cap {ℱ}_2$.

• $\mathrm{■}$

  DM Parity: Given a delta-matroid $D=(V,ℱ)$ and a partition $\mathrm{\Pi }$ of $V$ into pairs, is there a feasible set in $D$ which is the union of pairs? More generally, find a feasible set $F\in ℱ$ to minimize the number of broken pairs, i.e., the number of pairs $p\in \mathrm{\Pi }$ with $|p\cap F|=1$.

Recall that the matroid versions differ in complexity; Matroid Intersection is tractable in the oracle model while Matroid Parity is intractable in general but tractable for linear matroids. However, due to the flexibility of delta-matroids, DM Intersection and DM Parity are equivalent under efficient transformations [17], hence both intractable in general. Given an instance $(D_1,D_2)$ of DM Intersection, a reduction to DM Parity is immediate by constructing the disjoint union of $D_1$ and $D_2$ [17]. In the other direction, given a delta-matroid $D=(V,ℱ)$ and a partition $\mathrm{\Pi }$ of $V$ into pairs, let $D_{\mathrm{\Pi }}$ be the matching delta-matroid of the graph with edge set $\mathrm{\Pi }$. Thus the feasible sets of $D_{\mathrm{\Pi }}$ are precisely the sets $S\subseteq V$ with no broken pairs, and the DM Parity instance $(D,\mathrm{\Pi })$ has a perfect solution – i.e., one with no broken pairs – if and only if $D$ and $D_{\mathrm{\Pi }}$ have a common feasible set. For linear-delta-matroids the problems are solvable in $O(n^{\omega +1})$ time due to Geelen et al. [17].

Additionally, the following problems have been considered. Again, due to the flexibility of delta-matroids, these problems are related to one another; see [17, 29]. The previously fastest algorithm for all of them is by Geelen et al. [17] at $O(n^{\omega +1})$ time. Let $D_1=(V,{ℱ}_1)$ and $D_2=(V,{ℱ}_2)$ be given delta-matroids.

• $\mathrm{■}$

  DM Covering: Given $D_1$ and $D_2$, find $F_1\in {ℱ}_1$, $F_2\in {ℱ}_2$ with $F_1\cap F_2=\mathrm{\varnothing }$ to maximize $|F_1\cup F_2|$

• $\mathrm{■}$

  DM Delta-Covering: Given $D_1$ and $D_2$, find $F_1\in {ℱ}_1$, $F_2\in {ℱ}_2$ to maximize $|F_1\mathrm{\Delta }{F}_2|$

• $\mathrm{■}$

  DM Partition: Given $D_1$ and $D_2$, find a partition $V=P\cup Q$ such that $P\in {ℱ}_1$ and $Q\in {ℱ}_2$

The variant of DM Covering where the disjointness constraint is dropped reduces to Matroid Union, since the maximal feasible sets of a delta-matroid form a matroid, hence is of less interest for delta-matroids.

Using the methods of the previous subsection, the decision versions of the above for linear and projected linear delta-matroids all reduce to computing the rank of an $O(n)\times O(n)$ skew-symmetric matrix. Indeed, consider DM Delta-Covering. Assume that $D_1$ and $D_2$ are given in some linear representation and let $D=𝐃(A)/T=D_1\mathrm{\Delta }{D}_2$. Then a set $F\subseteq V$ is a solution $F=F_1\mathrm{\Delta }{F}_2$ to the delta-covering problem if and only if $F\cup T$ is a basis of $A$. Similarly, DM Covering reduces to finding a maximum feasible set in $D_1\cup D_2$. DM Intersection and DM Partition are asking whether $\mathrm{\varnothing }$ is feasible in $D_1\mathrm{\Delta }{D}_2$ and $D_1\cup D_2$, respectively. For DM Parity, as above let the input be $(D,\mathrm{\Pi })$ and construct the delta-matroid $D_{\mathrm{\Pi }}$. Then DM Parity reduces to finding the rank of $D\mathrm{\Delta }{D}_{\mathrm{\Pi }}$ (or indeed $D\cup D_{\mathrm{\Pi }}$). Thus the decision versions of all the above problems can be solved by a randomized algorithm using $O(n^{\omega })$ field operations given linear representations of $D$ resp. $D_1$ and $D_2$ thanks to Theorem 2.

For general delta-matroids, these problems are as hard as Matroid Parity: Clearly, DM Parity is as hard as Matroid Parity. Given an instance $(D,\mathrm{\Pi })$ of DM Parity, let $D_1=D$ and $D_2=D_{\mathrm{\Pi }}$. Then, the following is equivalent:

• $\mathrm{■}$

  The instance $(D,\mathrm{\Pi })$ has a perfect solution for DM Parity

• $\mathrm{■}$

  $(D_1,D_2)$ has a solution of cardinality $V(D)$ for DM Covering

• $\mathrm{■}$

  $(D_1,D_2)$ has a solution of cardinality $V(D)$ for DM Delta-Covering

• $\mathrm{■}$

  $(D_1,D_2)$ is a yes-instance of DM Partition

This shows that these problems are all intractable in the oracle model. For linear delta-matroids, achieving $O(n^{\omega })$ time is arguably the best possible.

For the search versions, the situation changes slightly. Although these problems can be reduced to straightforward questions about non-singularity or rank of a skew-symmetric matrix $A$ the resulting solution (e.g., a basis of $A$) provides only limited insight into the solution of the original problem. For example, if $(D,\mathrm{\Pi })$ is an instance of DM Parity, then the rank of $D\mathrm{\Delta }{D}_{\mathrm{\Pi }}$ tells us the number of broken pairs in an optimal solution (and a maximum feasible set tells us the set of broken pairs in such a solution), it does not give us the feasible set $F\in ℱ(D)$ that is the “actual” solution. Similarly, for DM Covering and DM Delta-Covering the above reduction gives us the set $F=F_1\cup F_2$ respectively $F=F_1\mathrm{\Delta }{F}_2$ but not the pair $(F_1,F_2)$. We refer to this (the set $F$ for DM Parity and the pair $(F_1,F_2)$ for the other four problems) as the witness.

The algorithm of Geelen et al. [17] actually computes the witness for Linear DM Parity, and can be implemented in $O(n^{\omega +1})$ field operations. Applying self-reducibility over the above-mentioned representation to find a witness would reproduce the same running time. Using methods of Harvey [18] we show the following improved result. These methods also underpin the currently fastest algorithm for linear matroid parity [6]. The condition of field size is for simplicity; given representations over a common field $𝔽$ we can easily move to a large enough extension field of $𝔽$.

Via the reductions given above, this lets us find a witness for all problems considered. For Linear DM Covering, we would first find the optimal set $F=F_1\cup F_2$ as above, then solve Linear DM Partition for the instance induced by $F$; for the remaining problems the solution is straightforward. See the full version of the paper for details.

Finally, we consider the weighted versions of the above problems. Again, the picture becomes slightly different. For DM Partition, there is no sensible weighted version. For DM Covering and DM Delta-Covering, the natural weight is the weight of the solution set $F$, in which case the problem is solved in strongly polynomial time of $O(n^{\omega })$ field operations using Theorem 2 and 3. For DM Parity, we would attach weights to the pairs, and consider two weighted versions. In the first version, we want to minimize the weight of the broken pairs; this problem is solved in $O(n^{\omega })$ field operations using Theorem 2 and 3. For the more interesting version, we assume that there exists a perfect delta-matroid parity solution, and we wish to maximize the weight of such a set. This version, finally, is equivalent to the weighted version of DM Intersection, which we focus on, and directly generalizes Weighted Matroid Parity. We use the matrix representation of the problem to construct a solution via algebraic methods.

As a special case, even the unit weight version, Maximum Linear DM Intersection, is an interesting problem which up to now has had no polynomial-time solution. Kakimura and Takamatsu [21] asked this as an open problem, and provided algorithms for some special cases of it. We solve the general case with a randomized algorithm.

By self-reducibility, the search version can thus be solved by a factor $O(n)$ overhead.

Removing the overhead on this result appears significantly harder. Indeed, a similar overhead exists for algorithms for weighted linear matroid parity [6], and even removing the overhead for Weighted Perfect Matching was significantly non-trivial [9]. We leave this as a (challenging) open question.

We now review some applications of the results. Not all of these results are new, but they serve to demonstrate the applicability of the setting.

One area of application is graph matching and factor problems. In the general factor problem, we are given a graph $G=(V,E)$, and a set of integers $f(v)\subseteq \mathbb{N}$ for each vertex $v\in V$. The task is to find a spanning subgraph $H=(V,F)$ such that ${\mathrm{deg}}_H(v)\in f(v)$ for every vertex $v\in V$. Cornuéjols [7] showed that this problem is polynomial-time solvable if each $f(v)$ has gaps of length at most 1, but becomes NP-hard otherwise.

For each $v\in V$, let $\delta (v)$ be the set of edges incident with $v$ and define ${ℱ}_v=\{S\subseteq \delta (v)\mid |S|\in f(v)\}$. Under the gap-1 condition, $D_v=(\delta (v),{ℱ}_v)$ forms a delta-matroid for every $v\in V$. We refer to $D_v$ as a symmetric delta-matroid.

The general factor problem can be reformulated as a DM Intersection problem. We define two delta-matroids on the ground set $E_2=\{(e,v)\mid e\in E,v\in e\}$, where each edge $uv\in E$ is represented by $(uv,u)$ and $(uv,v)$. Let $D_E$ be the matching delta-matroid of $G^{\prime }$, where $G^{\prime }$ is the graph on $E_2$ with edges between the pairs $(uv,u)$ and $(uv,v)$ for each edge $uv\in E$. Furthermore, let $D_f$ be the direct sum of symmetric delta-matroids $D_v=({\partial }_v,{ℱ}_v)$ with ${\partial }_v=\{(uv,v)\mid uv\in E\}$ and ${ℱ}_v=\{S\subseteq {\partial }_v\mid |S|\in f(v)\}$. Then the intersection of $D_E$ and $D_f$ captures the general factor problem.²²2We find it interesting that in this formulation, the General Factor problem is tractable if and only if every set system $D_v$, $v\in V$ forms a delta-matroid. For more such occurrences, see the Boolean Edge CSP [13, 22] and Boolean Planar CSP [11, 22] problems, both of which appear (roughly speaking) to be interestingly tractable if and only if the constraints form delta-matroids in natural ways.

When the symmetric delta-matroids correspond to cases where $f(v)=\{a,a+2,\mathrm{\dots },b\}$ and $f(v)=\{a,a+1,\mathrm{\dots },b\}$, they are linear and projected linear, respectively. The associated factor problems are known as parity $(a,b)$-factors and $(a,b)$-factors. Thus, these problems can be reduced to Linear DM Intersection, and solved via Corollary 4 (although a naive formulation gives only time $O(m^{\omega })$ here). The algebraic formulation of Gabow and Sankowski [16] for the $f$-factor problem, where $|f(v)|=1$ for all $v\in V$, can essentially be derived from this method in a generic way using the Ishikawa-Wakayama formula (see Lemma 10), as the corresponding systems form matroids. See also recent work on weighted general factors [10, 23].

For another example, let $G=(V,E)$ be a graph and $T\subseteq V$ a set of terminals. Let $𝒮$ be a partition of $T$. An $𝒮$-path packing is a vertex-disjoint packing of paths where every path has endpoints in distinct parts of $𝒮$ and internal vertices disjoint from $T$. A classical theorem of Mader shows a min-max theorem characterizing the maximum number of paths in an $𝒮$-path packing, generalizing Menger’s theorem and the Tutte-Berge formula; see Schrijver [32]. Wahlström [36] recently showed the following. Let a set $F\subseteq T$ be feasible if there is an $𝒮$-path packing whose set of endpoints is precisely $F$. Then $D=(T,ℱ)$ is a linear delta-matroid. Then, via Linear DM Intersection as above, we can solve the following “$𝒮$-factor” problem: Given $G$, $𝒮$ and a prescribed set of degrees $f(T_i)\in \mathbb{N}$, $T_i\in 𝒮$, is there an $𝒮$-path packing in $(G,𝒮)$ where precisely $f(T_i)$ paths have an endpoint in $T_i$? The generalizations to $(a,b)$-factors and $(a,b)$-parity factors can be handled similarly.

Section 2 contains all definitions. Section 3 gives results about new representations, and Section 4 gives the algorithmic results. Section 5 concludes the paper. For missing proofs (for results marked with $\mathrm{★}$) and additional results, including a more extensive related work review, see the full version of the paper.

Let $D=(V,ℱ)$ be given as $D=𝐃(A)\mathrm{\Delta }S$, $S\subseteq V$. For a set $T$ of size $|S|$, define a skew-symmetric matrix $A^{\prime }$ over $V\cup T$ by

where $I$ is an identity matrix. Note that the support graph of $A^{\prime }[T\cup S]$ has a unique perfect matching (namely, every vertex in $T$ has degree one), thus $\mathrm{Pf}{A}^{\prime }[T\cup S]=\pm 1$ and $A^{\prime }[T\cup S]$ is non-singular. Thus, we can construct the matrix $A^{\ast }=A^{\prime }\ast (T\cup S)$. Note that

and consequently, the result of pivoting is

Clearly, $A^{\ast }$ can be constructed in $O(n^2)$ time. Now by Lemma 8, for any $F\subseteq V$, $A^{\ast }[F\cup T]$ is non-singular if and only if $A^{\prime }[(F\cup T)\mathrm{\Delta }(S\cup T)]=A^{\prime }[F\mathrm{\Delta }S]$ is. Since $F\mathrm{\Delta }S\subseteq V$ and $A^{\prime }[V]=A[V]$, this is equivalent to $F\in ℱ(D)$, thereby showing that $𝐃(A^{\ast })/T$ is a contraction representation of $D$. $◀$

Let $S\subseteq V$ be a set such that $A[S\cup T]$ is non-singular; such a set exists since $ℱ(D)\ne \mathrm{\varnothing }$ by assumption, and can be found efficiently over $A$. Then $A^{\prime }=A\ast (S\cup T)$ is well-defined. Let $A^{\ast }=A^{\prime }\setminus T$. Observe that $D=𝐃(A)\mathrm{\Delta }S$, that is, for every $F\subseteq V$, $A^{\ast }[F\mathrm{\Delta }S]=A^{\prime }[F\mathrm{\Delta }S]$ is non-singular if and only if $A[(F\mathrm{\Delta }S)\mathrm{\Delta }(S\cup T)]=A[F\cup T]$ is non-singular by Lemma 8. All operations above can be performed in matrix multiplication time. $◀$

We also observe that the contracted set $T$ in a representation of a delta-matroid $D=(V,ℱ)$ never needs to be larger than $|V|$.

Let $D_1=(V,{ℱ}_1)=𝐃(A_1)/T_1$ and $D_2=(V,{ℱ}_2)=𝐃(A_2)/T_2$, w.l.o.g. represented over the same ground set and with $T_1\cap T_2=\mathrm{\varnothing }$. Create three copies $V\uplus V_1\uplus V_2$ of the ground set and define three sets of variables $Y_i=\{y_{v,i}\mid v\in V\}$, $i=1,2,3$. Let

where $B_i$, $i=1,2,3$ is a diagonal matrix whose $v$:th entry is $y_{v,i}$. Note that $A$ can be seen as the sum of the representation of the disjoint union of $D_1$ and $D_2$ and the Tutte matrix of the graph consisting of a disjoint union of triangles on $\{v,v^1,v^2\}$ for every $v\in V$, where $v^i$ is the copy of $v$ in $V_i$, $i=1,2$. It now follows from the Pfaffian sum formula (Lemma 9) that $𝐃(A)/(V_1\cup T_1\cup V_2\cup T_2)$ is an $\epsilon$-approximate representation of $D_1\mathrm{\Delta }{D}_2$. $◀$

Recall that a projected linear delta-matroid $D=(V,ℱ)$ is a delta-matroid represented as $D=D^{\prime }|X$ where $D^{\prime }=(V\cup X,{ℱ}^{\prime })$ is a linear delta-matroid. Projections of linear delta-matroids were studied by Geelen et al. [17] in the context of linear delta-matroids over fields of characteristic 2, and by Kakimura and Takamatsu [21] regarding generalizations of constrained matching problems. We observe that if $D$ is linear, then the even (respectively odd) sets of $D|X$ form a linear delta-matroid, and that every projected linear delta-matroid $D|X$ can be represented via an elementary projection.

The following hold: $w(F)=w^{\prime }(F\setminus N)-w^{\prime }(F\cap N)$ and $w^{\prime }(F\mathrm{\Delta }N)=w^{\prime }(F\setminus N)+w^{\prime }(N\setminus F)$. Thereby $w(F)-w^{\prime }(F\mathrm{\Delta }N)=-w^{\prime }(N)=w(N)$ as promised. $◀$

The problem of finding a max-weight feasible set in a linear delta-matroid in contraction representation now reduces to the problem of finding a max-weight basis of a linear matroid.

See 2

By Lemma 17, it suffices to prove the statement for linear delta-matroids.

Let $D=(V,ℱ)$ and $w:V\to \mathbb{Q}$ be given as input, and as above define , $D^{\prime }=D\mathrm{\Delta }N$ and $w^{\prime }:V\to \mathbb{Q}$ where $w^{\prime }(v)=|w(v)|$ for all $v\in V$. Let $𝐃(A)/T$ be a contraction representation of $D^{\prime }$, which can be constructed using Lemma 12. Finally, order the columns of $A$ to begin with $T$ and thereafter elements $v\in V$ in order of non-increasing weight $w^{\prime }(v)$. Let $B$ be a lex-min column basis for $A$ with respect to this ordering. Then $B$ can be computed in $O(n^{\omega })$ field operations over $A$ (see e.g., [5]), and $B$ is a max-weight column basis of $A$ with respect to the weights $w^{\prime }$. We claim that $F=(B\setminus T)\mathrm{\Delta }N$ is a max-weight feasible set in $D$. For this, let $F^{\ast }$ be a max-weight feasible set in $D$ with respect to the weights $w$. Then by Lemma 18, $F^{\ast }\mathrm{\Delta }N$ is a max-weight feasible set in $D^{\prime }$ with respect to the weights $w^{\prime }$. Hence $B^{\prime }=(F^{\ast }\mathrm{\Delta }N)\cup T$ is feasible in $𝐃(A)$ and $w^{\prime }(B\setminus T)\ge w^{\prime }(B^{\prime }\setminus T)=w(F^{\ast })-w(N)$. On the other hand, let $B$ be a lex-min basis of $A$ in the above ordering. Then $T\subseteq B$ by construction. By Lemma 18, $F=(B\setminus T)\mathrm{\Delta }N$ is a feasible set in $D$ with $w(F)=w^{\prime }(B\setminus T)+w(N)\le w(F^{\ast })$. Hence $w^{\prime }(B\setminus T)=w(F^{\ast })-w(N)$ by sandwiching and $w((B\setminus T)\mathrm{\Delta }N)=w^{\prime }(B\setminus T)+w(N)=w(F^{\ast })$. $◀$