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-Lin 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 , , , solve the following problem and find an optimal assignment:
where is evaluated in , and elements are regarded as , respectively.
Special cases of BAO are closely connected with classical problems in coding theory and with optimization problems for linear systems over . If is feasible, then its solution set is an affine coset of the linear code . In the special case for all , 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 , usually formulated as Max-Lin, can also be converted into the form of BAO and provide another closely related viewpoint. Max-Lin contains several graph optimization problems, such as MaxCut and signed frustration. Parameterized complexity results for Max-Lin and its sparse-occurrence cases were developed [4, 5], where the approximation problem was considered. The W[1]-hardness of Max-Lin, 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 variables was studied.
In this paper, we study the complexity of BAO, present fixed-parameter tractable (FPT) algorithms, and explore their applications to Max-Lin (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-Lin, we consider the exact problem rather than the approximation problem. We convert Max-Lin 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 has Hamming weight at most , then BAO can be solved in polynomial time. For convenience, we say that or, equivalently, the BAO problem, satisfies the weight-two condition when this holds.
Theorem 1.2. Let be a matrix satisfying the weight-two condition, and let , . Then the feasibility of can be determined in polynomial time. If the system is feasible, both the value
and an optimal vector 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 -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 has Hamming weight exactly , BAO is still NP-hard. This establishes the tightness of the weight-two condition.
Theorem 1.3. The following problem is NP-complete: given in which every column has Hamming weight three, and an integer , decide whether there is such that
Consequently, minimizing the Hamming weight subject to is NP-hard even when every column of 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 be the indexes of columns of with Hamming weight at least 3. We enumerate all possibilities of . After is fixed, the remaining of the constraint is of the form , where satisfies the weight-two condition. Therefore the remaining problem can be solved within polynomial time, and the total running time must be . However, we can apply this algorithm with some twist. First, for any , . Therefore we can pick any and instead consider the columns of of Hamming weight at least 3. By applying the row operation to , 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 pair , , satisfying , is called a nearly-graphic certificate for .
Let collect all nearly-graphic certificates for . From now on, if is clear from the context, we will simply call 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 , we may not have to go through all possibilities of . Instead, we can consider , enumerate all elements in , and compute an optimal for each of the images. We have . Moreover, , which is an advantage. This leads to the definition of the following nearly-graphic parameters.
Definition 1.5 (nearly-graphic parameters). Let . Define the following parameters:
If is a nearly-graphic certificate for , then its support size is , and its non-graphic rank is
The notations exc, rex are abbreviations of the phrases “exceptional columns” and “rank of exceptional columns”, respectively. When a nearly-graphic certificate for is provided, we obtain two FPT algorithms solving BAO, parameterized by and , respectively.
Theorem 1.6. Let be an instance of BAO, and . Suppose a nearly-graphic certificate is given. Put and . The validity of the supplied certificate can be checked in time polynomial in . If it is valid, then there are two algorithms finding the optimum and an optimal assignment in and time, respectively.
We explore the application of Theorem 1.6 and consider the weighted Max-Lin problem, which is defined as follows.
Definition 1.7 (weighted Max-Lin). Let , , . We aim to compute
and an optimal vector . Here is evaluated in , and elements are regarded as , respectively.
The form of Max-Lin is different from that of BAO, hence we need to convert it. This is done by computing a representation of the left-nullspace of . Specifically, let be a matrix whose row space is (by we always mean the right-nullspace of a matrix, that’s why the left-nullspace of reads here). Then we have
Indeed, if , then , and hence . Conversely, if , then . Since the row space of is ,
Thus for some , which proves (6). Weighted Max-Lin is therefore equivalent to
By the conversion, we can recover an optimal assignment of if we know the optimal assignment of (7) in polynomial time. Therefore, if a nearly-graphic certificate of is provided, we can apply Theorem 1.6 and solve Max-Lin in , or time.
However, the choice of is not unique in general. Therefore, if a nearly-graphic certificate is to be provided, one must first specify , which is unrealistic. Hence we make further exploration by considering a special case of Max-Lin, i.e. Max-Lin on graphs. For brevity, here we omit the original form of Max-Lin on graphs, which is in § 4. We will show that, for Max-Lin on a graph , must be taken to represent the cycle space of . This leads to the concept of Eulerian-spanning set of , which is a multiset of vectors spanning the cycle space of . Therefore we can take to be the incidence matrix of a Eulerian-spanning set of . Denote the matrix by and we get the following BAO problem:
We will show that, , are independent from the choice of , and are equal to the contraction distance and contraction rank of , respectively. The contraction distance is the minimum number of edges to contract to make planar, while the contraction rank is a little more complicated and will be explained in § 5. Moreover, can be simply taken to be the set of edges whose contraction makes planar. More importantly, we can use the FPT algorithms in [10, 1] to compute the contraction distance of , and find the corresponding edge set. Therefore we get an FPT algorithm for Max-Lin on graphs parameterized by contraction distance, which needs no information other than the problem itself.
Theorem 1.8. Let be a graph, and be the contraction distance of . One can solve weighted Boolean Max-Lin on a graph , and find an optimal assignment in time , where is a function independent of .
A formal definition of 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 is provided, we design a more refined algorithm that reduces the exponent with respect to . 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 . However, we are not aware of any FPT algorithm for computing the contraction rank of , 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 . 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 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 is a graph, then denotes the number of connected components of . If is a graph and , then is the subgraph induced by .
Copies of the same element in a multiset are treated differently. For an integer , write , with the convention .
Unless stated otherwise, all vector spaces, matrices, and linear-algebraic operations in Sections 2–5 are over . For a binary vector , let and denote its support and Hamming weight. For where is clear from the context, write and use and for the corresponding subvectors and column submatrices. The notation denotes the th column of , and denotes the all-ones vector of the dimension determined by context. The rank of an empty matrix is zero.
For the vector space , , the non-degenerate symmetric bilinear form is taken in the obvious way, i.e. . 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 be a graph. For , let be the set of vertices of odd degree in the subgraph . A loop contributes two to the degree. For , a set is a -join if .
Since a loop contributes to the degree, including it or not does not affect . Hence, we may select all negative-weight loops, delete all loops from the graph, and work with the resulting graph instead. Therefore, when considering -joins, we may assume without loss of generality that is loopless. It is easy to see that a -join exists if and only if every connected component of contains an even number of vertices of . Necessity follows from a simple counting argument. For sufficiency, pair the vertices of arbitrarily within each component, choose a path for each pair, and take the symmetric difference of the edge sets of these paths.
The -join problem can be solved in polynomial time. Moreover, if is planar, the running time can be further decreased. The algorithm for planar graphs will be used later.
Lemma 2.2. Let be a loopless graph with weight function , let , and write , . Then there is an -time algorithm that either finds a minimum-weight edge subset satisfying , or reports that none exists. If is planar, the running time improves to .
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 -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 on those coordinates to be if the corresponding weight is positive, and otherwise. From now on we assume that has no zero columns. Construct a graph with vertex set , where is a new vertex. A column with support becomes an edge , and a column with support becomes an edge . The edge inherits the weight of the corresponding column.
Set
For , let be the corresponding set of graph edges. Then we have , . Hence
By Lemma Lemma 2.2, we can solve the above problem and recover an optimal vector in polynomial time. □
Remark 2.3. What we do in the proof is equivalent to attaching a row to that is the sum of all rows in . If we denote the matrix obtained by , then every column of has Hamming weight two. Moreover, is exactly the incidence matrix of the graph .
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 , , . Put and . For every , define
Let . Then all values for , together with all minimizers , can be computed in time .
Proof of Lemma 3.1. Order as . Choose a linear isomorphism , which can be computed by the Gaussian elimination, and let . For and , let
Then and for . Splitting a subset according to whether it contains gives
We have , . Then one can compute all values of , and hence in time . Moreover, we can keep track of the optimal assignments achieving during the computation. Therefore those achieving can be simultaneously obtained in the end of the induction.
Proof of Theorem 1.6. First apply the Gaussian Elimination to the system . If it detects an inconsistent system, report inconsistency and stop. Then we can verify in polynomial time that is invertible and that every column of outside has weight at most two. Afterwards, set and , so that is equivalent to . Now we give two different algorithms that achieve the two time complexities respectively.
For time complexity , we use the following algorithm to solve the problem. Use Lemma 3.1 to compute all , together with those achieving the optimum. The time cost of this procedure is . If , then the remaining coordinates must satisfy
We note that addition and subtraction are equivalent in , therefore . Moreover, has column weight at most two, so we can apply Theorem 1.2 to either detect infeasibility or obtain an such that achieves minimum. Denote this minimum by , and take when the system is infeasible. Then it is easy to see that the optimum value for the original BAO problem is
If for every , report that the affine system is infeasible. Otherwise, choose an attaining a finite minimum in (12). We already have after applying the algorithm in Lemma 3.1. can be recovered when applying Theorem 1.2. Concatenate and to obtain an optimal .
For time complexity , we use the following algorithm. For every , use Theorem 1.2 to compute
Then the optimal value is equal to
and the total time complexity is .
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 .
Max-Lin2 on graphs and Eulerian-spanning set
Before we proceed, we make the following conventions. Suppose is a finite multiset and is a field. Then is the linear space over with dimension . is regarded to be indexed by the multiset . Moreover, if , then every element in is regarded as an indicator function of some subset of . Suppose are two subsets of the same multiset . Then is the symmetric difference between . Moreover, the symmetric bilinear form on is defined as , . It is obvious that is non-degenerative.
Problem 4.1 (weighted Boolean Max-Lin2 on graphs). Suppose is a graph in which each edge has weight . In addition, a violation variable is associated with each edge . For , the violation vector is defined by
Our goal is to solve the following optimization problem, and compute an optimal assignment:
Remark 4.2. A loop corresponds to a fixed bit . By adding the constant to the objective and deleting the loop equations, we may assume that 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 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 admits a more concise expression in terms of the incidence matrix of a graph. Given a graph , its incidence matrix is defined as follows: its rows are indexed by , and its columns are indexed by ; moreover, for all and , if and only if is not a loop and is an endpoint of .
Problem 4.3 (weighted Boolean Max-Lin2 on graphs). Suppose is a graph, is a weight vector, and is a given violation vector. For , the violation vector is defined as
Our goal is to solve the optimization problem: .
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 is a graph and is its incidence matrix. Define the cycle space of to be . A Eulerian-spanning set of is a multiset consisting of elements in , such that the span of elements
in is . If elements in are linearly independent, then is called a Eulerian basis of . Its edge frequency for a certain is . Let be the matrix whose th row is the incidence vector of . Define the following exceptional parameters:
and will be called the exceptional rank of .
Remark 4.5. Every Eulerian subgraph of 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 , 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 and (7) yields
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-Lin on graphs.
Problem 4.6 (maxcut). Let be a graph with edge-weight vector , and . Define . Then
That is, the maxcut problem corresponds to the case of in Problem 4.3, and applying (14) then yields the following equivalent form.
Corollary 4.7. Let be a graph with edge-weight vector , , and let be a Eulerian-spanning set of . Then
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 and a negative edge by . A signed graph is balanced exactly when every cycle contains an even number of negative edges [11].
Problem 4.8 (signed frustration). Let be a signed graph with sign vector (obtained in the way described above) and edge-weight vector , and let be a Eulerian basis of . Then the minimum total weight of violated edges in any vertex assignment is
Remark 4.9. In an instance of signed frustration problem, if we pick an edge , change to , and to , 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 .
Contraction distance and contraction rank
Suppose is a graph and is a Eulerian-spanning set of . In this section we will show that , are independent from the choice of , and are equal to the contraction distance and contraction rank of , 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 , and the contraction distance and contraction rank of , 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 is a graph. For an edge set , define by identifying all vertices in each connected component of and deleting the edges of . Define to be .
It is easy to see that is the graph obtained by contracting the edges of sequentially.
If is a connected component of , then the projection of to is exactly the space of vectors with even Hamming weight. Thus with being the number of connected components of . And by the rank-nullity theorem, we have
We need a lemma that computes the rank of for any edge set .
Lemma 5.2. Suppose is a graph and is a Eulerian basis of . For every ,
In particular, this value is independent of .
Proof. Restricting a Eulerian edge set to the coordinates in defines a linear map
Its image is the row space of , and its kernel consists exactly of the Eulerian edge sets supported in , namely . Using the rank-nullity theorem and (16) gives . □
Let collect all Eulerian-spanning sets of and collect all Eulerian bases of . We are going to prove that the nearly-graphic parameters of are independent of the choice of .
Theorem 5.3. Suppose is a graph and is a Eulerian-spanning set of . Then
Proof. Suppose . For any , is the incidence matrix of another Eulerian-spanning set. We have
For any Eulerian-spanning set , there is a Eulerian basis , and , . Thus
For any Eulerian basis , there exists a , such that , implying
Hence equality holds all along.
For a graph , we set
The last three quantities are called the cographic rank of , the contraction distance of , and the contraction rank of , respectively. The inequalities and are immediate. We note that if and only if is planar. To see the nontrivial direction, let satisfy is planar and . The proof of Lemma 5.2 yields that the restriction of every vector in to is zero. Hence no edge of lies on a cycle, so every edge of is a bridge. Construct an auxiliary graph , with vertices corresponding to connected components of , 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 , contradicting the fact that . Each component of is planar because it is isomorphic to a subgraph of the planar graph . Pick any root of . 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 .
Cycle spaces under contraction
Definition 5.4 (coordinate projection). Suppose is a graph. Let be the natural coordinate projection. The target coordinates are naturally identified with the edges of .
Lemma 5.5 (forest contraction witnesses). Suppose is a graph. Let , and let be a spanning forest of . If is planar, then is planar and . Consequently, a minimum-cardinality contraction edge set may be chosen to be a forest.
Proof. Every edge of becomes a loop in , and deleting these loops from gives . Since adding loops preserves planarity, is planar whenever is planar. The inequality is obvious.
Lemma 5.6 (contraction projection). Let be a graph. We have, (1) for every , the map is surjective; (2) if is a forest, then 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 is a forest. The kernel of consists of Eulerian edge sets supported in . But a forest contains no nonempty Eulerian edge set, so the kernel is zero. Contracting decreases both the number of edges and the number of vertices by and leaves the number of connected components unchanged. Thus and have the same dimension, and is an isomorphism.
For arbitrary , choose a spanning forest of . In , the edges of are loops, and deleting these loops gives . Given , extend it to by assigning value zero to every loop in . By the forest case proven above (part 2 of this theorem), there exists a unique such that . Therefore and 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 is a graph, define the basis number of to be
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 is planar if and only if . We need and prove the following form.
Theorem 5.7 (Mac Lane’s criterion for graphs). A graph is planar if and only if , or equivalently, it has a Eulerian basis satisfying for every edge .
Proof. First suppose that is planar. Fix an arbitrary planar embedding of . For a face of the embedding, define its boundary vector by declaring that is the number of occurrences of in the boundary walk of , reduced modulo two. Then a bridge, which is traversed twice by the same facial boundary walk, has coordinate zero. For each connected component of , view the induced drawing of as a plane embedding in its own right and let be its face set. Then every cycle in 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 is itself. Therefore the boundary vectors do span . 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 . Since every edge is incident to at most two faces, it occurs in at most two chosen vectors.
Conversely, suppose that has a Eulerian basis in which every edge has frequency at most two, and let be the set of loops in . Then the natural coordinate projection onto maps surjectively onto . Project , delete the zero vectors, and select a basis from the remaining vectors to form a new set . Then each edge can appear in at most two elements in . 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 . Again, each edge can appear in at most two elements in .
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 ,
Moreover, given such that is planar and a planar embedding of , one can construct in polynomial time a Eulerian basis of satisfying
Proof. We first prove
Let be a Eulerian basis and put . By Lemma 5.6(1), the vectors , with , span . Delete zero vectors and select a basis from the remaining vectors to form a basis . Every edge of corresponds to an edge outside and therefore occurs in at most two vectors in . Theorem 5.7 implies that is planar. By Lemma 5.2,
Minimizing the above inequalities over gives (25).
Next we prove
Let be such that is planar, and let be a spanning forest of . Lemma 5.5 gives that is planar. By Theorem 5.7, choose a Eulerian basis of in which every edge has frequency at most two. Since is a forest, Lemma 5.6(2) gives a unique lift of every . These lifts form a Eulerian basis of . For each edge , the coordinate is unchanged by the lift, so . Thus
It follows that
Minimizing the first inequality over cardinality-minimal and the second over rank-minimal leads to (26). Combining (25) and (26) together proves (23).
For the constructive statement, start from the given embedding of . Let be a spanning forest of . Lemma 5.5 gives that is planar. We can compute an embedding of by simply adding the loops corresponding to to . By Theorem 5.7, there is a Eulerian basis of such that for each edge , . Therefore we only have to compute the lift .
The unique lift can be computed directly. Root every tree component of arbitrarily. For a fixed , define a vector by first setting for every . For a vertex , let be the number of incidences at among the edges in , with a loop counted twice. For a nonroot vertex in , let be its parent edge and let be the rooted subtree at . Let be the vertex set of . Set
Let . Now we show that is a Eulerian subgraph of . Indeed, for every nonroot vertex, the parity contributed by its parent edge is the same as that of the incidences with and the child edges, so its degree in is even. For a root with tree component , let be the vertex set of . Then the sum equals, modulo two, the degree of at the corresponding vertex of , which is even. So the root degree is also even. Thus by Lemma 5.6(2). The construction is polynomial, and the inequalities above give (24). □
Corollary 5.9. Suppose is an instance of Problem 4.3. Moreover, we are given a such that is planar. Then there are two algorithms finding the optimal value and an optimal assignment in time
respectively. The same conclusion holds for the maxcut and signed frustration problems.
Proof. By Remark 4.2, we assume that is loopless. A planar embedding of can be found in polynomial time by the planarity-testing algorithm in [12]. Construct the Eulerian basis by Theorem 5.8. Then is a nearly-graphic certificate for . so Theorem 1.6 gives the stated running time. The special cases follow from Corollary 4.7 and Remark 4.9. □
Let . If we relax the exponent above to , we can actually apply a more delicate algorithm that takes time ).
Theorem 5.10. Suppose is an instance of Problem 4.3. Moreover, we are given such that is planar. Let . Then the optimal value and an optimal assignment can be found in time
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 . The Planar Contraction decision problem asks whether an input pair admits a set with such that is planar. There is an -time algorithm for solving it [10, 1]. Put . Run the decision algorithm for until the first time that the algorithm accepts. This process terminates, because contracting a spanning forest of produces a planar graph consisting only of loops. If is the first value for which the algorithm accepts, the total running time of these calls is at most .
Now we recover the set by self-reduction. Call a positive instance if there is a set with such that is planar. If a nonplanar instance is positive, then there must be an edge such that the instance is positive. Therefore we go through all edges, choose one such that the instance is positive, contract it, and repeat the procedure until the graph is planar. This uses at most decision calls. The search therefore takes at most time. For the returned set , one has . Applying Corollary 5.9 concludes the proof.
Conclusion and outlook
In this paper, we give an FPT algorithm solving 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 . When the constraints of are defined by a graph, we use Eulerian-spanning set to describe the converted affine system, and prove that the nearly-graphic parameters of , i.e. , are equal to , , respectively. We therefore give FPT algorithms solving on graphs. We specifically obtain an FPT algorithm solving 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 and .
Several problems are left open for the future. Finding a nearly-graphic certificate that has optimal, or nearly optimal parameters for the affine system is an important one. Additionally, one may try to minimize the exponents above 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 without loops, a vertex set . Our goal is to find the minimum weighted set such that , or claim that no such exists. If is not connected, we can solve the problem on each connected component of , respectively. Therefore, we assume that is connected from now on. Moreover, if , then by a simple counting argument there can be no such . Therefore, we assume that from now on.
We first convert the problem to a maximum weighted Eulerian subgraph problem. Let be the set of vertices of odd degree in , and . Now we need to compute an edge set such that . Specifically, we have the following lemma:
Lemma A.1. Let be a connected graph, and satisfy . Then we can find an edge set such that in time .
Proof. First, we compute a rooted spanning tree of in time . Let the root be . We pick the edge set as follows. Let , and suppose is the son of . Denote by the subtree rooted at , and the set of vertices in . Then if and only if is odd. The set can be easily computed in time by tracing from the leaves to the root. Therefore we only need to verify that . Now, for each non-root vertex , the degree of in the subgraph is equal (modulo ) to , which is if and only if . Because there is only one root , the parity condition forces that . Therefore .
By the above lemma, we can compute the set such that in time . Let be the sum of the absolute values of weights of . For every , we add a duplicate of to the graph , and weight the duplicated edge by . Denote the graph obtained by , then it suffices to find with minimum total weight such that . Moreover, is the set of odd vertices in . Therefore, , , we have that is a Eulerian subgraph, and vice versa. Therefore, it suffices to find a maximum weighted Eulerian subgraph of . We note that because . Moreover, if is planar, then is also planar, because adding duplicate edges does not affect planarity. Obviously a planar embedding of can be computed in time .
Now we convert the maximum weighted Eulerian subgraph problem on to a maximum weighted perfect matching problem, using a procedure almost identical to that in [13]. Starting with the graph , the conversion consists of two steps:
Step 1. For every vertex of degree at least five in , do the following: let the edges incident to be , in cyclic order. Split into vertices, . Add a path , and weight all edges on the path by zero. Attach to . Attach to , for . Attach to . This step of modification is depicted in Figure 1.

Figure 1. An example of modification in step 1. The vertex is of degree 8, and is split into three vertices.
Let the graph obtained after step 1 be , which is still planar if is planar, as is shown in Figure 1. Moreover, every vertex in is of degree at most 4. Every Eulerian subgraph of corresponds to a Eulerian subgraph of with the same total weight, and vice versa. Therefore we only need to find a maximum weighted Eulerian subgraph in . We note that .
Step 2. For every vertex in , do one of the following according to the degree of :
(i) If is of degree one, let the edge incident to be . Split into , weight the edge in by zero, and attach to a vertex in $K_2.
(ii) If is of degree two, let the edges incident to be . Split into , weight the edge in by zero, and attach to different vertices in .
(iii) If is of degree three, let the edges incident to be . Split into , weight the edges in by zero, and attach to three different vertices in .
(iv) If is of degree four, let the edges incident to be . Split into , weight the edges in by zero, and attach to four different vertices in .
The modification in this step is depicted in Figure 2.

Figure 2. The modification in step 2. The figures, from left to right, correspond to the cases where is of degree 1,2,3,4, respectively.
Let be the graph obtained after this step. Then is actually a simple graph. It can be verified that, for every Eulerian subgraph of , its corresponding edges in is a subset of a perfect matching with the same total weight. And for every perfect matching in , the edges in corresponding to matching edges in form a Eulerian subgraph with the same total weight. The verifications are similar to those in [13], which already cover the cases where is of degree 3 and 4. Therefore we omit the verifications here. We note that , .
Now we only need to find a maximum weighted perfect matching in . 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 , because empty graph is a Eulerian subgraph of ). In general case, we can simply apply the Algorithm in [8] to solve the problem in time . If is planar, then 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 be any undirected simple planar graph of vertices. Each vertex is assigned a nonnegative weight, such that all weights sums to one. Let . Then there is an -time algorithm finding a partition of into three sets satisfying the following conditions. Neither or has total weight larger than . . No edge of joins a vertex in and a vertex in .
In the algorithm, we need to apply the above algorithm to the graph , and its induced subgraphs. Although 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 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 . Then there is an -time algorithm finding a partition of into three sets satisfying the following conditions. Neither or has total weight larger than . . No edge of joins a vertex in and a vertex in .
Proof. By the degree condition, . We compute the underlying simple graph in time , and construct the separator for the simple graph as in Theorem A.2. Therefore no edge joins a vertex in and a vertex in in the original graph.
Theorem A.4 (see Lemma 2 in [14] and the comments below it). Let be an undirected simple graph with edges weighted, and . Let , . Suppose we know the maximum weighted matching of , then a maximum weighted matching of can be computed in time .
Now we describe the algorithm, which begins with the simple graph :
Step 1. If contains at most one vertex, return the empty set as the maximum weighted matching.
Step 2. Let the vertices of corresponding to vertices in form a set . For each vertex , let be the number of vertices in the gadget of that replaces . Assign the normalized weight . Apply the algorithm of Corollary A.3 on the induced graph to get a partition of into three sets , where , the total weight of each of is at most , and no edge of joins a vertex in and a vertex in . Let be the unions of gadgets corresponding to . Then , , , and no edge of joins a vertex in and a vertex in . Apply our algorithm recursively to to find the maximum weighted matching in .
Step 3. Add vertices in to 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 joining a vertex in and a vertex in , therefore the union of maximum weighted matchings of is indeed the maximum weighted matching of . Therefore the algorithm is correct. Let be the running time of this algorithm on a graph with at most vertices. Then
Where are positive constants. An inductive argument shows that . Therefore the time needed to compute a maximum weighted matching in is .
Moreover, converting the problem to a maximum weighted matching problem costs time at most . Solving the maximum weighted matching problem costs time , and recovering the answer based on the solution also costs time at most . Therefore the procedure in this appendix costs an overall 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 is loopless by Remark 4.2.
Pick such that is a spanning forest of . Then is also planar. Pick any planar embedding of (which can be computed in time ), and take the Eulerian-spanning set to be the set of boundary vectors of all faces in the embedding. Let , where is as in Lemma 5.6. Then is a Eulerian-spanning set of . Note that the size of the matrix 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 .
Now we consider the cost of storing the support of each column of . By Theorem 5.8, , and is simply the number of faces of , which cannot exceed by Euler’s formula. Now we consider the total cardinality of edge sets in . This value is equal to the number of 1’s in , which is in turn equal to
For , . For , . Therefore the total cardinality of edge sets in is .
By (14), we only need to solve the following optimization problem and compute an optimal assignment:
Note that we can compute again by simply determining the value for each edge one by one, which takes a total of time. Our algorithm is as follows: for every , compute
We can again compute by simply determining the value for each edge one by one, which takes a total of time. Let be the planar dual of , which is again planar. Then there is a one-to-one correspondence between and . Therefore we can also write as . We have by planar duality. Each edge corresponds to an edge such that the boundary vectors of the two faces incident to $e are . Therefore . Then , is equivalent to . 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 .
Last, we compute and get the optimal value and assignment. The total running time is therefore
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 is an instance of Problem 4.3. Moreover, we are given another edge set , such that if we denote , then is planar. Let , , , . Then an optimal assignment can be found in
time. The same conclusion holds for maxcut and signed frustration.
Application to the case of crossing numbers
We first present the definition of -planar graphs [15] and crossing number of a given embedding.
Definition B.2. A graph is -planar if it can be embedded in the plane such that each edge is crossed at most 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 has an -planar embedding of crossing number , if can be embedded in the plane such that each edge is crossed at most times, and the crossing number of this embedding is . We define the crossing number of to be the minimum crossing number among all embeddings of in the plane.
Remark B.3. Given an embedding of 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 is drawn in the plane so that situations in which three edges intersect in one point do not occur.
Lemma B.4. Suppose is a simple graph that has a 2-planar embedding of crossing number . Then there is another edge set such that , and if we let , then the underlying simple graph of , which we denote by , is planar. Moreover, we can compute and the planar embedding of in time .
Proof. We construct a procedure consisting of at most rounds. In each round, we do one of the following three things:
Re-embed (or redraw) in the plane.
Contract an edge in while merging multiple edges and removing loops.
Pick an edge not in , add it to , and contract it while merging multiple edges and removing loops.
We will show that after each round, is a simple graph that has a 2-planar embedding of smaller crossing number. Therefore, after at most rounds, we will get a planar graph, and the edges we have contracted during the procedure certainly form the set we wanted.
Now suppose is a simple graph with a 2-planar embedding of crossing number . Pick any intersection point , and suppose it is the intersection of and . We distinguish between three cases:
(1) If and intersect at least twice, then by 2-planarity of the embedding, they must intersect exactly twice, and cannot possibly intersect any other edge. Therefore, can be redrawn in the way depicted in Figure 3, such that and 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.

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 and intersect exactly once at , and share an endpoint, say, . Let , . By 2-planarity, the segments (on ), (on ), , can intersect other edges at most once each. Therefore, if we redraw the edges 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 and are pairwise different, and they intersect only once on . Let , . By 2-planarity of the embedding, the segments on can only be crossed once by other edges altogether. Therefore there must be a segment, say , that is not crossed by any other edge. Similarly, let be the segment on that is not crossed by any other edge. Let . We further distinguish between two cases:
(i) If , we first contract in while preserving multiple edges and loops, and redraw the edges and all edges incident to in the way depicted in Figure 4. Specifically, we remove the edge , move the vertices to along the segments , and extend the edges incident to along the corresponding segments. Then we adjust the segments on edges incident to in a local way so that they do not cross each other, and do not cross other edges as well.

Figure 4. The case where the endpoints of and are pairwise different, and they intersect only once on . If , we contract to the intersection point , and redraw all edges incident to 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 . Moreover, 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 , we add the edge to (we note that the way we draw the edge on the plane is irrelevant, because we will contract it soon). Then we contract while preserving multiple edges and loops, and redraw the edges , and all edges incident to , in the way depicted in Figure 5. Specifically, we remove the edge , move the vertices , to along the segments , , and extend the edges incident to , along the corresponding segments. Then we adjust the segments , on edges incident to , in a local way so that they do not cross each other, and do not cross other edges as well.

Figure 5. The case where the endpoints of and are pairwise different, and they intersect only once on . If , we first add to , then contract to the intersection point , and redraw all edges incident to 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 . Moreover, 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 and planar embedding of . Each round of our procedure can be done in time , since there are at most edges to be redrawn. Therefore the total running time of the procedure is .
Theorem B.5. Suppose is an instance of Problem 4.3, where is simple. Moreover, suppose that we are given a 2-planar embedding of with crossing number . Let and . Then there is an algorithm running in time that solves the problem and computes an optimal assignment.
Proof. By [15], . Each edge is crossed at most twice, therefore . Apply Lemma B.4 and Corollary B.1.
Theorem B.6. Suppose is an instance of Problem 4.3, and is simple. Moreover, we are given a planar embedding of with crossing number . Let . Then there is an -time algorithm solving the problem, and computing the optimal assignment.
Proof. By Remark 4.9, we can assume , .
For any edge do the following: let a point move from to through edge , and the intersection points it encounters be in chronological order. If , we do nothing. Otherwise, for each , add two vertices between on . Weight every edge on the path by , and set the coordinates of on these edges to . Let the resulting graph be . Then is a 2-planar graph with at most vertices. Suppose the weight and violation vectors of are . Then the instance is equivalent to that of in the following sense:
View a vector as a vertex partition. For each subdivided edge , distinguish between two cases:
(1)
If and belong to the same set of the partition, then at most edges on the path can satisfy the edge restriction. Otherwise, there is a partition such that all edges on the path satisfy the edge restriction. Therefore, the effect of the path is the same as a single edge weighted by .
(2)
If and belong to the same set of the partition, then all edges on the path can satisfy the edge restriction. Otherwise, at most edges on the path can satisfy the edge restriction. Therefore, the effect of the path is the same as a single edge weighted by .
In conclusion, the instance is equivalent to that of , and we can recover an optimal assignment of in time if we know that of . By Theorem B.5, we can solve the instance on in time . 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 be a universe set of size , and let be three-element subsets of . Take to be the element–set incidence matrix. We will prove that has an exact cover by sets in if and only if there is such that , . Suppose has an exact cover by sets in . Let be the vector whose coordinates corresponding to the chosen set are , and otherwise. Then and . Conversely, suppose and . Each element is covered an odd (hence at least one) number of times, so the selected sets account for at least incidences. Since at most sets, each of size three, are selected, they account for at most incidences. Thus equality holds throughout: exactly 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 is a graph. If is obtained from by replacing one nonloop edge by a nonempty – path whose internal vertices are new and have no other incident edges, then
Proof. By Theorem 5.8 we only need to prove . Pick an Eulerian basis of such that . There is a natural linear isomorphism : 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 corresponding to is . Then the column vectors in 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 . If it is at least three, replacing one column by several identical columns does not change the rank of the exceptional-column submatrix. Hence and . Applying the inverse cycle-space isomorphism to an optimal Eulerian basis of replaces the identical path columns by one column and gives the reverse inequality. Therefore .
:::
Theorem D.2 (unbounded separation). For , let be obtained from by replacing every edge by a path of length . Then
Consequently, is not bounded by any function of .
Proof. Consider . It is nonplanar by Kuratowski’s theorem. Contract an edge and we get a wheel, which is planar. By Theorem 5.8 and the obvious inequality , . By non-planarity of , . Proposition D.1 gives .
Now consider . Contract all edges of one subdivided branch merges its two branch vertices and we get a subdivision of a wheel. So .
For the reverse inequality, let contain fewer than edges, and be the vertex set of . Any two of the six original branch vertices have distance at least , so no connected component of contains two vertices present in the original . Moreover, every one of the nine subdivided branches retains at least one uncontracted edge. In , the six vertices present in are therefore distinct and joined by nine internally disjoint nonempty paths, the same way as the incidence pattern of . Therefore one can contract edges in and get . By Kuratowski’s theorem, cannot be planar.
References
- [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]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]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]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]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]J. Edmonds, E. L. Johnson, Matching, Euler tours and the Chinese postman, Mathematical Programming, 1973, 5: 88–124.DOI
- [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]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]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]P. A. Golovach, P. van ’t Hof, D. Paulusma, Obtaining planarity by contracting few edges, Theoretical Computer Science, 2013, 476: 38–46.
- [11]F. Harary, On the notion of balance of a signed graph, Michigan Mathematical Journal, 1953, 2(2): 143–146.DOI
- [12]J. E. Hopcroft, R. E. Tarjan, Efficient planarity testing, Journal of the ACM, 1974, 21(4): 549–568.DOI
- [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]R. J. Lipton, R. E. Tarjan, Applications of a planar separator theorem, SIAM Journal on Computing, 1980, 9(3): 615–627.
- [15]J. Pach, G. Tóth, Graphs drawn with few crossings per edge, Combinatorica, 1997, 17(3): 427–439.