betaFeedback

WorksComputer Science

Binary Affine Optimization with Nearly-Graphic Constraint Matrices

Abstract

We present a polynomial-time algorithm for binary affine optimization with a linear objective when every column of the constraint matrix has Hamming weight at most 2, and prove that the problem is NP-hard when every column of the constraint matrix has Hamming weight exactly 3. We obtain fixed-parameter tractable (FPT) algorithms for the unrestricted problem provided that a nearly-graphic certificate is given, where the certificate roughly measures how far the constraint matrix is from having columns of Hamming weight at most 2. We apply our FPT algorithm to Max-Lin2_2 on graphs and obtain FPT algorithms parameterized by the contraction distance and contraction rank of the graph, utilizing the concept of Eulerian-spanning set. In the case of contraction distance, another FPT algorithm can be used to find the corresponding certificate; that is, we obtain an FPT algorithm that requires no information beyond the problem instance itself.

Introduction

Many exact optimization, decoding, and graph-labeling problems over binary variables can be written as, or converted to the following NP-hard binary affine optimization, with a linear objective. (For the notations in the introduction, one can look up them in “Basic assumptions” at the end of it.)

Problem 1.1 (binary affine optimization with a linear objective, or BAO). Given A∈F2n×mA \in\mathbb{F}_2^{n \times m}, b∈F2nb \in\mathbb{F}_2^n, Δ∈Rm\Delta\in\mathbb{R}^m, solve the following problem and find an optimal assignment:

min⁡{ΔTx:Ax=b,x∈F2m},(1)\min\{\Delta^{\mathsf{T}}x : Ax=b,\quad x \in\mathbb{F}_2^m\}, \tag*{(1)}

where ΔTx\Delta^{\mathsf{T}}x is evaluated in R\mathbb{R}, and elements 0,1∈F20,1 \in\mathbb{F}_2 are regarded as 0,1∈R0,1 \in\mathbb{R}, respectively.

Special cases of BAO are closely connected with classical problems in coding theory and with optimization problems for linear systems over F2\mathbb{F}_2. If Ax=bAx=b is feasible, then its solution set is an affine coset of the linear code ker⁡A\ker A. In the special case Δj=1\Delta_j=1 for all jj, BAO is exactly the problem of finding a minimum-Hamming-weight representative of a prescribed coset, i.e., the syndrome-decoding or coset-leader problem for a binary linear code. The general decoding problem was shown to be NP-complete [3]. Related minimization and approximability questions for linear systems, including the minimization of the number of nonzero variables and binary-restricted variants, were studied systematically [2].

Weighted systems of linear equations over F2\mathbb{F}_2, usually formulated as Max-Lin2_2, can also be converted into the form of BAO and provide another closely related viewpoint. Max-Lin2_2 contains several graph optimization problems, such as MaxCut and signed frustration. Parameterized complexity results for Max-Lin2_2 and its sparse-occurrence cases were developed [4, 5], where the approximation problem was considered. The W[1]-hardness of Max-Lin2_2, parameterized by the total weight of violated equations, was proved [4]. The problem of finding an assignment for which the total weight of satisfied equations exceeds that of random guessing was investigated [5], where the parameter is the gap from half the total weight and the special case in which every equation contains at most rr variables was studied.

In this paper, we study the complexity of BAO, present fixed-parameter tractable (FPT) algorithms, and explore their applications to Max-Lin2_2 (where we allow real weights). As far as we are aware, both our approach and our results are structurally new. For the BAO problem, our results focus on the columns of the constraint matrix whose Hamming weight is at least three, which, to the best of our knowledge, have not been considered elsewhere. For Max-Lin2_2, we consider the exact problem rather than the approximation problem. We convert Max-Lin2_2 into the form of BAO and solve the latter, rather than attempting to solve it directly as in [4, 5].

We now describe the results, techniques, and key concepts of this work. We first show that if every column of AA has Hamming weight at most 22, then BAO can be solved in polynomial time. For convenience, we say that AA or, equivalently, the BAO problem, satisfies the weight-two condition when this holds.

Theorem 1.2. Let A∈F2r×mA \in\mathbb{F}_2^{r \times m} be a matrix satisfying the weight-two condition, and let b∈F2rb \in\mathbb{F}_2^r, w∈Rmw \in\mathbb{R}^m. Then the feasibility of Ax=bAx=b can be determined in polynomial time. If the system is feasible, both the value

min⁡{wTx:Ax=b, x∈F2m}(2)\min\{w^{\mathsf{T}}x : Ax=b,\ x \in\mathbb{F}_2^m\} \tag*{(2)}

and an optimal vector xx can be computed in polynomial time.

A constraint matrix satisfying weight-two condition has a graph-incidence interpretation. A BAO instance with such a constraint matrix can be converted to a minimum-weight TT-join problem on a graph, for which classical matching methods provide the algorithmic foundation [6].

On the other hand, we show that even when every column of AA has Hamming weight exactly 33, BAO is still NP-hard. This establishes the tightness of the weight-two condition.

Theorem 1.3. The following problem is NP-complete: given A∈F2r×mA \in\mathbb{F}_2^{r \times m} in which every column has Hamming weight three, and an integer q∈Z≥0q \in\mathbb{Z}_{\geq0}, decide whether there is x∈F2mx \in\mathbb{F}_2^m such that

Ax=1,wt⁡(x)≤q.Ax=1,\qquad\operatorname{wt}(x) \leq q.

Consequently, minimizing the Hamming weight wt⁡(x)\operatorname{wt}(x) subject to Ax=1Ax=1 is NP-hard even when every column of AA has Hamming weight three.

The proof of Theorem 1.3 is in Appendix § 10.

With Theorem 1.2, we can develop FPT algorithms for general BAO. We start from a simple application. Let JJ be the indexes of columns of AA with Hamming weight at least 3. We enumerate all possibilities of xJx_J. After xJx_J is fixed, the remaining of the constraint is of the form AJ‾xJ‾=b′A_{\overline{J}}x_{\overline{J}}=b', where AJ‾A_{\overline{J}} satisfies the weight-two condition. Therefore the remaining problem can be solved within polynomial time, and the total running time must be O(2∣J∣max⁡{r,m}O(1))O(2^{|J|}\max\{r,m\}^{O(1)}). However, we can apply this algorithm with some twist. First, for any U∈GL(r,2)U\in\mathrm{GL}(r,2), Ax=b⇔UAx=UbAx=b\Leftrightarrow UAx=Ub. Therefore we can pick any U∈GL(r,2)U\in\mathrm{GL}(r,2) and instead consider the columns of UAUA of Hamming weight at least 3. By applying the row operation UU to AA, the number of columns of Hamming weight at least 3 can be reduced. This leads to the concept of nearly-graphic certificate.

Definition 1.4. Let A∈F2r×mA\in\mathbb{F}_2^{r\times m}. A pair (U,J)(U,J), U∈GL(r,2)U\in\mathrm{GL}(r,2), J⊆[m]J\subseteq[m] satisfying ∀j∈[m]∖J\forall j\in[m]\setminus J, wt⁡((UA)j)≤2\operatorname{wt}((UA)_j)\leq2 is called a nearly-graphic certificate for AA.

Let CA\mathcal{C}_A collect all nearly-graphic certificates for AA. From now on, if AA is clear from the context, we will simply call (U,J)(U,J) a nearly-graphic certificate. The word nearly-graphic comes from the fact that a binary matrix satisfying the weight-two condition can be converted to the incidence matrix of some graph. For the enumeration of coordinates in JJ, we may not have to go through all 2∣J∣2^{|J|} possibilities of xJx_J. Instead, we can consider Im⁡((UA)J)\operatorname{Im}((UA)_J), enumerate all elements in Im⁡((UA)J)\operatorname{Im}((UA)_J), and compute an optimal xJx_J for each of the images. We have ∣Im⁡((UA)J)∣=2rank⁡((UA)J)|\operatorname{Im}((UA)_J)|=2^{\operatorname{rank}((UA)_J)}. Moreover, rank⁡((UA)J)=rank⁡(AJ)≤∣J∣\operatorname{rank}((UA)_J)=\operatorname{rank}(A_J)\leq|J|, which is an advantage. This leads to the definition of the following nearly-graphic parameters.

Definition 1.5 (nearly-graphic parameters). Let A∈F2r×mA\in\mathbb{F}_2^{r\times m}. Define the following parameters:

exc⁡2(A)=min⁡(U,J)∈CA∣J∣,(3)\operatorname{exc}_2(A)=\min_{(U,J)\in\mathcal{C}_A}|J|, \tag*{(3)}
rex⁡2(A)=min⁡(U,J)∈CArank⁡(AJ).(4)\operatorname{rex}_2(A)=\min_{(U,J)\in\mathcal{C}_A}\operatorname{rank}(A_J). \tag*{(4)}

If (U,J)(U,J) is a nearly-graphic certificate for AA, then its support size is ∣J∣|J|, and its non-graphic rank is

ρ(U,J)=rank⁡((UA)J)=rank⁡(AJ).(5)\rho(U,J)=\operatorname{rank}((UA)_J)=\operatorname{rank}(A_J). \tag*{(5)}

The notations exc, rex are abbreviations of the phrases “exceptional columns” and “rank of exceptional columns”, respectively. When a nearly-graphic certificate (U,J)(U,J) for AA is provided, we obtain two FPT algorithms solving BAO, parameterized by ∣J∣|J| and rank⁡(AJ)\operatorname{rank}(A_J), respectively.

Theorem 1.6. Let (A,b,Δ)(A,b,\Delta) be an instance of BAO, and N=max⁡{r,m}N=\max\{r,m\}. Suppose a nearly-graphic certificate (U,J)(U,J) is given. Put k=∣J∣k=|J| and ρ=rank⁡(AJ)=rank⁡((UA)J)\rho=\operatorname{rank}(A_J)=\operatorname{rank}((UA)_J). The validity of the supplied certificate can be checked in time polynomial in NN. If it is valid, then there are two algorithms finding the optimum and an optimal assignment in O(2rNO(1))O(2^rN^{O(1)}) and O(2kNO(1))O(2^kN^{O(1)}) time, respectively.

We explore the application of Theorem 1.6 and consider the weighted Max-Lin2_2 problem, which is defined as follows.

Definition 1.7 (weighted Max-Lin2_2). Let M∈F2q×nM \in\mathbb{F}_2^{q \times n}, d∈F2qd \in\mathbb{F}_2^q, w∈Rqw \in\mathbb{R}^q. We aim to compute

min⁡{wTz:z=Mx+d, z∈F2q},\min\{w^\mathsf{T}z : z = Mx + d,\ z \in\mathbb{F}_2^q\},

and an optimal vector zz. Here wTzw^\mathsf{T}z is evaluated in R\mathbb{R}, and elements 0,1∈F20,1 \in\mathbb{F}_2 are regarded as 0,1∈R0,1 \in\mathbb{R}, respectively.

The form of Max-Lin2_2 is different from that of BAO, hence we need to convert it. This is done by computing a representation of the left-nullspace of MM. Specifically, let HH be a matrix whose row space is ker⁡MT\ker M^\mathsf{T} (by ker⁡\ker we always mean the right-nullspace of a matrix, that’s why the left-nullspace of MM reads ker⁡MT\ker M^\mathsf{T} here). Then we have

{Mx+d:x∈F2n}={z∈F2q:Hz=Hd}.(6)\{Mx+d : x \in\mathbb{F}_2^n\} = \{z \in\mathbb{F}_2^q : Hz = Hd\}. \tag*{(6)}

Indeed, if z=Mx+dz=Mx+d, then HM=0HM=0, and hence Hz=HdHz=Hd. Conversely, if Hz=HdHz=Hd, then z+d∈ker⁡Hz+d \in\ker H. Since the row space of HH is ker⁡MT\ker M^\mathsf{T},

ker⁡H=(ker⁡MT)⊥=Im⁡M.\ker H = (\ker M^\mathsf{T})^\perp= \operatorname{Im} M.

Thus z+d=Mxz+d=Mx for some xx, which proves (6). Weighted Max-Lin2_2 is therefore equivalent to

min⁡{wTz:Hz=Hd, z∈F2q}.(7)\min\{w^\mathsf{T}z : Hz = Hd,\ z \in\mathbb{F}_2^q\}. \tag*{(7)}

By the conversion, we can recover an optimal assignment of xx if we know the optimal assignment of (7) in polynomial time. Therefore, if a nearly-graphic certificate (U,J)(U,J) of HH is provided, we can apply Theorem 1.6 and solve Max-Lin2_2 in 2rank⁡(HJ)NO(1)2^{\operatorname{rank}(H_J)}N^{O(1)}, or 2∣J∣NO(1)2^{|J|}N^{O(1)} time.

However, the choice of HH is not unique in general. Therefore, if a nearly-graphic certificate is to be provided, one must first specify HH, which is unrealistic. Hence we make further exploration by considering a special case of Max-Lin2_2, i.e. Max-Lin2_2 on graphs. For brevity, here we omit the original form of Max-Lin2_2 on graphs, which is in § 4. We will show that, for Max-Lin2_2 on a graph G=(V,E)G=(V,E), HH must be taken to represent the cycle space of GG. This leads to the concept of Eulerian-spanning set of GG, which is a multiset of vectors spanning the cycle space of GG. Therefore we can take HH to be the incidence matrix of a Eulerian-spanning set B\mathcal{B} of GG. Denote the matrix by ABA_{\mathcal{B}} and we get the following BAO problem:

min⁡{wTz:ABz=ABc, z∈F2E}.\min\{w^\mathsf{T}z : A_{\mathcal{B}}z = A_{\mathcal{B}}c,\ z \in\mathbb{F}_2^E\}.

We will show that, exc⁡2(AB)\operatorname{exc}_2(A_{\mathcal{B}}), rex⁡2(AB)\operatorname{rex}_2(A_{\mathcal{B}}) are independent from the choice of B\mathcal{B}, and are equal to the contraction distance and contraction rank of GG, respectively. The contraction distance is the minimum number of edges to contract to make GG planar, while the contraction rank is a little more complicated and will be explained in § 5. Moreover, JJ can be simply taken to be the set of edges whose contraction makes GG planar. More importantly, we can use the FPT algorithms in [10, 1] to compute the contraction distance of GG, and find the corresponding edge set. Therefore we get an FPT algorithm for Max-Lin2_2 on graphs parameterized by contraction distance, which needs no information other than the problem itself.

Theorem 1.8. Let G=(V,E)G=(V,E) be a graph, and ctr⁡(G)\operatorname{ctr}(G) be the contraction distance of GG. One can solve weighted Boolean Max-Lin2_2 on a graph G=(V,E)G=(V,E), and find an optimal assignment in time F(ctr⁡(G))max⁡{∣V∣,∣E∣}O(1)F(\operatorname{ctr}(G))\max\{|V|,|E|\}^{O(1)}, where FF is a function independent of ∣V∣,∣E∣|V|,|E|.

A formal definition of ctr⁡(G)\operatorname{ctr}(G) can also be found in § 5. We explore applications of our algorithms for Max-Lin2 to specific graph optimization problems. Specifically, we consider MaxCut and signed frustration, to which Theorem 1.8 can be applied directly. Moreover, when the edge set JJ is provided, we design a more refined algorithm that reduces the exponent with respect to max⁡{∣V∣,∣E∣}\max\{|V|, |E|\}. This algorithm generalizes the result of [7], which considers nonnegative weights, to the case of arbitrary real weights. A further application of this algorithm yields an FPT algorithm for Max-Lin2 parameterized by the crossing number, provided that a corresponding drawing is given.

As mentioned earlier, FPT algorithms exist for computing the contraction distance of GG. However, we are not aware of any FPT algorithm for computing the contraction rank of GG, even though the latter is generally smaller and thus has the potential to yield faster algorithms. We investigate the possible separation between the contraction distance and the contraction rank of GG. In Appendix § 11, we show that the contraction distance can be arbitrarily larger than the contraction rank.

Paper organization Section 2 gives the polynomial algorithms for BAO under the weight-two condition. Section 3 gives the two FPT algorithms for BAO. Section 4 converts Max-Lin2 on graphs to BAO using the concept of Eulerian-spanning set. Section 5 characterizes the nearly-graphic parameters of ABA_B by the contraction rank and the contraction distance, and gives FPT algorithms for solving Max-Lin2 on graphs.

Basic assumptions

  • Every graph is assumed to be finite and undirected. Graphs are allowed to have multiple edges and loops. By simple graph we mean graphs without multiple edges and loops. If GG is a graph, then c(G)c(G) denotes the number of connected components of GG. If G=(V,E)G=(V,E) is a graph and V′⊆VV' \subseteq V, then G[V′]G[V'] is the subgraph induced by V′V'.

  • Copies of the same element in a multiset are treated differently. For an integer t≥0t \ge0, write [t]={1,…,t}[t]=\{1,\ldots,t\}, with the convention [0]=∅[0]=\varnothing.

  • Unless stated otherwise, all vector spaces, matrices, and linear-algebraic operations in Sections 2–5 are over F2\mathbb{F}_2. For a binary vector xx, let supp⁡(x)\operatorname{supp}(x) and wt⁡(x)\operatorname{wt}(x) denote its support and Hamming weight. For J⊆[m]J \subseteq[m] where mm is clear from the context, write J‾=[m]∖J\overline{J}=[m]\setminus J and use xJx_J and AJA_J for the corresponding subvectors and column submatrices. The notation AjA_j denotes the jjth column of AA, and 1\mathbf{1} denotes the all-ones vector of the dimension determined by context. The rank of an empty matrix is zero.

  • For the vector space F2n\mathbb{F}_2^n, n∈Z+n \in\mathbb{Z}^+, the non-degenerate symmetric bilinear form ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle is taken in the obvious way, i.e. ⟨x,y⟩=∑i∈[n]xiyi\langle x,y\rangle=\sum_{i\in[n]}x_i y_i. Orthogonal subspaces are taken with respect to this bilinear form.

Polynomial algorithm under weight-two condition

To solve BAO under weight-two condition, we first convert the problem to a T-join problem, and then solve the latter in polynomial time.

Definition 2.1. Let G=(V,E)G=(V,E) be a graph. For Q⊆EQ\subseteq E, let ∂GQ\partial_G Q be the set of vertices of odd degree in the subgraph (V,Q)(V,Q). A loop contributes two to the degree. For T⊆VT\subseteq V, a set Q⊆EQ\subseteq E is a TT-join if ∂G(Q)=T\partial_G(Q)=T.

Since a loop contributes 22 to the degree, including it or not does not affect ∂G(Q)\partial_G(Q). Hence, we may select all negative-weight loops, delete all loops from the graph, and work with the resulting graph instead. Therefore, when considering TT-joins, we may assume without loss of generality that GG is loopless. It is easy to see that a TT-join exists if and only if every connected component of GG contains an even number of vertices of TT. Necessity follows from a simple counting argument. For sufficiency, pair the vertices of TT arbitrarily within each component, choose a path for each pair, and take the symmetric difference of the edge sets of these paths.

The TT-join problem can be solved in polynomial time. Moreover, if GG is planar, the running time can be further decreased. The algorithm for planar graphs will be used later.

Lemma 2.2. Let G=(V,E)G=(V,E) be a loopless graph with weight function f:E→Rf:E\to\mathbb{R}, let Vt⊆VV_t\subseteq V, and write n=∣V∣n=|V|, m=∣E∣m=|E|. Then there is an O(max⁡{m,n}3)O(\max\{m,n\}^{3})-time algorithm that either finds a minimum-weight edge subset E′⊆EE'\subseteq E satisfying ∂G(E′)=Vt\partial_G(E')=V_t, or reports that none exists. If GG is planar, the running time improves to O(max⁡{m,n}3/2log⁡max⁡{m,n})O(\max\{m,n\}^{3/2}\log\max\{m,n\}).

The proof of Lemma Lemma 2.2 is delayed to Appendix § 8. Next we will present the proof of Theorem 1.2 which shows how to convert Problem 1.1 to a TT-join problem and then solve it under the weight-two condition.

Proof of Theorem 1.2. Because zero columns do not contribute to the affine system, we can simply pick the value of xx on those coordinates to be 00 if the corresponding weight is positive, and 11 otherwise. From now on we assume that AA has no zero columns. Construct a graph GAG_A with vertex set [r]∪{⋆}[r]\cup\{\star\}, where ⋆\star is a new vertex. A column with support {u,v}\{u,v\} becomes an edge uvuv, and a column with support {u}\{u\} becomes an edge u⋆u\star. The edge inherits the weight of the corresponding column.

Set

Tb=supp⁡(b)△{{⋆},if wt⁡(b) is odd,∅,if wt⁡(b) is even.(8)T_b=\operatorname{supp}(b)\mathbin{\triangle} \begin{cases} \{\star\}, & \text{if }\operatorname{wt}(b)\text{ is odd},\\ \varnothing, & \text{if }\operatorname{wt}(b)\text{ is even}. \end{cases} \tag*{(8)}

For x∈F2mx\in\mathbb{F}_2^m, let ExE_x be the corresponding set of graph edges. Then we have ∀x\forall x, Ax=(∂GAEx)[r]Ax=(\partial_{G_A}E_x)[r]. Hence

Ax=b⟺∂GAEx=Tb.Ax=b\quad\Longleftrightarrow\quad\partial_{G_A}E_x=T_b.

By Lemma Lemma 2.2, we can solve the above problem and recover an optimal vector xx in polynomial time. □

Remark 2.3. What we do in the proof is equivalent to attaching a row to AA that is the sum of all rows in AA. If we denote the matrix obtained by A′A', then every column of A′A' has Hamming weight two. Moreover, A′A' is exactly the incidence matrix of the graph GAG_A.

FPT algorithm with nearly-graphic parameters

We first need a lemma that solves the subproblem of specific coordinates.

Lemma 3.1 (subproblem of specific coordinates). Let C∈F2r×mC \in\mathbb{F}_2^{r \times m}, J⊆[m]J \subseteq[m], Δ∈Rm\Delta\in\mathbb{R}^m. Put k=∣J∣k = |J| and ρ=rank⁡(CJ)\rho= \operatorname{rank}(C_J). For every s∈Im⁡(CJ)s \in\operatorname{Im}(C_J), define

DJ(s)=min⁡{ΔJTα:CJα=s, α∈F2J}.(9)D_J(s) = \min\{\Delta_J^{\mathsf{T}}\alpha: C_J\alpha= s,\ \alpha\in\mathbb{F}_2^J\}. \tag*{(9)}

Let N=max⁡{r,m}N = \max\{r,m\}. Then all values DJ(s)D_J(s) for s∈Im⁡(CJ)s \in\operatorname{Im}(C_J), together with all minimizers α\alpha, can be computed in time O(2ρNO(1))O(2^\rho N^{O(1)}).

Proof of Lemma 3.1. Order JJ as j1,…,jkj_1,\ldots,j_k. Choose a linear isomorphism f:Im⁡(CJ)↦F2ρf:\operatorname{Im}(C_J)\mapsto\mathbb{F}_2^\rho, which can be computed by the Gaussian elimination, and let zi=f(Cji)z_i=f(C_{j_i}). For i∈{0,…,k}i\in\{0,\ldots,k\} and t∈F2ρt\in\mathbb{F}_2^\rho, let

Di(t)=min⁡{ΔJTα:CJα=f−1(t),supp⁡(α)⊆{j1,…,ji}}.D_i(t)=\min\{\Delta_J^{\mathsf{T}}\alpha:C_J\alpha=f^{-1}(t),\operatorname{supp}(\alpha)\subseteq\{j_1,\ldots,j_i\}\}.

Then D0(0)=0D_0(0)=0 and D0(t)=+∞D_0(t)=+\infty for t≠0t\ne0. Splitting a subset according to whether it contains jij_i gives

Di(t)=min⁡{Di−1(t),Di−1(t+zi)+Δji}.(10)D_i(t)=\min\{D_{i-1}(t),D_{i-1}(t+z_i)+\Delta_{j_i}\}. \tag*{(10)}

We have ∀t∈F2ρ\forall t\in\mathbb{F}_2^\rho, Dk(t)=DJ(f−1(t))D_k(t)=D_J(f^{-1}(t)). Then one can compute all values of DJ(f−1(t))D_J(f^{-1}(t)), and hence DJ(s)D_J(s) in time O(2ρNO(1))O(2^\rho N^{O(1)}). Moreover, we can keep track of the optimal assignments achieving Di(t)D_i(t) during the computation. Therefore those α\alpha achieving DJ(s)D_J(s) can be simultaneously obtained in the end of the induction.

Proof of Theorem 1.6. First apply the Gaussian Elimination to the system Ax=bAx=b. If it detects an inconsistent system, report inconsistency and stop. Then we can verify in polynomial time that UU is invertible and that every column of UAUA outside JJ has weight at most two. Afterwards, set C=UAC=UA and g=Ubg=Ub, so that Cx=gCx=g is equivalent to Ax=bAx=b. Now we give two different algorithms that achieve the two time complexities respectively.

  1. For time complexity O(2ρNO(1))O(2^\rho N^{O(1)}), we use the following algorithm to solve the problem. Use Lemma 3.1 to compute all DJ(s)D_J(s), together with those xJx_J achieving the optimum. The time cost of this procedure is O(2ρNO(1))O(2^\rho N^{O(1)}). If CJxJ=sC_Jx_J=s, then the remaining coordinates must satisfy

CJ‾xJ‾=g+s.(11)C_{\overline{J}}x_{\overline{J}}=g+s. \tag*{(11)}

We note that addition and subtraction are equivalent in F2\mathbb{F}_2, therefore g+s=g−sg+s=g-s. Moreover, CJ‾C_{\overline{J}} has column weight at most two, so we can apply Theorem 1.2 to either detect infeasibility or obtain an xJ‾x_{\overline{J}} such that ΔJ‾TxJ‾\Delta_{\overline{J}}^{\mathsf{T}}x_{\overline{J}} achieves minimum. Denote this minimum by Q(s)Q(s), and take Q(s)=+∞Q(s)=+\infty when the system is infeasible. Then it is easy to see that the optimum value for the original BAO problem is

min⁡s∈Im⁡(CJ)(DJ(s)+Q(s)).(12)\min_{s\in\operatorname{Im}(C_J)}\left(D_J(s)+Q(s)\right). \tag*{(12)}

If Q(s)=+∞Q(s)=+\infty for every s∈Im⁡(CJ)s\in\operatorname{Im}(C_J), report that the affine system is infeasible. Otherwise, choose an ss attaining a finite minimum in (12). We already have xJx_J after applying the algorithm in Lemma 3.1. xJ‾x_{\overline{J}} can be recovered when applying Theorem 1.2. Concatenate xJx_J and xJ‾x_{\overline{J}} to obtain an optimal xx.

  1. For time complexity O(2kNO(1))O(2^kN^{O(1)}), we use the following algorithm. For every xJx_J, use Theorem 1.2 to compute

Q(xJ)=min⁡{ΔJ‾TxJ‾:CJ‾xJ‾=g+CJxJ}.Q(x_J)=\min\{\Delta_{\overline{J}}^{\mathsf{T}}x_{\overline{J}}:C_{\overline{J}}x_{\overline{J}}=g+C_Jx_J\}.

Then the optimal value is equal to

min⁡xJ{ΔJTxJ+Q(xJ)}\min_{x_J}\{\Delta_J^{\mathsf{T}}x_J+Q(x_J)\}

and the total time complexity is O(2kNO(1))O(2^kN^{O(1)}).

We would like to point out that Theorem 1.6 is certificate-based. It verifies a supplied certificate and optimizes from it, but it does not find a certificate attaining rex⁡2(A)\operatorname{rex}_2(A).

Max-Lin2 on graphs and Eulerian-spanning set

Before we proceed, we make the following conventions. Suppose SS is a finite multiset and F\mathbb{F} is a field. Then FS\mathbb{F}^{S} is the linear space over F\mathbb{F} with dimension ∣S∣\lvert S\rvert. FS\mathbb{F}^{S} is regarded to be indexed by the multiset SS. Moreover, if F=F2\mathbb{F}=\mathbb{F}_2, then every element in F2S\mathbb{F}_2^{S} is regarded as an indicator function of some subset of SS. Suppose S1,S2S_1,S_2 are two subsets of the same multiset SS. Then S1△S2S_1\mathbin{\triangle}S_2 is the symmetric difference between S1,S2S_1,S_2. Moreover, the symmetric bilinear form ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle on F2S\mathbb{F}_2^{S} is defined as ⟨x,y⟩=∑s∈Sx(s)y(s)\langle x,y\rangle=\sum_{s\in S}x(s)y(s), ∀x,y∈F2S\forall x,y\in\mathbb{F}_2^{S}. It is obvious that ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle is non-degenerative.

Problem 4.1 (weighted Boolean Max-Lin2 on graphs). Suppose G=(V,E)G=(V,E) is a graph in which each edge e∈Ee\in E has weight we∈Rw_e\in\mathbb{R}. In addition, a violation variable ce∈F2c_e\in\mathbb{F}_2 is associated with each edge e∈Ee\in E. For x∈F2Vx\in\mathbb{F}_2^{V}, the violation vector z(x)∈F2Ez(x)\in\mathbb{F}_2^{E} is defined by

∀e∈E, e=(u,v), z(x)e=xu+xv+ce.\forall e\in E,\ e=(u,v),\ z(x)_e=x_u+x_v+c_e.

Our goal is to solve the following optimization problem, and compute an optimal assignment:

min⁡{wTz(x):x∈F2V}.\min\{w^{\mathsf T}z(x):x\in\mathbb{F}_2^{V}\}.

Remark 4.2. A loop corresponds to a fixed bit cec_e. By adding the constant wecew_ec_e to the objective and deleting the loop equations, we may assume that G=(V,E)G=(V,E) is loopless. Moreover, one can merge multiple edges, and modify the weights and violation variables accordingly to obtain an equivalent problem (up to an additive constant in the objective). Therefore we may assume that G=(V,E)G=(V,E) is simple. The loopless assumption is used in Appendix § 9, in the proof of Theorem 5.10. The simple assumption is used in Appendix § 9, in application to the case of crossing numbers.

The violation vector zz admits a more concise expression in terms of the incidence matrix of a graph. Given a graph G=(V,E)G=(V,E), its incidence matrix MG∈F2V×EM_G\in\mathbb{F}_2^{V\times E} is defined as follows: its rows are indexed by VV, and its columns are indexed by EE; moreover, for all v∈Vv\in V and e∈Ee\in E, MG(v,e)=1M_G(v,e)=1 if and only if ee is not a loop and vv is an endpoint of ee.

Problem 4.3 (weighted Boolean Max-Lin2 on graphs). Suppose G=(V,E)G=(V,E) is a graph, w∈REw\in\mathbb{R}^{E} is a weight vector, and c∈F2Ec\in\mathbb{F}_2^{E} is a given violation vector. For x∈F2Vx\in\mathbb{F}_2^{V}, the violation vector z(x)∈F2Ez(x)\in\mathbb{F}_2^{E} is defined as

z(x)=MGTx+c.z(x)=M_G^{\mathsf T}x+c.

Our goal is to solve the optimization problem: min⁡{wTz(x):x∈F2V}\min\{w^{\mathsf T}z(x):x\in\mathbb{F}_2^{V}\}.

It is easy to see that Problem 4.1 is equivalent to Problem 4.3. We will use the latter form from now on. Next we give the definition of Eulerian-spanning sets, and convert Max-Lin2 to BAO.

Definition 4.4. *Suppose G=(V,E)G=(V,E) is a graph and MGM_G is its incidence matrix. Define the cycle space Z(G)\mathcal{Z}(G) of GG to be Z(G)=ker⁡MG\mathcal{Z}(G)=\ker M_G. A Eulerian-spanning set of GG is a multiset B=(B1,…,Br)\mathcal{B}=(B_1,\ldots,B_r) consisting of elements in Z(G)\mathcal{Z}(G), such that the span of elements

in BB is Z(G)Z(G). If elements in BB are linearly independent, then BB is called a Eulerian basis of GG. Its edge frequency for a certain e∈Ee \in E is fB(e)=∣{i:e∈Bi}∣f_B(e) = |\{i : e \in B_i\}|. Let AB∈F2B×EA_B \in\mathbb{F}_2^{B \times E} be the matrix whose iith row is the incidence vector of BiB_i. Define the following exceptional parameters:

JB={e∈E:fB(e)≥3},ρB=rank⁡((AB)JB),(13)J_B = \{e \in E : f_B(e) \ge3\}, \qquad\rho_B = \operatorname{rank}((A_B)_{J_B}), \tag*{(13)}

and ρB\rho_B will be called the exceptional rank of BB.

Remark 4.5. Every Eulerian subgraph of GG is an edge-disjoint union of cycles: a nonempty Eulerian component contains a cycle, and deleting the edges of that cycle preserves even degree, so induction applies. Therefore, given any Eulerian basis BB, we can split every element into cycles, and then select a basis from the whole set of cycles. It is easy to see the above procedure does not increase any edge frequency.

Using the Eulerian-spanning set of GG and (7) yields

min⁡{wTz(x):x∈F2V}=min⁡{wTz:ABz=ABc, z∈F2E}.(14)\min\{w^{\mathsf T}z(x) : x \in\mathbb{F}_2^V\} = \min\{w^{\mathsf T}z : A_Bz = A_Bc,\, z \in\mathbb{F}_2^E\}. \tag*{(14)}

If we have the solution to the latter, then we are able to recover the solution to the former in polynomial time. In particular, the maxcut and signed frustration problems are special cases of Max-Lin2_2 on graphs.

Problem 4.6 (maxcut). Let G=(V,E)G = (V, E) be a graph with edge-weight vector w∈REw \in\mathbb{R}^E, and W=∑e∈EweW = \sum_{e \in E} w_e. Define MaxCut⁡w(G)=max⁡x∈F2V∑e=(u,v)∈Ewe1{xu≠xv}\operatorname{MaxCut}_w(G) = \max_{x \in\mathbb{F}_2^V} \sum_{e=(u,v) \in E} w_e \mathbf{1}_{\{x_u \ne x_v\}}. Then

MaxCut⁡w(G)=W−min⁡{wT(MGTx+1):x∈F2V}.\operatorname{MaxCut}_w(G) = W - \min\{w^{\mathsf T}(M_G^{\mathsf T}x + 1) : x \in\mathbb{F}_2^V\}.

That is, the maxcut problem corresponds to the case of c=1c = 1 in Problem 4.3, and applying (14) then yields the following equivalent form.

Corollary 4.7. Let G=(V,E)G = (V, E) be a graph with edge-weight vector w∈REw \in\mathbb{R}^E, W=∑e∈EweW = \sum_{e \in E} w_e, and let BB be a Eulerian-spanning set of GG. Then

MaxCut⁡w(G)=W−min⁡{wTz:ABz=AB1, z∈F2E}.(15)\operatorname{MaxCut}_w(G) = W - \min\{w^{\mathsf T}z : A_Bz = A_B1,\, z \in\mathbb{F}_2^E\}. \tag*{(15)}

The signed frustration problem involves the concept of a signed graph. A signed graph is a graph with each edge marked with a sign, positive or negative. For a signed graph, encode a positive edge by ce=0c_e = 0 and a negative edge by ce=1c_e = 1. A signed graph is balanced exactly when every cycle contains an even number of negative edges [11].

Problem 4.8 (signed frustration). Let G=(V,E)G = (V, E) be a signed graph with sign vector c∈F2Ec \in\mathbb{F}_2^E (obtained in the way described above) and edge-weight vector w∈REw \in\mathbb{R}^E, and let BB be a Eulerian basis of GG. Then the minimum total weight of violated edges in any vertex assignment is

min⁡{wT(MGTx+c):x∈F2V}=min⁡{wTz:ABz=ABc, z∈F2E}.\min\{w^{\mathsf T}(M_G^{\mathsf T}x + c) : x \in\mathbb{F}_2^V\} = \min\{w^{\mathsf T}z : A_Bz = A_Bc,\, z \in\mathbb{F}_2^E\}.

Remark 4.9. In an instance of signed frustration problem, if we pick an edge e∈Ee \in E, change cec_e to 1−ce1-c_e, and wew_e to −we-w_e, then we only change the optimal value by a known constant, and leave the optimal assignments unchanged. That is, each instance of maxcut is equivalent (up to an additive constant) to an instance of signed frustration, and vice versa. Moreover, the conversion in both directions can be done in time O(max⁡{∣V∣,∣E∣})O(\max\{|V|, |E|\}).

Contraction distance and contraction rank

Suppose G=(V,E)G=(V,E) is a graph and B\mathcal{B} is a Eulerian-spanning set of GG. In this section we will show that exc⁡2(AB)\operatorname{exc}_{2}(A_{\mathcal{B}}), rex⁡2(AB)\operatorname{rex}_{2}(A_{\mathcal{B}}) are independent from the choice of B\mathcal{B}, and are equal to the contraction distance and contraction rank of GG, respectively. § 5.1 proves the independence and gives the definition of contraction distance and contraction rank. § 5.2 characterizes the correspondence between cycle space of a graph and its contracted graph. § 5.3 proves the equality between exc⁡2(AB)\operatorname{exc}_{2}(A_{\mathcal{B}}), rex⁡2(AB)\operatorname{rex}_{2}(A_{\mathcal{B}}) and the contraction distance and contraction rank of GG, and gives FPT algorithms.

Independence

We first present the definition of edge contraction and deletion for graphs. They are standard and are presented only for completeness.

Definition 5.1 (edge contraction and deletion). Suppose G=(V,E)G=(V,E) is a graph. For an edge set P⊆E(G)P\subseteq E(G), define G/PG/P by identifying all vertices in each connected component of (V,P)(V,P) and deleting the edges of PP. Define G−PG-P to be G−P=(V,E∖P)G-P=(V,E\setminus P).

It is easy to see that G/PG/P is the graph obtained by contracting the edges of PP sequentially.

If (Vt,Et)(V_t,E_t) is a connected component of GG, then the projection of Im⁡MG\operatorname{Im} M_G to VtV_t is exactly the space of vectors with even Hamming weight. Thus rank⁡(MG)=∣V∣−c(G)\operatorname{rank}(M_G)=|V|-c(G) with c(G)c(G) being the number of connected components of GG. And by the rank-nullity theorem, we have

dim⁡Z(G)=∣E∣−∣V∣+c(G).(16)\dim\mathcal{Z}(G)=|E|-|V|+c(G). \tag*{(16)}

We need a lemma that computes the rank of (AB)P(A_{\mathcal{B}})_P for any edge set PP.

Lemma 5.2. Suppose G=(V,E)G=(V,E) is a graph and B\mathcal{B} is a Eulerian basis of GG. For every P⊆EP\subseteq E,

rank⁡((AB)P)=dim⁡Z(G)−dim⁡Z(G−P)=∣P∣−c(G−P)+c(G).(17)\operatorname{rank}((A_{\mathcal{B}})_P)=\dim\mathcal{Z}(G)-\dim\mathcal{Z}(G-P)=|P|-c(G-P)+c(G). \tag*{(17)}

In particular, this value is independent of B\mathcal{B}.

Proof. Restricting a Eulerian edge set to the coordinates in PP defines a linear map

Z(G)⟶F2P.\mathcal{Z}(G)\longrightarrow\mathbb{F}_2^P.

Its image is the row space of (AB)P(A_{\mathcal{B}})_P, and its kernel consists exactly of the Eulerian edge sets supported in E∖PE\setminus P, namely Z(G−P)\mathcal{Z}(G-P). Using the rank-nullity theorem and (16) gives rank⁡((AB)P)=(∣E∣−∣V∣+c(G))−(∣E∣−∣P∣−∣V∣+c(G−P))=∣P∣−c(G−P)+c(G)\operatorname{rank}((A_{\mathcal{B}})_P)=(|E|-|V|+c(G))-(|E|-|P|-|V|+c(G-P))=|P|-c(G-P)+c(G). □

Let EG\mathcal{E}_G collect all Eulerian-spanning sets of GG and E~G\widetilde{\mathcal{E}}_G collect all Eulerian bases of GG. We are going to prove that the nearly-graphic parameters of ABA_{\mathcal{B}} are independent of the choice of B\mathcal{B}.

Theorem 5.3. Suppose G=(V,E)G=(V,E) is a graph and B\mathcal{B} is a Eulerian-spanning set of GG. Then

exc⁡2(AB)=min⁡B′∈EG∣JB′∣=min⁡B′∈E~G∣JB′∣,\operatorname{exc}_{2}(A_{\mathcal{B}})=\min_{\mathcal{B}'\in\mathcal{E}_G}|J_{\mathcal{B}'}|=\min_{\mathcal{B}'\in\widetilde{\mathcal{E}}_G}|J_{\mathcal{B}'}|,
rex⁡2(AB)=min⁡B′∈EGρB′=min⁡B′∈E~GρB′.\operatorname{rex}_{2}(A_{\mathcal{B}})=\min_{\mathcal{B}'\in\mathcal{E}_G}\rho_{\mathcal{B}'}=\min_{\mathcal{B}'\in\widetilde{\mathcal{E}}_G}\rho_{\mathcal{B}'}.

Proof. Suppose AB∈F2r×EA_B \in\mathbb{F}_2^{r \times E}. For any U∈GL⁡(r,2)U \in\operatorname{GL}(r,2), UABUA_B is the incidence matrix of another Eulerian-spanning set. We have

exc⁡2(AB)≥min⁡B′∈EG∣JB′∣,rex⁡2(AB)≥min⁡B′∈EGρB′.\operatorname{exc}_2(A_B) \ge\min_{B' \in\mathcal{E}_G} |J_{B'}|,\qquad\operatorname{rex}_2(A_B) \ge\min_{B' \in\mathcal{E}_G} \rho_{B'}.

For any Eulerian-spanning set B′B', there is a Eulerian basis B′′⊆B′B'' \subseteq B', and ∣JB′∣≥∣JB′′∣|J_{B'}| \ge|J_{B''}|, ρB′≥ρB′′\rho_{B'} \ge\rho_{B''}. Thus

min⁡B′∈EG∣JB′∣≥min⁡B′∈E~G∣JB′∣,min⁡B′∈EGρB′≥min⁡B′∈E~GρB′.\min_{B' \in\mathcal{E}_G} |J_{B'}| \ge\min_{B' \in\widetilde{\mathcal{E}}_G} |J_{B'}|,\qquad\min_{B' \in\mathcal{E}_G} \rho_{B'} \ge\min_{B' \in\widetilde{\mathcal{E}}_G} \rho_{B'}.

For any Eulerian basis B′B', there exists a U∈GL⁡(r,2)U \in\operatorname{GL}(r,2), such that UAB=(AB′0)UA_B = \begin{pmatrix} A_{B'} \\ 0 \end{pmatrix}, implying

min⁡B′∈E~G∣JB′∣≥exc⁡2(AB),min⁡B′∈E~GρB′≥rex⁡2(AB).\min_{B' \in\widetilde{\mathcal{E}}_G} |J_{B'}| \ge\operatorname{exc}_2(A_B),\qquad\min_{B' \in\widetilde{\mathcal{E}}_G} \rho_{B'} \ge\operatorname{rex}_2(A_B).

Hence equality holds all along.

For a graph G=(V,E)G=(V,E), we set

cex⁡(G)=min⁡B∈E~G∣JB∣,(18)\operatorname{cex}(G)=\min_{B\in\widetilde{\mathcal{E}}_G}|J_B|, \tag*{(18)}
rcex⁡(G)=min⁡B∈E~GρB,(19)\operatorname{rcex}(G)=\min_{B\in\widetilde{\mathcal{E}}_G}\rho_B, \tag*{(19)}
ρG(P)=∣P∣−c(G−P)+c(G), for P⊆E,(20)\rho_G(P)=|P|-c(G-P)+c(G),\ \text{for }P\subseteq E, \tag*{(20)}
ctr⁡(G)=min⁡{∣P∣:P⊆E, G/P is planar},(21)\operatorname{ctr}(G)=\min\{|P|:P\subseteq E,\ G/P\text{ is planar}\}, \tag*{(21)}
rctr⁡(G)=min⁡{ρG(P):P⊆E, G/P is planar}.(22)\operatorname{rctr}(G)=\min\{\rho_G(P):P\subseteq E,\ G/P\text{ is planar}\}. \tag*{(22)}

The last three quantities are called the cographic rank of PP, the contraction distance of GG, and the contraction rank of GG, respectively. The inequalities rcex⁡(G)≤cex⁡(G)\operatorname{rcex}(G)\le\operatorname{cex}(G) and rctr⁡(G)≤ctr⁡(G)\operatorname{rctr}(G)\le\operatorname{ctr}(G) are immediate. We note that rctr⁡(G)=0\operatorname{rctr}(G)=0 if and only if GG is planar. To see the nontrivial direction, let P⊆EP\subseteq E satisfy G/PG/P is planar and ρG(P)=0\rho_G(P)=0. The proof of Lemma 5.2 yields that the restriction of every vector in Z(G)\mathcal{Z}(G) to PP is zero. Hence no edge of PP lies on a cycle, so every edge of PP is a bridge. Construct an auxiliary graph GaG_a, with vertices corresponding to connected components of G−PG-P, and edges corresponding to bridges connecting two components. Then the auxiliary graph must be a forest, because a cycle in this auxiliary graph would place every edge of that cycle on a cycle of GG, contradicting the fact that ρG(P)=0\rho_G(P)=0. Each component of G−PG-P is planar because it is isomorphic to a subgraph of the planar graph G/PG/P. Pick any root of GaG_a. Then we can start with planar embeddings of these components and follow the auxiliary tree from its root. We draw each bridge to be both in a face of the father and in the outer face of the child. This constructs a planar embedding of GG.

Cycle spaces under contraction

Definition 5.4 (coordinate projection). Suppose G=(V,E)G=(V,E) is a graph. Let πP:F2E→F2E∖P\pi_P:\mathbb{F}_2^E\to\mathbb{F}_2^{E\setminus P} be the natural coordinate projection. The target coordinates are naturally identified with the edges of G/PG/P.

Lemma 5.5 (forest contraction witnesses). Suppose G=(V,E)G=(V,E) is a graph. Let P⊆EP\subseteq E, and let TT be a spanning forest of (V,P)(V,P). If G/PG/P is planar, then G/TG/T is planar and ∣T∣≤∣P∣|T|\le|P|. Consequently, a minimum-cardinality contraction edge set may be chosen to be a forest.

Proof. Every edge of P∖TP \setminus T becomes a loop in G/TG/T, and deleting these loops from G/TG/T gives G/PG/P. Since adding loops preserves planarity, G/TG/T is planar whenever G/PG/P is planar. The inequality ∣T∣≤∣P∣|T| \le|P| is obvious.

Lemma 5.6 (contraction projection). Let G=(V,E)G=(V,E) be a graph. We have, (1) for every P⊆EP \subseteq E, the map πP:Z(G)⟶Z(G/P)\pi_P:\mathcal{Z}(G) \longrightarrow\mathcal{Z}(G/P) is surjective; (2) if T⊆ET \subseteq E is a forest, then πT:Z(G)⟶Z(G/T)\pi_T:\mathcal{Z}(G) \longrightarrow\mathcal{Z}(G/T) is an isomorphism.

Proof. The projection maps Eulerian edge sets to Eulerian edge sets, because the degree parity at a contracted vertex is the sum of the degree parities at the vertices that were identified, with every internal edge contributing twice.

Suppose first that TT is a forest. The kernel of πT\pi_T consists of Eulerian edge sets supported in TT. But a forest contains no nonempty Eulerian edge set, so the kernel is zero. Contracting TT decreases both the number of edges and the number of vertices by ∣T∣|T| and leaves the number of connected components unchanged. Thus Z(G)\mathcal{Z}(G) and Z(G/T)\mathcal{Z}(G/T) have the same dimension, and πT\pi_T is an isomorphism.

For arbitrary PP, choose a spanning forest TT of (V,P)(V,P). In G/TG/T, the edges of P∖TP \setminus T are loops, and deleting these loops gives G/PG/P. Given z∈Z(G/P)z \in\mathcal{Z}(G/P), extend it to z′∈Z(G/T)z' \in\mathcal{Z}(G/T) by assigning value zero to every loop in P∖TP \setminus T. By the forest case proven above (part 2 of this theorem), there exists a unique y∈Z(G)y \in\mathcal{Z}(G) such that πT(y)=z′\pi_T(y)=z'. Therefore πP(y)=z\pi_P(y)=z and πP\pi_P is surjective.

Cardinality and rank correspondences

Before we prove the parameter correspondences, we need a Mac Lane’s law of planarity on general graphs. Suppose G=(V,E)G=(V,E) is a graph, define the basis number of GG to be

b(G)=min⁡B∈E~Gmax⁡e∈E(G)fB(e).b(G)=\min_{\mathcal{B}\in\widetilde{\mathcal{E}}_G}\max_{e\in E(G)} f_{\mathcal{B}}(e).

We use the convention that the maximum over an empty edge set is zero. By the cycle-decomposition observation described in Remark 4.5, this definition agrees with the usual definition in terms of cycle bases. The original Mac Lane’s criterion states that a simple graph GG is planar if and only if b(G)≤2b(G) \le2. We need and prove the following form.

Theorem 5.7 (Mac Lane’s criterion for graphs). A graph G=(V,E)G=(V,E) is planar if and only if b(G)≤2b(G) \le2, or equivalently, it has a Eulerian basis B\mathcal{B} satisfying fB(e)≤2f_{\mathcal{B}}(e) \le2 for every edge ee.

Proof. First suppose that GG is planar. Fix an arbitrary planar embedding of GG. For a face FF of the embedding, define its boundary vector ∂2F∈F2E\partial_2F \in\mathbb{F}_2^E by declaring that (∂2F)e(\partial_2F)_e is the number of occurrences of ee in the boundary walk of FF, reduced modulo two. Then a bridge, which is traversed twice by the same facial boundary walk, has coordinate zero. For each connected component KK of GG, view the induced drawing of KK as a plane embedding in its own right and let F(K)\mathcal{F}(K) be its face set. Then every cycle CC in KK corresponds to a Jordan cycle in the plane, and therefore encloses a space. It is easy to see that the sum of all boundaries of faces in CC is CC itself. Therefore the boundary vectors do span Z(K)\mathcal{Z}(K). Omitting one such vector gives a basis, because the only way some of these vectors can sum to zero is that the geometric boundary of the sum of the corresponding faces is empty, meaning that they can only be the whole set of boundary vectors. Taking the union over all components yields a basis of Z(G)\mathcal{Z}(G). Since every edge is incident to at most two faces, it occurs in at most two chosen vectors.

Conversely, suppose that GG has a Eulerian basis B\mathcal{B} in which every edge has frequency at most two, and let L0L_0 be the set of loops in GG. Then the natural coordinate projection onto E(G)∖L0E(G)\setminus L_0 maps Z(G)\mathcal{Z}(G) surjectively onto Z(G−L0)\mathcal{Z}(G-L_0). Project B\mathcal{B}, delete the zero vectors, and select a basis from the remaining vectors to form a new set B′\mathcal{B}'. Then each edge can appear in at most two elements in B′\mathcal{B}'. If a selected basis element is disconnected, split it into edge-disjoint cycle and select a basis from the resulting generating family to form a set B′′\mathcal{B}''. Again, each edge can appear in at most two elements in B′′\mathcal{B}''.

Now we subdivide every edge of the resulting loopless graph once. Then the resulting graph is simple, and subdivision induces a natural linear cycle-space isomorphism that preserves the number of appearances of each original edge in a Eulerian basis. Now Mac Lane’s law gives that the subdivided graph is planar. Suppressing the subdivision vertices and restoring the loops, and we conclude that the original graph is planar.

Theorem 5.8. For every graph G=(V,E)G=(V,E),

cex⁡(G)=ctr⁡(G),rcex⁡(G)=rctr⁡(G).(23)\operatorname{cex}(G)=\operatorname{ctr}(G), \qquad\operatorname{rcex}(G)=\operatorname{rctr}(G). \tag*{(23)}

Moreover, given P⊆EP\subseteq E such that G/PG/P is planar and a planar embedding of G/PG/P, one can construct in polynomial time a Eulerian basis B\mathcal{B} of GG satisfying

JB⊆P,ρB≤ρG(P).(24)J_{\mathcal{B}}\subseteq P, \qquad\rho_{\mathcal{B}}\leq\rho_G(P). \tag*{(24)}

Proof. We first prove

ctr⁡(G)≤cex⁡(G),rctr⁡(G)≤rcex⁡(G).(25)\operatorname{ctr}(G)\leq\operatorname{cex}(G), \qquad\operatorname{rctr}(G)\leq\operatorname{rcex}(G). \tag*{(25)}

Let B\mathcal{B} be a Eulerian basis and put P=JBP=J_{\mathcal{B}}. By Lemma 5.6(1), the vectors πP(B)\pi_P(B), with B∈BB\in\mathcal{B}, span Z(G/P)\mathcal{Z}(G/P). Delete zero vectors and select a basis from the remaining vectors to form a basis B′\mathcal{B}'. Every edge of G/PG/P corresponds to an edge outside PP and therefore occurs in at most two vectors in B′\mathcal{B}'. Theorem 5.7 implies that G/PG/P is planar. By Lemma 5.2,

ctr⁡(G)≤∣JB∣,rctr⁡(G)≤ρG(JB)=rank⁡((AB)JB)=ρB,\operatorname{ctr}(G)\leq|J_{\mathcal{B}}|,\qquad\operatorname{rctr}(G)\leq\rho_G(J_{\mathcal{B}})=\operatorname{rank}((A_{\mathcal{B}})_{J_{\mathcal{B}}})=\rho_{\mathcal{B}},

Minimizing the above inequalities over B\mathcal{B} gives (25).

Next we prove

cex⁡(G)≤ctr⁡(G),rcex⁡(G)≤rctr⁡(G).(26)\operatorname{cex}(G)\leq\operatorname{ctr}(G), \qquad\operatorname{rcex}(G)\leq\operatorname{rctr}(G). \tag*{(26)}

Let P⊆E(G)P\subseteq E(G) be such that G/PG/P is planar, and let TT be a spanning forest of (V,P)(V,P). Lemma 5.5 gives that G/TG/T is planar. By Theorem 5.7, choose a Eulerian basis B′\mathcal{B}' of G/TG/T in which every edge has frequency at most two. Since TT is a forest, Lemma 5.6(2) gives a unique lift B=πT−1(B′)\mathcal{B}=\pi_T^{-1}(\mathcal{B}') of every B′∈B′B'\in\mathcal{B}'. These lifts form a Eulerian basis B\mathcal{B} of GG. For each edge e∉Te\notin T, the coordinate is unchanged by the lift, so fB(e)=fB′(e)≤2f_{\mathcal{B}}(e)=f_{\mathcal{B}'}(e)\leq2. Thus

JB⊆T⊆P.J_{\mathcal{B}}\subseteq T\subseteq P.

It follows that

∣JB∣≤∣P∣,ρB=rank⁡((AB)JB)≤rank⁡((AB)P)=ρG(P).|J_{\mathcal{B}}|\leq|P|,\qquad\rho_{\mathcal{B}}=\operatorname{rank}((A_{\mathcal{B}})_{J_{\mathcal{B}}})\leq\operatorname{rank}((A_{\mathcal{B}})_P)=\rho_G(P).

Minimizing the first inequality over cardinality-minimal PP and the second over rank-minimal PP leads to (26). Combining (25) and (26) together proves (23).

For the constructive statement, start from the given embedding of G/PG/P. Let TT be a spanning forest of (V,P)(V,P). Lemma 5.5 gives that G/TG/T is planar. We can compute an embedding of G/TG/T by simply adding the loops corresponding to P∖TP \setminus T to G/PG/P. By Theorem 5.7, there is a Eulerian basis B′B' of G/TG/T such that for each edge ee, fB′(e)≤2f_{B'}(e) \le2. Therefore we only have to compute the lift πT−1(B′)\pi_T^{-1}(B').

The unique lift can be computed directly. Root every tree component of TT arbitrarily. For a fixed B′∈B′B' \in\mathcal{B}', define a vector x∈F2Ex \in\mathbb{F}_2^E by first setting xe=Be′x_e = B'_e for every e∉Te \notin T. For a vertex u∈Vu \in V, let dx(u)d_x(u) be the number of incidences at uu among the edges in (E∖T)∩B′(E \setminus T) \cap B', with a loop counted twice. For a nonroot vertex vv in TT, let eve_v be its parent edge and let TvT_v be the rooted subtree at vv. Let V(Tv)V(T_v) be the vertex set of TvT_v. Set

xev≡∑u∈V(Tv)dx(u)(mod2).(27)x_{e_v} \equiv\sum_{u \in V(T_v)} d_x(u) \pmod2. \tag*{(27)}

Let B=supp⁡(x)B = \operatorname{supp}(x). Now we show that BB is a Eulerian subgraph of GG. Indeed, for every nonroot vertex, the parity contributed by its parent edge is the same as that of the incidences with E∖TE \setminus T and the child edges, so its degree in supp⁡(x)\operatorname{supp}(x) is even. For a root rr with tree component KK, let V(K)V(K) be the vertex set of KK. Then the sum ∑u∈V(K)dx(u)\sum_{u \in V(K)} d_x(u) equals, modulo two, the degree of B′B' at the corresponding vertex of G/TG/T, which is even. So the root degree is also even. Thus B=πT−1(B′)B = \pi_T^{-1}(B') by Lemma 5.6(2). The construction is polynomial, and the inequalities above give (24). □

Corollary 5.9. Suppose G=(V,E),w,cG = (V,E), w,c is an instance of Problem 4.3. Moreover, we are given a P⊆EP \subseteq E such that G/PG/P is planar. Then there are two algorithms finding the optimal value and an optimal assignment in time

O(2ρG(P)max⁡{∣V∣,∣E∣}O(1))andO(2∣P∣max⁡{∣V∣,∣E∣}O(1))O\left(2^{\rho_G(P)}\max\{|V|,|E|\}^{O(1)}\right) \quad\text{and} \quad O\left(2^{|P|}\max\{|V|,|E|\}^{O(1)}\right)

respectively. The same conclusion holds for the maxcut and signed frustration problems.

Proof. By Remark 4.2, we assume that GG is loopless. A planar embedding of G/PG/P can be found in polynomial time by the planarity-testing algorithm in [12]. Construct the Eulerian basis BB by Theorem 5.8. Then (I,P)(I,P) is a nearly-graphic certificate for ABA_B. so Theorem 1.6 gives the stated running time. The special cases follow from Corollary 4.7 and Remark 4.9. □

Let n=∣V∣,m=∣E∣n = |V|, m = |E|. If we relax the exponent above 22 to ∣P∣|P|, we can actually apply a more delicate algorithm that takes time O(2∣P∣(max⁡{m,n}3/2log⁡(max⁡{m,n})+∣P∣max⁡{m,n}))O(2^{|P|}(\max\{m,n\}^{3/2}\log(\max\{m,n\}) + |P|\max\{m,n\}))).

Theorem 5.10. Suppose G=(V,E),w,cG = (V,E), w,c is an instance of Problem 4.3. Moreover, we are given P⊆E(G)P \subseteq E(G) such that G/PG/P is planar. Let n=∣V∣,m=∣E∣n = |V|, m = |E|. Then the optimal value and an optimal assignment can be found in time

O(2∣P∣(max⁡{m,n}3/2log⁡(max⁡{m,n})+∣P∣max⁡{m,n})).O(2^{|P|}(\max\{m,n\}^{3/2}\log(\max\{m,n\}) + |P|\max\{m,n\})).

The same conclusion holds for maxcut and signed frustration.

This result can be applied to the parameterization by crossing numbers. For the proof and the application, see Appendix § 9.

Proof of Theorem 1.8. Let N=max⁡{∣V∣,∣E∣}N = \max\{|V|, |E|\}. The Planar Contraction decision problem asks whether an input pair (G,k)(G, k) admits a set P⊆E(G)P \subseteq E(G) with ∣P∣≤k|P| \le k such that G/PG/P is planar. There is an f(k)Ncf(k)N^c-time algorithm for solving it [10, 1]. Put F(k)=max⁡0≤i≤kf(i)F(k) = \max_{0 \le i \le k} f(i). Run the decision algorithm for i=0,1,…i = 0, 1, \ldots until the first time that the algorithm accepts. This process terminates, because contracting a spanning forest of GG produces a planar graph consisting only of loops. If k=ctr⁡(G)k = \operatorname{ctr}(G) is the first value for which the algorithm accepts, the total running time of these calls is at most (k+1)F(k)Nc(k + 1)F(k)N^c.

Now we recover the set PP by self-reduction. Call (G,k)(G, k) a positive instance if there is a set P⊆E(G)P \subseteq E(G) with ∣P∣≤k|P| \le k such that G/PG/P is planar. If a nonplanar instance (G,k)(G, k) is positive, then there must be an edge ee such that the instance (G/e,k−1)(G/e, k - 1) is positive. Therefore we go through all edges, choose one ee such that the instance (G/e,k−1)(G/e, k - 1) is positive, contract it, and repeat the procedure until the graph is planar. This uses at most k∣E∣k|E| decision calls. The search therefore takes at most k∣E∣F(k)Nck|E|F(k)N^c time. For the returned set PP, one has ρG(P)≤∣P∣≤k\rho_G(P) \le|P| \le k. Applying Corollary 5.9 concludes the proof.

Conclusion and outlook

In this paper, we give an FPT algorithm solving BAO\mathrm{BAO} when a nearly-graphic certificate is given, which is parameterized by the support size and non-graphic rank. We explore the application of this algorithm to Max-Lin2\mathrm{Max\text{-}Lin}_2. When the constraints of Max-Lin2\mathrm{Max\text{-}Lin}_2 are defined by a graph, we use Eulerian-spanning set to describe the converted affine system, and prove that the nearly-graphic parameters of ABA_B, i.e. cex⁡(G)\operatorname{cex}(G), rcex⁡(G)\operatorname{rcex}(G) are equal to ctr⁡(G)\operatorname{ctr}(G), rctr⁡(G)\operatorname{rctr}(G), respectively. We therefore give FPT algorithms solving Max-Lin2\mathrm{Max\text{-}Lin}_2 on graphs. We specifically obtain an FPT algorithm solving Max-Lin2\mathrm{Max\text{-}Lin}_2 on graphs, which is parameterized by contraction distance and needs no information other than the problem itself. Moreover, we prove an arbitrarily large separation between ctr⁡(G)\operatorname{ctr}(G) and rctr⁡(G)\operatorname{rctr}(G).

Several problems are left open for the future. Finding a nearly-graphic certificate (U,J)(U, J) that has optimal, or nearly optimal parameters for the affine system Bx=dBx = d is an important one. Additionally, one may try to minimize the exponents above max⁡{∣V∣,∣E∣}\max\{|V|, |E|\} in algorithms present in § 4, which we do not give explicitly.

Acknowledgement

This research was supported by the National Natural Science Foundation of China (Nos. 12325112, 12288101).

Proof of Lemma 2.2

Now we are given a graph G=(V,E)G = (V,E) without loops, a vertex set Vt⊆VV_t \subseteq V. Our goal is to find the minimum weighted set E′⊆EE' \subseteq E such that ∂G(E′)=Vt\partial_G(E') = V_t, or claim that no such E′E' exists. If GG is not connected, we can solve the problem on each connected component of GG, respectively. Therefore, we assume that GG is connected from now on. Moreover, if 2∤∣Vt∣2 \nmid|V_t|, then by a simple counting argument there can be no such E′E'. Therefore, we assume that 2∣∣Vt∣2 \mid|V_t| from now on.

We first convert the problem to a maximum weighted Eulerian subgraph problem. Let Vo⊆VV_o \subseteq V be the set of vertices of odd degree in GG, and Vc=Vo△VtV_c = V_o \triangle V_t. Now we need to compute an edge set Ec⊆EE_c \subseteq E such that ∂G(Ec)=Vc\partial_G(E_c) = V_c. Specifically, we have the following lemma:

Lemma A.1. Let G=(V,E)G = (V,E) be a connected graph, and Q⊆VQ \subseteq V satisfy 2∣∣Q∣2 \mid|Q|. Then we can find an edge set EQ⊆EE_Q \subseteq E such that ∂G(EQ)=Q\partial_G(E_Q) = Q in time O(max⁡{∣V∣,∣E∣})O(\max\{|V|,|E|\}).

Proof. First, we compute a rooted spanning tree T=(V,ET)T = (V,E_T) of GG in time O(max⁡{∣V∣,∣E∣})O(\max\{|V|,|E|\}). Let the root be rr. We pick the edge set EQ⊆ETE_Q \subseteq E_T as follows. Let e=(u,v)∈ETe = (u,v) \in E_T, and suppose vv is the son of uu. Denote by TvT_v the subtree rooted at vv, and V(Tv)V(T_v) the set of vertices in TvT_v. Then e∈EQe \in E_Q if and only if ∣V(Tv)∩Q∣|V(T_v) \cap Q| is odd. The set EQE_Q can be easily computed in time O(max⁡{∣V∣,∣E∣})O(\max\{|V|,|E|\}) by tracing from the leaves to the root. Therefore we only need to verify that ∂G(EQ)=Q\partial_G(E_Q) = Q. Now, for each non-root vertex vv, the degree of vv in the subgraph (V,EQ)(V,E_Q) is equal (modulo 22) to ∣V(Tv)∩Q∣−∑w is a son of v∣V(Tw)∩Q∣|V(T_v) \cap Q| - \sum_{w\text{ is a son of }v} |V(T_w) \cap Q|, which is 11 if and only if v∈Qv \in Q. Because there is only one root rr, the parity condition forces that r∈Q⇔r∈∂G(EQ)r \in Q \Leftrightarrow r \in\partial_G(E_Q). Therefore ∂G(EQ)=Q\partial_G(E_Q) = Q.

By the above lemma, we can compute the set Ec⊆EE_c \subseteq E such that ∂G(Ec)=Vc\partial_G(E_c) = V_c in time O(max⁡{∣V∣,∣E∣})O(\max\{|V|,|E|\}). Let WW be the sum of the absolute values of weights of EE. For every e∈Ece \in E_c, we add a duplicate of ee to the graph GG, and weight the duplicated edge by W+1W+1. Denote the graph obtained by Gaug=(V,Eaug)G_{aug} = (V,E_{aug}), then it suffices to find E1′⊆EaugE'_1 \subseteq E_{aug} with minimum total weight such that ∂Gaug(E1′)=Vt\partial_{G_{aug}}(E'_1) = V_t. Moreover, VtV_t is the set of odd vertices in GaugG_{aug}. Therefore, ∀E1′⊆Eaug\forall E'_1 \subseteq E_{aug}, ∂Gaug(E1′)=Vt\partial_{G_{aug}}(E'_1) = V_t, we have that (V,Eaug∖E1′)(V,E_{aug} \setminus E'_1) is a Eulerian subgraph, and vice versa. Therefore, it suffices to find a maximum weighted Eulerian subgraph of GaugG_{aug}. We note that ∣Eaug∣≤2∣E∣|E_{aug}| \leq2|E| because Ec⊆EE_c \subseteq E. Moreover, if GG is planar, then GaugG_{aug} is also planar, because adding duplicate edges does not affect planarity. Obviously a planar embedding of GaugG_{aug} can be computed in time O(max⁡{m,n})O(\max\{m,n\}).

Now we convert the maximum weighted Eulerian subgraph problem on GaugG_{aug} to a maximum weighted perfect matching problem, using a procedure almost identical to that in [13]. Starting with the graph GaugG_{aug}, the conversion consists of two steps:

Step 1. For every vertex v∈Vv \in V of degree at least five in GaugG_{aug}, do the following: let the edges incident to vv be e1,e2,…,ere_1,e_2,\ldots,e_r, in cyclic order. Split vv into q=⌈r−12⌉q = \left\lceil\frac{r-1}{2}\right\rceil vertices, u1,…,uqu_1,\ldots,u_q. Add a path u1u2⋯uqu_1u_2\cdots u_q, and weight all edges on the path by zero. Attach e1,e2,e3e_1,e_2,e_3 to u1u_1. Attach e2i,e2i+1e_{2i},e_{2i+1} to uiu_i, for i=2,3,…,q−1i=2,3,\ldots,q-1. Attach e2q,e2q+1,…,ere_{2q},e_{2q+1},\ldots,e_r to uqu_q. This step of modification is depicted in Figure 1.

An example of modification in step 1

Figure 1. An example of modification in step 1. The vertex vv is of degree 8, and is split into three vertices.

Let the graph obtained after step 1 be G(1)=(V(1),E(1))G^{(1)} = (V^{(1)},E^{(1)}), which is still planar if GaugG_{aug} is planar, as is shown in Figure 1. Moreover, every vertex in G(1)G^{(1)} is of degree at most 4. Every Eulerian subgraph of G(1)G^{(1)} corresponds to a Eulerian subgraph of GaugG_{aug} with the same total weight, and vice versa. Therefore we only need to find a maximum weighted Eulerian subgraph in G(1)G^{(1)}. We note that ∣V(1)∣≤∣V∣+∣E∣≤max⁡{m,n}+m=O(max⁡{m,n}),∣E(1)∣≤∣E∣+∣V(1)∣=O(max⁡{m,n})|V^{(1)}| \leq|V|+|E| \leq\max\{m,n\}+m = O(\max\{m,n\}),|E^{(1)}| \leq|E|+|V^{(1)}| = O(\max\{m,n\}).

Step 2. For every vertex vv in G(1)G^{(1)}, do one of the following according to the degree of vv:

(i) If vv is of degree one, let the edge incident to vv be e1e_1. Split vv into K2K_2, weight the edge in K2K_2 by zero, and attach e1e_1 to a vertex in $K_2.

  • (ii) If vv is of degree two, let the edges incident to vv be e1,e2e_1,e_2. Split vv into K2K_2, weight the edge in K2K_2 by zero, and attach e1,e2e_1,e_2 to different vertices in K2K_2.

  • (iii) If vv is of degree three, let the edges incident to vv be e1,e2,e3e_1,e_2,e_3. Split vv into K4K_4, weight the edges in K4K_4 by zero, and attach e1,e2,e3e_1,e_2,e_3 to three different vertices in K4K_4.

  • (iv) If vv is of degree four, let the edges incident to vv be e1,e2,e3,e4e_1,e_2,e_3,e_4. Split vv into K4K_4, weight the edges in K4K_4 by zero, and attach e1,e2,e3,e4e_1,e_2,e_3,e_4 to four different vertices in K4K_4.

The modification in this step is depicted in Figure 2.

The modification in step 2

Figure 2. The modification in step 2. The figures, from left to right, correspond to the cases where vv is of degree 1,2,3,4, respectively.

Let G(2)=(V(2),E(2))G^{(2)}=(V^{(2)},E^{(2)}) be the graph obtained after this step. Then G(2)G^{(2)} is actually a simple graph. It can be verified that, for every Eulerian subgraph of G(1)G^{(1)}, its corresponding edges in G(2)G^{(2)} is a subset of a perfect matching with the same total weight. And for every perfect matching in G(2)G^{(2)}, the edges in G(1)G^{(1)} corresponding to matching edges in G(2)G^{(2)} form a Eulerian subgraph with the same total weight. The verifications are similar to those in [13], which already cover the cases where vv is of degree 3 and 4. Therefore we omit the verifications here. We note that ∣V(2)∣≤4∣V(1)∣=O(max⁡{m,n})|V^{(2)}| \le4|V^{(1)}|=O(\max\{m,n\}), ∣E(2)∣≤∣E(1)∣+6∣V(1)∣=O(max⁡{m,n})|E^{(2)}| \le|E^{(1)}|+6|V^{(1)}|=O(\max\{m,n\}).

Now we only need to find a maximum weighted perfect matching in G(2)G^{(2)}. First, by adding a suitable large number to all weights, we can convert the problem to finding a maximum weighted matching (note that there exists a perfect matching in G(2)G^{(2)}, because empty graph is a Eulerian subgraph of G(1)G^{(1)}). In general case, we can simply apply the Algorithm in [8] to solve the problem in time O((max⁡{m,n})3)O((\max\{m,n\})^3). If GG is planar, then GaugG_{\mathrm{aug}} is planar as well. We can exploit the planarity to reduce the time complexity. Now we describe an algorithm similar to that in [13, 14], using some results of this work:

Theorem A.2 (Theorem 1 of [14]). Let G=(V,E)G=(V,E) be any undirected simple planar graph of nn vertices. Each vertex is assigned a nonnegative weight, such that all weights sums to one. Let n=∣V∣n=|V|. Then there is an O(n)O(n)-time algorithm finding a partition of VV into three sets A,B,CA,B,C satisfying the following conditions. Neither AA or BB has total weight larger than 2/32/3. ∣C∣≤22n|C| \le2\sqrt{2n}. No edge of EE joins a vertex in AA and a vertex in BB.

In the algorithm, we need to apply the above algorithm to the graph G(1)G^{(1)}, and its induced subgraphs. Although G(1)G^{(1)} itself is not simple, each vertex has degree at most 4, and the same condition holds for its induced subgraphs. Therefore we can modify the algorithm and use the following corollary.

Corollary A.3. Let G=(V,E)G=(V,E) be any undirected planar graph, such that each vertex has degree at most 4. Each vertex is assigned a nonnegative weight, such that all weights sums to one. Let n=∣V∣n=|V|. Then there is an O(n)O(n)-time algorithm finding a partition of VV into three sets A,B,CA,B,C satisfying the following conditions. Neither AA or BB has total weight larger than 2/32/3. ∣C∣≤22n|C| \le2\sqrt{2n}. No edge of EE joins a vertex in AA and a vertex in BB.

Proof. By the degree condition, ∣E∣≤2∣V∣=2n|E| \le2|V|=2n. We compute the underlying simple graph in time O(n)O(n), and construct the separator A,B,CA,B,C for the simple graph as in Theorem A.2. Therefore no edge joins a vertex in AA and a vertex in BB in the original graph.

Theorem A.4 (see Lemma 2 in [14] and the comments below it). Let G=(V,E)G=(V,E) be an undirected simple graph with edges weighted, and v∈Vv\in V. Let n=∣V∣n=|V|, m=∣E∣m=|E|. Suppose we know the maximum weighted matching of G−vG-v, then a maximum weighted matching of GG can be computed in time O(mlog⁡n)O(m\log n).

Now we describe the algorithm, which begins with the simple graph G(2)G^{(2)}:

  1. Step 1. If G=(V(G),E(G))G=(V(G),E(G)) contains at most one vertex, return the empty set as the maximum weighted matching.

  1. Step 2. Let the vertices of G(1)G^{(1)} corresponding to vertices in GG form a set VV. For each vertex v∈Vv\in V, let σv∈{2,4}\sigma_v\in\{2,4\} be the number of vertices in the gadget of G(2)G^{(2)} that replaces vv. Assign vv the normalized weight σv∑v∈Vσv\frac{\sigma_v}{\sum_{v\in V}\sigma_v}. Apply the algorithm of Corollary A.3 on the induced graph G(1)[V]G^{(1)}[V] to get a partition of VV into three sets A,B,CA,B,C, where ∣C∣=O(∣V∣)|C|=O(\sqrt{|V|}), the total weight of each of A,BA,B is at most 2/32/3, and no edge of G(1)[V]G^{(1)}[V] joins a vertex in AA and a vertex in BB. Let Ap,Bp,Cp⊆V(G)A_p,B_p,C_p\subseteq V(G) be the unions of gadgets corresponding to A,B,CA,B,C. Then ∣Cp∣≤4∣C∣=O(∣V∣)=O(∣V(G)∣)|C_p|\le4|C|=O(\sqrt{|V|})=O(\sqrt{|V(G)|}), ∣Ap∣≤2∣V(G)∣/3|A_p|\le2|V(G)|/3, ∣Bp∣≤2∣V(G)∣/3|B_p|\le2|V(G)|/3, and no edge of GG joins a vertex in ApA_p and a vertex in BpB_p. Apply our algorithm recursively to G[Ap],G[Bp]G[A_p],G[B_p] to find the maximum weighted matching in G[Ap],G[Bp]G[A_p],G[B_p].

  1. Step 3. Add vertices in CpC_p to G[Ap∪Bp]G[A_p\cup B_p] one at a time. Each time a vertex is added, apply Theorem A.4 to find a maximum weighted matching in the new graph.

The description is completed.

In Step 2, there are no edges of GG joining a vertex in ApA_p and a vertex in BpB_p, therefore the union of maximum weighted matchings of G[Ap],G[Bp]G[A_p],G[B_p] is indeed the maximum weighted matching of G[Ap∪Bp]G[A_p\cup B_p]. Therefore the algorithm is correct. Let t(n)t(n) be the running time of this algorithm on a graph with at most nn vertices. Then

t(1)=c1t(1)=c_1
∀n>1,t(n)≤max⁡{t(n1)+t(n2)+c2n3/2log⁡n:n1+n2=n, n1,n2≤2n/3}.(28)\forall n>1,\quad t(n)\le\max\{t(n_1)+t(n_2)+c_2n^{3/2}\log n:n_1+n_2=n,\ n_1,n_2\le2n/3\}. \tag*{(28)}

Where c1,c2c_1, c_2 are positive constants. An inductive argument shows that t(n)=O(n3/2log⁡n)t(n) = O(n^{3/2}\log n). Therefore the time needed to compute a maximum weighted matching in G(2)G^{(2)} is O(max⁡{m,n}3/2log⁡(max⁡{m,n}))O(\max\{m,n\}^{3/2}\log(\max\{m,n\})).

Moreover, converting the problem to a maximum weighted matching problem costs time at most O(max⁡{m,n})O(\max\{m,n\}). Solving the maximum weighted matching problem costs time O(max⁡{m,n}3/2log⁡(max⁡{m,n}))O(\max\{m,n\}^{3/2}\log(\max\{m,n\})), and recovering the answer E′E' based on the solution also costs time at most O(max⁡{m,n})O(\max\{m,n\}). Therefore the procedure in this appendix costs an overall O(max⁡{m,n}3/2log⁡(max⁡{m,n}))O(\max\{m,n\}^{3/2}\log(\max\{m,n\})) time.

Proof of Theorem 5.10, and the application

Proof of Theorem 5.10, and a corollary

Proof of Theorem 5.10. We assume that GG is loopless by Remark 4.2.

Pick T⊆PT \subseteq P such that (V,T)(V,T) is a spanning forest of (V,P)(V,P). Then G/TG/T is also planar. Pick any planar embedding of G/TG/T (which can be computed in time O(max⁡{m,n})O(\max\{m,n\})), and take the Eulerian-spanning set BT\mathcal{B}_T to be the set of boundary vectors of all faces in the embedding. Let B=πT−1(BT)\mathcal{B} = \pi_T^{-1}(\mathcal{B}_T), where πT\pi_T is as in Lemma 5.6. Then B\mathcal{B} is a Eulerian-spanning set of GG. Note that the size of the matrix ABA_{\mathcal{B}} may already exceed the expected running time. But we can store it in a clever way. Specifically, we simply store the support of each column of ABA_{\mathcal{B}}.

Now we consider the cost of storing the support of each column of ABA_{\mathcal{B}}. By Theorem 5.8, ∣B∣=∣BT∣|\mathcal{B}| = |\mathcal{B}_T|, and ∣BT∣|\mathcal{B}_T| is simply the number of faces of G/TG/T, which cannot exceed O(max⁡{m,n})O(\max\{m,n\}) by Euler’s formula. Now we consider the total cardinality of edge sets in B\mathcal{B}. This value is equal to the number of 1’s in ABA_{\mathcal{B}}, which is in turn equal to

∑e∈EfB(e).\sum_{e \in E} f_{\mathcal{B}}(e).

For e∉Te \notin T, fB(e)≤2f_{\mathcal{B}}(e) \le2. For e∈Te \in T, fB(e)≤∣B∣=O(max⁡{m,n})f_{\mathcal{B}}(e) \le|\mathcal{B}| = O(\max\{m,n\}). Therefore the total cardinality of edge sets in B\mathcal{B} is O((∣T∣+1)max⁡{m,n})O((|T|+1)\max\{m,n\}).

By (14), we only need to solve the following optimization problem and compute an optimal assignment:

min⁡{wTz:ABz=ABc, z∈F2E}.\min\{w^{T}z : A_{\mathcal{B}}z = A_{\mathcal{B}}c,\ z \in\mathbb{F}_2^{E}\}.

Note that we can compute ABcA_{\mathcal{B}}c again by simply determining the value for each edge one by one, which takes a total of O((∣T∣+1)max⁡{m,n})O((|T|+1)\max\{m,n\}) time. Our algorithm is as follows: for every zT∈F2Tz_T \in\mathbb{F}_2^{T}, compute

Q(zT)≜min⁡{wT‾Tz‾T:(AB)T‾z‾T=ABc+(AB)TzT, z‾T∈F2T‾}.Q(z_T) \triangleq\min\{w_{\overline{T}}^{T}\overline{z}_T : (A_{\mathcal{B}})_{\overline{T}}\overline{z}_T = A_{\mathcal{B}}c + (A_{\mathcal{B}})_Tz_T,\ \overline{z}_T \in\mathbb{F}_2^{\overline{T}}\}.

We can again compute (AB)TzT(A_{\mathcal{B}})_Tz_T by simply determining the value for each edge one by one, which takes a total of O((∣T∣+1)max⁡{m,n})O((|T|+1)\max\{m,n\}) time. Let Gd=(Vd,Ed)G_d = (V_d,E_d) be the planar dual of G/TG/T, which is again planar. Then there is a one-to-one correspondence between VdV_d and B\mathcal{B}. Therefore we can also write GdG_d as Gd=(B,Ed)G_d = (\mathcal{B},E_d). We have ∣Ed∣≤∣E∣=m|E_d| \le|E| = m by planar duality. Each edge e∈E∖Te \in E \setminus T corresponds to an edge e=(Bi,Bj)∈Ede=(B_i,B_j)\in E_d such that the boundary vectors of the two faces incident to $e are Bi,BjB_i,B_j. Therefore (AB)T‾=MGd(A_{\mathcal{B}})_{\overline{T}} = M_{G_d}. Then ∀z∈F2E\forall z \in\mathbb{F}_2^E, (AB)T‾z‾T=ABc+(AB)TzT(A_{\mathcal{B}})_{\overline{T}}\overline{z}_T = A_{\mathcal{B}}c + (A_{\mathcal{B}})_Tz_T is equivalent to ∂Gd(supp⁡(z‾T))=supp⁡(ABc+(AB)TzT)\partial_{G_d}(\operatorname{supp}(\overline{z}_T)) = \operatorname{supp}(A_{\mathcal{B}}c + (A_{\mathcal{B}})_Tz_T). After picking the loops with negative weight and removing all loops, we can use Lemma 2.2 to solve the optimization problem and recover an optimal assignment in time O(max⁡{m,n}3/2log⁡max⁡{m,n})O(\max\{m,n\}^{3/2}\log\max\{m,n\}).

Last, we compute min⁡zT{Q(zT)+wTTzT}\min_{z_T}\{Q(z_T)+w_{T}^{\mathsf{T}}z_T\} and get the optimal value and assignment. The total running time is therefore

O(2∣T∣(max⁡{m,n}3/2log⁡(max⁡{m,n})+∣T∣max⁡{m,n}))=O(2∣P∣(max⁡{m,n}3/2log⁡(max⁡{m,n})+∣P∣max⁡{m,n}).O(2^{|T|}(\max\{m,n\}^{3/2}\log(\max\{m,n\})+|T|\max\{m,n\})) =O(2^{|P|}(\max\{m,n\}^{3/2}\log(\max\{m,n\})+|P|\max\{m,n\}).

Because we can also add zero-weighted edges (and arbitrarily assign the violation value) without affecting the optimal solution and assignment of the problem. Then we have the following:

Corollary B.1. Suppose G=(V,E),w,cG=(V,E),w,c is an instance of Problem 4.3. Moreover, we are given another edge set PP, such that if we denote Gaug=(V,E∪P)G_{\mathrm{aug}}=(V,E\cup P), then Gaug/PG_{\mathrm{aug}}/P is planar. Let n=∣V∣n=|V|, m=∣E∣m=|E|, k=∣P∣k=|P|, N=max⁡{m,n}N=\max\{m,n\}. Then an optimal assignment can be found in

O(2k((N+k)3/2log⁡(N+k)+k(N+k)))O(2^k((N+k)^{3/2}\log(N+k)+k(N+k)))

time. The same conclusion holds for maxcut and signed frustration.

Application to the case of crossing numbers

We first present the definition of ss-planar graphs [15] and crossing number of a given embedding.

Definition B.2. A graph G=(V,E)G=(V,E) is ss-planar if it can be embedded in the plane such that each edge is crossed at most ss times. The crossing number of an embedding is obtained in the following way: count the crossings separately for each pair of edges, and for each crossing point of the pair of edges. We say GG has an ss-planar embedding of crossing number kk, if GG can be embedded in the plane such that each edge is crossed at most ss times, and the crossing number of this embedding is kk. We define the crossing number of GG to be the minimum crossing number among all embeddings of GG in the plane.

Remark B.3. Given an embedding of GG in the plane, if there are at least three edges that intersect in one point, we can adjust the edges a little in a local way such that each pair of edges intersect in a different point, without changing the total number of crossings. Therefore, we will always assume that GG is drawn in the plane so that situations in which three edges intersect in one point do not occur.

Lemma B.4. Suppose G=(V,E)G=(V,E) is a simple graph that has a 2-planar embedding of crossing number kk. Then there is another edge set E1E_1 such that ∣E1∣≤k|E_1|\leq k, and if we let Gaug=(V,E∪E1)G_{\mathrm{aug}}=(V,E\cup E_1), then the underlying simple graph of Gaug/E1G_{\mathrm{aug}}/E_1, which we denote by GpG_p, is planar. Moreover, we can compute E1E_1 and the planar embedding of GpG_p in time O(km)O(km).

Proof. We construct a procedure consisting of at most kk rounds. In each round, we do one of the following three things:

  • Re-embed (or redraw) GG in the plane.

  • Contract an edge in GG while merging multiple edges and removing loops.

  • Pick an edge not in GG, add it to GG, and contract it while merging multiple edges and removing loops.

We will show that after each round, G′G' is a simple graph that has a 2-planar embedding of smaller crossing number. Therefore, after at most kk rounds, we will get a planar graph, and the edges we have contracted during the procedure certainly form the set E1E_1 we wanted.

Now suppose G=(V,E)G=(V,E) is a simple graph with a 2-planar embedding of crossing number rr. Pick any intersection point xx, and suppose it is the intersection of e1e_1 and e2e_2. We distinguish between three cases:

(1) If e1e_1 and e2e_2 intersect at least twice, then by 2-planarity of the embedding, they must intersect exactly twice, and cannot possibly intersect any other edge. Therefore, e1,e2e_1,e_2 can be redrawn in the way depicted in Figure 3, such that e1e_1 and e2e_2 do not cross each other, and do not cross any other edges. Therefore the redrawing is indeed 2-planar, and the crossing number is reduced.

Redrawing two intersecting edges

Figure 3. the case of two edges intersecting two times (figures in the left and middle, we distinguish cases whether they share an endpoint or not), and the case where two edges share an endpoint, but intersect only once (figure in the right). The original edges are those in solid lines, while the redrawn ones are those in dotted lines.

(2) If e1e_1 and e2e_2 intersect exactly once at xx, and share an endpoint, say, v1v_1. Let e1=(v1,v2)e_1=(v_1,v_2), e2=(v1,v3)e_2=(v_1,v_3). By 2-planarity, the segments v1xv_1x (on e1e_1), v1xv_1x (on e2e_2), xv2xv_2, xv3xv_3 can intersect other edges at most once each. Therefore, if we redraw the edges e1,e2e_1,e_2 in the way depicted in Figure 3, then they do not intersect each other, and can only intersect at most twice with other edges each. Therefore the redrawing is indeed 2-planar. Moreover, the crossing number is also reduced after the redrawing.

(3) If the endpoints of e1e_1 and e2e_2 are pairwise different, and they intersect only once on xx. Let e1=(v1,v2)e_1=(v_1,v_2), e2=(v3,v4)e_2=(v_3,v_4). By 2-planarity of the embedding, the segments xv1,xv2xv_1,xv_2 on e1e_1 can only be crossed once by other edges altogether. Therefore there must be a segment, say xv1xv_1, that is not crossed by any other edge. Similarly, let xv3xv_3 be the segment on e2e_2 that is not crossed by any other edge. Let e=(v1,v3)e=(v_1,v_3). We further distinguish between two cases:

(i) If e∈Ee\in E, we first contract ee in GG while preserving multiple edges and loops, and redraw the edges e1,e2e_1,e_2 and all edges incident to v1,v3v_1,v_3 in the way depicted in Figure 4. Specifically, we remove the edge ee, move the vertices v1,v3v_1,v_3 to xx along the segments v1x,v3xv_1x,v_3x, and extend the edges incident to v1,v3v_1,v_3 along the corresponding segments. Then we adjust the segments v1x,v3xv_1x,v_3x on edges incident to v1,v3v_1,v_3 in a local way so that they do not cross each other, and do not cross other edges as well.

The case where the endpoints of $e_1$ and $e_2$ are pairwise different and they intersect only once on $x$

Figure 4. The case where the endpoints of e1e_1 and e2e_2 are pairwise different, and they intersect only once on xx. If e=(v1,v3)∈Ee=(v_1,v_3)\in E, we contract ee to the intersection point xx, and redraw all edges incident to v1,v3v_1,v_3 as depicted above (we have not merged multiple edges or removed loops so far).

Then an intersection point in the redrawing must also be an intersection point of GG. Moreover, xx is no longer an intersection point of the redrawing. Therefore the redrawing is 2-planar, and of smaller crossing number. Then we merge multiple edges and remove loops, which cannot affect 2-planarity or increase the crossing number.

(ii) If e∉Ee \notin E, we add the edge ee to GG (we note that the way we draw the edge ee on the plane is irrelevant, because we will contract it soon). Then we contract ee while preserving multiple edges and loops, and redraw the edges e1e_1, e2e_2 and all edges incident to v1v_1, v3v_3 in the way depicted in Figure 5. Specifically, we remove the edge ee, move the vertices v1v_1, v3v_3 to xx along the segments v1xv_1x, v3xv_3x, and extend the edges incident to v1v_1, v3v_3 along the corresponding segments. Then we adjust the segments v1xv_1x, v3xv_3x on edges incident to v1v_1, v3v_3 in a local way so that they do not cross each other, and do not cross other edges as well.

The case where the endpoints of $e_1$ and $e_2$ are pairwise different and they intersect only once on $x$

Figure 5. The case where the endpoints of e1e_1 and e2e_2 are pairwise different, and they intersect only once on xx. If e=(v1,v3)∉Ee=(v_1,v_3)\notin E, we first add ee to GG, then contract ee to the intersection point xx, and redraw all edges incident to v1,v3v_1,v_3 as depicted above (we have not merged multiple edges or removed loops so far).

Then an intersection point in the redrawing must also be an intersection point of GG. Moreover, xx is no longer an intersection point of the redrawing. Therefore the redrawing is indeed 2-planar, and of smaller crossing number. Then we merge multiple edges and remove loops, which cannot affect 2-planarity or increase the crossing number.

Now we consider the computational complexity of finding E1E_1 and planar embedding of GpG_p. Each round of our procedure can be done in time O(m)O(m), since there are at most mm edges to be redrawn. Therefore the total running time of the procedure is O(km)O(km).

Theorem B.5. Suppose G=(V,E),w,cG=(V,E), w, c is an instance of Problem 4.3, where GG is simple. Moreover, suppose that we are given a 2-planar embedding of GG with crossing number kk. Let n=∣V∣n=|V| and m=∣E∣m=|E|. Then there is an algorithm running in O(2k(n3/2log⁡n+kn))O(2^k(n^{3/2}\log n+kn)) time that solves the problem and computes an optimal assignment.

Proof. By [15], m≤5n−10=O(n)m\le5n-10=O(n). Each edge is crossed at most twice, therefore k≤2m=O(n)k\le2m=O(n). Apply Lemma B.4 and Corollary B.1.

Theorem B.6. Suppose G=(V,E),w,cG=(V,E), w, c is an instance of Problem 4.3, and GG is simple. Moreover, we are given a planar embedding of G=(V,E)G=(V,E) with crossing number kk. Let n=∣V∣,m=∣E∣n=|V|,m=|E|. Then there is an O(2k((n+k)3/2log⁡(n+k)+(n+k)k))O(2^k((n+k)^{3/2}\log(n+k)+(n+k)k))-time algorithm solving the problem, and computing the optimal assignment.

Proof. By Remark 4.9, we can assume ∀e∈E\forall e\in E, we≥0w_e\ge0.

For any edge e=(v1,v2)∈Ee=(v_1,v_2)\in E do the following: let a point move from v1v_1 to v2v_2 through edge ee, and the intersection points it encounters be u1,…,ulu_1,\ldots,u_l in chronological order. If l<3l<3, we do nothing. Otherwise, for each i∈{1,2,…,⌊l−12⌋}i\in\{1,2,\ldots,\lfloor\frac{l-1}{2}\rfloor\}, add two vertices z2i−1,z2iz_{2i-1},z_{2i} between u2i,u2i+1u_{2i},u_{2i+1} on ee. Weight every edge on the path v1z1z2⋯z2⌊l−12⌋v2v_1z_1z_2\cdots z_{2\lfloor\frac{l-1}{2}\rfloor}v_2 by wew_e, and set the coordinates of cc on these edges to cec_e. Let the resulting graph be G2G_2. Then G2G_2 is a 2-planar graph with at most n+2kn+2k vertices. Suppose the weight and violation vectors of G2G_2 are w′,c′w',c'. Then the instance (G2,w′,c′)(G_2,w',c') is equivalent to that of GG in the following sense:

View a vector x∈F2Vx\in\mathbb{F}_2^V as a vertex partition. For each subdivided edge e∈Ee\in E, distinguish between two cases:

(1) ce=1c_e=1

If v1v_1 and v2v_2 belong to the same set of the partition, then at most 2⌊l−12⌋2\lfloor\frac{l-1}{2}\rfloor edges on the path v1z1z2⋯z2⌊l−12⌋v2v_1z_1z_2\cdots z_{2\lfloor\frac{l-1}{2}\rfloor}v_2 can satisfy the edge restriction. Otherwise, there is a partition such that all (2⌊l−12⌋+1)(2\lfloor\frac{l-1}{2}\rfloor+1) edges on the path v1z1z2⋯z2⌊l−12⌋v2v_1z_1z_2\cdots z_{2\lfloor\frac{l-1}{2}\rfloor}v_2 satisfy the edge restriction. Therefore, the effect of the path v1z1z2⋯z2⌊l−12⌋v2v_1z_1z_2\cdots z_{2\lfloor\frac{l-1}{2}\rfloor}v_2 is the same as a single edge (v1,v2)(v_1,v_2) weighted by w(e)w(e).

(2) ce=0c_e=0

If v1v_1 and v2v_2 belong to the same set of the partition, then all edges on the path v1z1z2⋯z2⌊l−12⌋v2v_1z_1z_2\cdots z_{2\lfloor\frac{l-1}{2}\rfloor}v_2 can satisfy the edge restriction. Otherwise, at most 2⌊l−12⌋2\lfloor\frac{l-1}{2}\rfloor edges on the path v1z1z2⋯z2⌊l−12⌋v2v_1z_1z_2\cdots z_{2\lfloor\frac{l-1}{2}\rfloor}v_2 can satisfy the edge restriction. Therefore, the effect of the path v1z1z2⋯z2⌊l−12⌋v2v_1z_1z_2\cdots z_{2\lfloor\frac{l-1}{2}\rfloor}v_2 is the same as a single edge (v1,v2)(v_1,v_2) weighted by w(e)w(e).

In conclusion, the instance (G2,w′,c′)(G_2,w',c') is equivalent to that of GG, and we can recover an optimal assignment of GG in time O(n)O(n) if we know that of G2G_2. By Theorem B.5, we can solve the instance on G2G_2 in time O(2k((n+k)3/2log⁡(n+k)+k(n+k)))O(2^k((n+k)^{3/2}\log(n+k)+k(n+k))). This proves the theorem.

Hardness at column weight three

Proof of Theorem 1.3. Membership in NP is obvious. For NP-hardness, we reduce from Exact Cover by 3-Sets (X3C) [9 Problem SP2]. Let U\mathcal{U} be a universe set of size 3q3q, and let S1,…,SmS_1,\ldots,S_m be three-element subsets of U\mathcal{U}. Take AA to be the element–set incidence matrix. We will prove that U\mathcal{U} has an exact cover by sets in S1,…,SmS_1,\ldots,S_m if and only if there is x∈F2mx\in\mathbb{F}_2^m such that Ax=1Ax=\mathbf{1}, wt⁡(x)≤q\operatorname{wt}(x)\le q. Suppose U\mathcal{U} has an exact cover by sets in S1,…,SmS_1,\ldots,S_m. Let x∈F2mx \in\mathbb{F}_2^m be the vector whose coordinates corresponding to the chosen set are 11, and 00 otherwise. Then Ax=1Ax = \mathbf{1} and wt⁡(x)=q\operatorname{wt}(x) = q. Conversely, suppose Ax=1Ax = \mathbf{1} and wt⁡(x)≤q\operatorname{wt}(x) \leq q. Each element is covered an odd (hence at least one) number of times, so the selected sets account for at least 3q3q incidences. Since at most qq sets, each of size three, are selected, they account for at most 3q3q incidences. Thus equality holds throughout: exactly qq sets are selected and every element occurs exactly once. These sets form an exact cover.

Subdivision invariance and unbounded separation

Proposition D.1 (subdivision invariance). Suppose G=(V,E)G = (V,E) is a graph. If G′G' is obtained from GG by replacing one nonloop edge uvuv by a nonempty uu–vv path whose internal vertices are new and have no other incident edges, then

rctr⁡(G′)=rctr⁡(G).\operatorname{rctr}(G') = \operatorname{rctr}(G).

Proof. By Theorem 5.8 we only need to prove rcex⁡(G′)=rcex⁡(G)\operatorname{rcex}(G') = \operatorname{rcex}(G). Pick an Eulerian basis B\mathcal{B} of GG such that ρB=rcex⁡(G)\rho_{\mathcal{B}} = \operatorname{rcex}(G). There is a natural linear isomorphism f:Z(G)→Z(G′)f : \mathcal{Z}(G) \to\mathcal{Z}(G'): the coordinate of the replaced edge is copied to every edge of the replacement path, and all other coordinates remain unchanged. Thus every Eulerian basis of one graph corresponds to an Eulerian basis of the other. Suppose the Eulerian basis of G′G' corresponding to B\mathcal{B} is B′\mathcal{B}'. Then the column vectors in AB′A_{\mathcal{B}'} corresponding to all edges of the replacement path are the same. Moreover, the number of appearances of each subdivided edge in the new Eulerian basis is the same as the original edge in the original Eulerian basis. If that number is at most two, none of these columns belongs to JB′J_{\mathcal{B}'}. If it is at least three, replacing one column by several identical columns does not change the rank of the exceptional-column submatrix. Hence ρB′=ρB\rho_{\mathcal{B}'} = \rho_{\mathcal{B}} and rcex⁡(G′)≤rcex⁡(G)\operatorname{rcex}(G') \leq\operatorname{rcex}(G). Applying the inverse cycle-space isomorphism to an optimal Eulerian basis of G′G' replaces the identical path columns by one column and gives the reverse inequality. Therefore rcex⁡(G′)=rcex⁡(G)\operatorname{rcex}(G') = \operatorname{rcex}(G).

:::

Theorem D.2 (unbounded separation). For L≥1L \geq1, let GLG_L be obtained from K3,3K_{3,3} by replacing every edge by a path of length LL. Then

rctr⁡(GL)=1,ctr⁡(GL)=L.(29)\operatorname{rctr}(G_L) = 1,\qquad\operatorname{ctr}(G_L) = L. \tag*{(29)}

Consequently, ctr⁡(G)\operatorname{ctr}(G) is not bounded by any function of rctr⁡(G)\operatorname{rctr}(G).

Proof. Consider K3,3K_{3,3}. It is nonplanar by Kuratowski’s theorem. Contract an edge a1b1a_1b_1 and we get a wheel, which is planar. By Theorem 5.8 and the obvious inequality rcex⁡(G)≤cex⁡(G)\operatorname{rcex}(G) \leq\operatorname{cex}(G), rctr⁡(K3,3)≤1\operatorname{rctr}(K_{3,3}) \leq1. By non-planarity of K3,3K_{3,3}, rctr⁡(K3,3)=1\operatorname{rctr}(K_{3,3}) = 1. Proposition D.1 gives rctr⁡(GL)=1\operatorname{rctr}(G_L) = 1.

Now consider ctr⁡(GL)\operatorname{ctr}(G_L). Contract all LL edges of one subdivided branch merges its two branch vertices and we get a subdivision of a wheel. So ctr⁡(GL)≤L\operatorname{ctr}(G_L) \leq L.

For the reverse inequality, let PP contain fewer than LL edges, and V(GL)V(G_L) be the vertex set of GLG_L. Any two of the six original branch vertices have distance at least LL, so no connected component of (V(GL),P)(V(G_L),P) contains two vertices present in the original K3,3K_{3,3}. Moreover, every one of the nine subdivided branches retains at least one uncontracted edge. In GL/PG_L/P, the six vertices present in K3,3K_{3,3} are therefore distinct and joined by nine internally disjoint nonempty paths, the same way as the incidence pattern of K3,3K_{3,3}. Therefore one can contract edges in GL/PG_L/P and get K3,3K_{3,3}. By Kuratowski’s theorem, GL/PG_L/P cannot be planar.

References

  1. [1]J. Abello, P. Klavík, J. Kratochvíl, T. Vyskočil, MSOL restricted contractibility to planar graphs, Theoretical Computer Science, 2017, 676: 1–14.
  2. [2]E. Amaldi, V. Kann, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Computer Science, 1998, 209(1–2): 237–260.DOI
  3. [3]E. R. Berlekamp, R. J. McEliece, H. C. A. van Tilburg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory, 1978, 24(3): 384–386.DOI
  4. [4]R. Crowston, M. Fellows, G. Gutin, M. Jones, F. Rosamond, S. Thomassé, A. Yeo, Simultaneously satisfying linear equations over F₂: MaxLin2 and Max-r-Lin2 parameterized above average, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), Leibniz International Proceedings in Informatics (LIPIcs), vol. 13, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2011, pp. 229–240.
  5. [5]R. Crowston, G. Gutin, M. Jones, A. Yeo, Parameterized complexity of satisfying almost all linear equations over F₂, Theory of Computing Systems, 2013, 52(4): 719–728.
  6. [6]J. Edmonds, E. L. Johnson, Matching, Euler tours and the Chinese postman, Mathematical Programming, 1973, 5: 88–124.DOI
  7. [7]Q. Fang, S. Shao, Y. Wu, Eulerian-spanning set and coboundary operator: An investigation of maxcut beyond planar graphs, arXiv:2606.00725, 2026.arxiv.org/abs/2606.00725
  8. [8]H. N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, in Proceedings of the First Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 1990), SIAM, Philadelphia, PA, 1990, pp. 434–443.DOI
  9. [9]M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Company, San Francisco, CA, 1979.
  10. [10]P. A. Golovach, P. van ’t Hof, D. Paulusma, Obtaining planarity by contracting few edges, Theoretical Computer Science, 2013, 476: 38–46.
  11. [11]F. Harary, On the notion of balance of a signed graph, Michigan Mathematical Journal, 1953, 2(2): 143–146.DOI
  12. [12]J. E. Hopcroft, R. E. Tarjan, Efficient planarity testing, Journal of the ACM, 1974, 21(4): 549–568.DOI
  13. [13]F. Liers, G. Pardella, Partitioning planar graphs: A fast combinatorial approach for max-cut, Computational Optimization and Applications, 2012, 51(1): 323–344.
  14. [14]R. J. Lipton, R. E. Tarjan, Applications of a planar separator theorem, SIAM Journal on Computing, 1980, 9(3): 615–627.
  15. [15]J. Pach, G. Tóth, Graphs drawn with few crossings per edge, Combinatorica, 1997, 17(3): 427–439.

Paper details

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

views · 9

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents