Eulerian-spanning set and coboundary operator: An investigation of maxcut beyond planar graphs
Qiming Fang, Sihong Shao, Yuxuan Wu · 2026
Read Eulerian-spanning set and coboundary operator: An investigation of maxcut beyond planar graphs by Qiming Fang, Sihong Shao, Yuxuan Wu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00725.txt.
Introduction
Fang, Shao, and Wu extend a classic trick for the maxcut problem in this 2026 maths paper. Maxcut asks how to split a graph's nodes into two sets so the weight of edges between them is as large as can be. Hadlock once turned maxcut on planar graphs into a simpler form. Graphs in that class lie flat with no crossed edges.
Their tools are an Eulerian-spanning set and a coboundary operator. With them, the conversion works for general graphs with weights that are zero or more. The pair of tools opens new paths to maxcut algorithms past the planar class. As one gain, they give a fixed-parameter tractable algorithm for k-contraction apex graphs. For graphs with crossing number k, their method matches the best known run time for this weight range.
Catalog record
| CREATOR | Qiming Fang, Sihong Shao, Yuxuan Wu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00725
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Eulerian-spanning set and coboundary operator: An investigation of maxcut beyond planar graphs Qiming Fang, Sihong Shao, Yuxuan Wu Abstract 2 2 footnotetext: CAPT, LMAM and School of Mathematical Sciences, Peking University, Beijing 100871, China. Email: [email protected] Abstract : Using the concepts of Eulerian-spanning set and coboundary operator, we generalize Hadlock’s conversion of the maxcut problem on planar graphs to one on general graphs with non-negative weights. Using our conversion, we can explore algorithms for maxcut beyond the class of planar graphs. We obtain a Fixed-Parameter Tractable algorithm for k -contraction apex graphs. Specifically, our algorithm can be applied to graphs with crossing number k , giving an O(2^{k}(n+k)^{3/2}\log(n+k)) -time algorithm that matches the best known results when restricted to non-negative weights. Keywords: maxcut, planar graphs, Eulerian-spanning set, coboundary operator, Fixed-Parameter Tractable algorithm. 1 Introduction The famous maxcut problem asks for a partition of vertices of a given graph into two sets such that the number of edges that cross between two parts attains maximum. It is an NP-complete problem [ 11 ] , thus being unlikely to be solved efficiently in general. However, a major breakthrough by Hadlock [ 10 ] showed that the maximum cut can be found in polynomial time on planar graphs. He showed that finding the maximum cut in a planar graph is equivalent to finding a minimum odd-circuit cover, which is further equivalent to finding a minimum odd-vertex pairing in the dual graph. While the problem of minimum odd-vertex pairing can be converted to a minimum matching problem, which can be solved using Edmonds’ Blossom Algorithm [ 5 ] , he concluded that we can find the maximum cut in a planar graph within polynomial time. In this paper, we start with Hadlock’s conversion, and generalize it beyond the setting of planar graphs. The second step of Hadlock’s conversion relies heavily on planar duality, whose generalization to general graphs remains to be established. With regard to this, we take a step back and see what happens. We noticed that on planar graphs, an odd-vertex pairing in the dual graph corresponds to an edge set in the original graph satisfying the following coboundary condition: its coboundary (over the field \mathbb{Z}_{2} ) is the set of odd faces. Therefore, a minimum odd-circuit cover is simply a minimum edge set satisfying the coboundary condition. But this coboundary condition can be generalized to the setting of general graphs by replacing the concept of face with our concept of Eulerian-spanning set . This idea rises from the fact that the boundaries of faces in a planar graph span its cycle space, i.e. the space of Eulerian subgraphs. Therefore we generalize Hadlock’s conversion on planar graphs to one that applies to maxcut on general graphs. Moreover, when restricted to planar graphs, our conversion is almost identical to Hadlock’s (c.f. Section 2 ). Figure 1 illustrates our generalization, and conversion of the maxcut problem. Our contribution. By noticing the coboundary condition on planar graphs, and generalizing it with the concept of Eulerian-spanning set, we obtain a conversion of maxcut on general graphs with non-negative weights. Using our conversion, the maxcut problem is eventually converted to a weighted set symmetric difference problem (WSSD) , which is polynomial-time solvable under specific conditions. We obtain a fixed-parameter algorithm that solves maxcut on graphs with a Eulerian-spanning set satisfying a k -frequent appearance condition , which is equivalent to the graph being a k -contraction apex graph (the concept of k -contraction apex graphs is a generalization of the concept of contraction apex graphs in [ 14 ] , c.f. Definition 1.1 ). This result can be modified to cover the case of graphs with crossing number k . Figure 1 : A comparison between Hadlock’s conversion [ 10 ] and ours. The star mark means that this step relies on planar duality, which is yet to be generalized to general graphs. We use bold font to emphasize what we notice, our generalization and our conversion. Definition 1.1 . An undirected graph G=(V,E) is a k -contraction apex graph, if we can contract at most k edges in G and get a planar graph. Throughout this paper, we will use P_{k}(G) to denote an edge set of cardinality at most k such that after contracting P_{k}(G) , G becomes a planar graph. In this work, we give an algorithm for maxcut parameterized by the number k , which comes down to the following main theorem. Theorem 1.2 . Suppose G=(V,E) is an undirected, simple, k -contraction apex graph, w:E\to\mathbb{R}^{+}\cup\{0\} is a weight function, and P_{k}(G) is included in the input. Let n=|V|,m=|E| Then there is an O(2^{k}\max\{m,n\}^{3/2}\log\max\{m,n\}) -time algorithm finding the maximum weighted cut of G . It is easy to see that planar graphs are simply the case of k=0 in Theorem 1.2 . Moreover, in Section 7 , we will show that an immediate corollary (Corollary 6.8 ) of this theorem covers the case of graphs with crossing number k , giving an O(2^{k}(n+k)^{3/2}\log(n+k)) -time algorithm (c.f. Theorem 7.5 ), which matches the results of [ 12 , 4 ] restricted to the setting of non-negative weights. We note that our algorithm is essentially different from those in [ 12 , 4 ] , which directly branch the original maxcut problem to multiple maxcut problems. Related work. Polynomial-time algorithms for max-cut have also been found in other classes of graphs, such as graphs not contractible to K_{5} [ 1 ] , graphs without long odd cycles [ 7 ] , graphs of bounded treewidth [ 2 ] , line graphs [ 9 ] , and weakly bipartite graphs [ 8 ] . Organization of this paper. In Section 2 , we illustrate the application of our conversion to planar graphs as a rough sketch of the main ideas. In Section 3 we give the formal definition of Eulerian-spanning set and coboundary operators. In Section 4 we describe the detailed conversion from the weighted maximum cut problem to a WSSD problem. In Section 5 we describe how to solve WSSD under the condition |S_{i}|\leq 2,\forall S\in\mathcal{S} . In Section 6 we prove Theorem 1.2 by finding a Eulerian-spanning set for k -contraction apex graphs, and utilizing the planarity. In Section 7 we prove that the immediate corollary of Theorem 1.2 (c.f. Corollary 6.8 ) covers the case of graphs with crossing number k . Basic assumptions. All graphs considered in this paper are finite and undirected, but are allowed to have multiple edges and self-loops unless otherwise specified. When we talk about a planar graph, we will always assume that its planar embedding is arbitrarily fixed unless otherwise specified. Throughout this paper, copies of the same instance in a multiset are considered to be different. 2 Our conversion on planar graphs In this section we briefly illustrate our conversion on planar graphs. The purpose is to prepare the reader for understanding our conversion on general graphs. We consider unweighted maximum cut on simple planar graphs for simplicity. We set up some definitions and notations first. Definition 2.1 . Suppose S is a finite multiset. Then \mathbb{Z}_{2}^{S} is the linear space over \mathbb{Z}_{2} (the field with two elements) with dimension |S| . Moreover, every element in