betaFeedback

WorksMathematics

Odd faces as a parameter for maximum independent set in embedded graphs

Abstract

We give a polynomial-time algorithm for finding a maximum weight independent set in a graph embedded in a surface of bounded genus and with a bounded number of vertex-disjoint odd faces. In particular, we obtain an algorithm for graphs with an even-faced embedding in a torus and for planar graphs with a bounded number of odd faces, answering a question of Thomassé (2018) and a question of Choi, Gorsky, Kim, McFarland, and Wiederrecht (2025) respectively. We reduce the original problem to finding a minimum cost non-negative integer circulation with homology constraints in the dual of a certain double cover of the original graph.

Introduction

Contribution

The Maximum Weighted Independent Set problem (MIS) takes as input a graph GG and a weighting w:V(G)→Q≥0w : V(G) \to\mathbb{Q}_{\ge0} and asks for an independent set of maximum weight. MIS is well known to be NP-hard in general, and remains NP-hard even in planar graphs of maximum degree 3 and arbitrarily large girth [22, 59]. Due to the problem’s hardness in general, there has been a long line of work on determining for which graph classes MIS admits a polynomial time algorithm (see Subsection 1.2). A classical example of such a graph class is bipartite graphs, and hence it is natural to ask whether MIS remains tractable on graphs which are “close” to being bipartite. One measure of how close a graph is to being bipartite is the odd cycle packing number of a graph, which measures the number of pairwise vertex disjoint odd cycles. Recently, Fiorini, Joret, Weltge, and Yuditsky [21] showed that MIS admits a polynomial time algorithm on graphs of odd cycle packing number at most kk for every constant kk. Their algorithm is fundamentally based on the work of Conforti, Fiorini, Huynh, Joret, and Weltge [13] on graphs with bounded genus and odd cycle packing number. Our main result extends the result of Conforti et al. to graphs that embed in a surface of bounded genus with a bounded number of vertex disjoint odd faces.

Theorem 1.1. Let g,k∈Z≥0g, k \in\mathbb{Z}_{\ge0} be fixed. There exists a polynomial time algorithm that, given a graph GG together with a cellular embedding in a surface of Euler genus gg with at most kk vertex-disjoint odd faces and vertex weights w:V(G)→Q≥0w : V(G) \to\mathbb{Q}_{\ge0}, finds a maximum weight independent set in GG in time nf(g+k)n^{f(g+k)} for some computable function ff.

In particular, Theorem 1.1 gives a polynomial time algorithm for MIS in a graph with an even-faced embedding in a torus, asked first by Thomassé [65 Problem 8] for the toroidal grid and more generally by Choi, Gorsky, Kim, McFarland, and Wiederrecht [9] for an even-faced embedding.

We also obtain the following as a corollary, answering a question of Choi et al. [9].

Corollary 1.2. Let k∈Z≥0k \in\mathbb{Z}_{\ge0} be fixed. There exists a polynomial time algorithm that, given a planar graph GG with at most kk odd faces, finds a maximum weight independent set in GG.

Before our work, the only cases that were known to be polynomially solvable were k=0k=0 (bipartite graphs) and k=2k=2 (by a result of Gerards [27]); note the number of odd faces must be even. We provide a more detailed comparison to Gerards’ result in Subsection 1.2. We note that planar graphs with two odd faces already have unbounded odd cycle packing number, as do graphs with an even-faced embedding in the torus. Hence our algorithm extends to graphs which are far from bipartite by previous metrics, yet for which the odd cycles have some topological structure. These types of topological constraints on odd cycles arise naturally in the study of odd-minors, and we believe that our results are central to solving MIS in graphs with a forbidden planar odd-minor. We discuss this motivation in more detail below.

We also note that Theorem 1.1 immediately implies the main result of Conforti et al. [13], and because our result only relies on an Erdős-Posá property for odd faces (see Subsection 4.1) instead of two-sided odd cycles, our analysis is much simpler.

By applying the reduction given in [21], § 3 (see also [8], Theorem 10.3), we obtain the following corollary to integer programming. A matrix A∈{−1,0,1}m×nA \in\{-1,0,1\}^{m \times n} with two nonzero entries per row is the edge-vertex incidence matrix of a signed graph (G,γ)(G,\gamma) if AA is supported on the incidence matrix of GG and an edge is odd if and only if the two entries in the corresponding row have the same sign. See Subsection 3.2 for definitions related to signed graphs. We note that the reduction given in [8], Theorem 10.3 applies to classes of signed graphs closed under subgraphs and parity-preserving subdivisions. The class of graphs with a cellular embedding in a surface of Euler genus gg with at most kk vertex-disjoint odd faces is closed under parity-preserving subdivisions, but it is not closed under subgraphs because the embedding must be cellular. One can get around this by setting the weights of vertices to zero instead of deleting them.

Corollary 1.3. Let g,k∈Z≥0g,k \in\mathbb{Z}_{\ge0} be fixed. There exists a polynomial time algorithm to solve the integer program

max⁡{wTx:Ax≤b,x∈[ℓ,u]∩Zn}\max\{w^{T}x : Ax \le b, x \in[\ell,u] \cap\mathbb{Z}^{n}\}

when A∈{−1,0,1}m×nA \in\{-1,0,1\}^{m \times n} is the edge-vertex incidence matrix of a signed graph with a given cellular embedding in a surface of Euler genus gg with at most kk vertex-disjoint odd faces, ℓ,u,w∈Zn\ell,u,w \in\mathbb{Z}^{n} and b∈Zmb \in\mathbb{Z}^{m}.

Our results are motivated by the study of odd-minors. A graph HH is an odd-minor of a graph GG if HH can be obtained from GG by deleting vertices, deleting edges, and contracting edge cuts (see Subsection 3.2 for an equivalent definition). Because every cycle shares an even number of edges with every cut, every cycle in HH corresponds naturally to a cycle in GG of the same parity. For example, K3K_{3}-odd-minor-free graphs are exactly bipartite graphs. Odd-minor-free graphs seek to generalize both minor-free graphs and bipartite graphs. They were originally introduced in the context of coloring [39, 23, 66, 45], but have since found applications to algorithmic problems which become tractable on bipartite graphs. To put our results in this context, we note that the class of graphs which embed on a fixed surface with at most kk vertex-disjoint odd faces is an odd-minor closed class, see Lemma 3.2.

For minor-closed classes, an exact algorithmic threshold for MIS is known (we will assume throughout our discussion that P≠NP\mathrm{P} \ne\mathrm{NP}). It is implied by the well-known Grid Theorem of Robertson and Seymour [63] that MIS admits a polynomial-time algorithm on a minor-closed class of graphs if and only if the class forbids a planar graph. Such classes have bounded treewidth, so the structure of such classes is relatively simple and well understood. Choi et al. [9] ask for an analogous algorithmic threshold for odd-minor closed classes, which we conjecture to again be characterized by planar graphs.

Conjecture 1.4. Let C\mathcal{C} be an odd-minor closed class of graphs. Then Maximum Weighted Independent Set admits a polynomial-time algorithm on C\mathcal{C} if and only if C\mathcal{C} excludes a planar graph.

Unlike graphs with a forbidden planar minor, graphs with forbidden planar odd-minor have a richer and less understood structure, see for instance [9]. We expect graphs with an embedding on a surface of bounded genus with a bounded number of odd faces to play an important role in the structure of such graphs, analogous to the role bounded genus graphs play in the structure of KtK_t-minor-free graphs. To see why this should be the case, we note that graphs with an embedding on a surface of bounded genus with a bounded number of odd faces give high-treewidth examples of graphs forbidding a planar odd-minor. Therefore such graphs do not decompose into simpler graphs via standard graph-minors machinery. Previous work also points to the importance of embedded graphs with few odd faces, see for instance [27, 21, 9].

We now discuss related work on the Maximum Weighted Independent Set (MIS) problem with a particular focus on odd-minor-closed graph classes. Recall that the odd cycle packing number (OCP) of a graph GG is the maximum number of pairwise vertex-disjoint odd cycles, and the odd cycle transversal number (OCT) of a graph is the size of the smallest set of vertices whose deletion leaves the graph bipartite. Clearly a graph has OCP less than kk if and only if it forbids k⋅K3k \cdot K_3 as an odd-minor. Reed [61] showed that a graph has bounded OCT if and only if it forbids k⋅K3k \cdot K_3 and the Escher wall of order kk as an odd-minor. Clearly MIS admits a polynomial time algorithm on graphs of bounded OCT by guessing a hitting set for the odd cycles, but in fact this can be made fixed-parameter tractable by a result of Reed, Smith, and Vetta [60].

The problem of MIS on graphs of bounded OCP was motivated by a famous conjecture in integer programming. It is conjectured that any integer program whose coefficient matrix has all subdeterminants bounded by Δ\Delta in absolute value admits a polynomial-time algorithm when Δ\Delta is constant [64]. An important special case of this conjecture is the edge formulation of MIS as an integer program, and in this case the conjecture would imply that graphs of bounded OCP admit a polynomial-time algorithm for MIS. The case of OCP equal to 0 is the case of bipartite graphs, while the case of OCP equal to 1 was first solved by Artmann, Weismantel, and Zenklusen [1], who showed more generally that any integer program whose coefficient matrix has all subdeterminants bounded by 2 in absolute value can be solved in polynomial time. Conforti, Fiorini, Huynh, Joret, and Weltge [13] showed that MIS is tractable on graphs with bounded genus and bounded OCP. After applying an Erdős-Posá type result, the crucial step of their algorithm is solving MIS for graphs with an even-faced embedding on a surface of bounded genus such that the odd cycles are exactly the 1-sided cycles. This is a natural topological structure for odd cycles dating back to Reed’s work on the Escher wall [61]. In our work, we apply a simpler Erdős-Posá type result to reduce to MIS on graphs with an even-faced embedding on a surface of bounded genus, but now with no further restriction on the odd cycles. Fiorini, Joret, Weltge, and Yuditsky [21] extended the work of Conforti et al. [13] to solve MIS on all graphs of bounded OCP. They did so by showing that graphs of bounded OCP “almost embed” on a surface of bounded genus such that odd cycles are exactly the 1-sided cycles.

A different approach to solving MIS in odd-minor-free classes has been the use of width parameters, which largely seek to generalize that MIS admits a polynomial time algorithm on bipartite graphs and graphs of bounded treewidth. Let B\mathcal{B} denote the class of bipartite graphs. Examples of such parameters are elimination distance to B\mathcal{B} [5, 6] and B\mathcal{B}-treewidth [17, 37, 38], which are the minimum kk such that a graph GG has a set X⊆V(G)X \subseteq V(G) with G−X∈BG-X \in\mathcal{B} and with the torso of XX in GG having treedepth (in the case of elimination distance to B\mathcal{B}) or treewidth (in the case of B\mathcal{B}-treewidth) at most kk. Another example is B\mathcal{B}-blind-treewidth [29], which measures the largest treewidth over all non-bipartite blocks of GG. Jaffke, Morelle, Sau, and Thilikos [36] introduced bipartite treewidth, which gives a proper generalization of both B\mathcal{B}-blind-treewidth and B\mathcal{B}-treewidth. A graph has bipartite treewidth at most kk if it admits a tree decomposition such that every bag has OCT at most kk and the intersection of a bag with its neighbors has size at most 1 after deleting this hitting set. Finally, Choi, Gorsky, Kim, McFarland, and Wiederrecht [9] introduced the notion of OCP-treewidth, which generalizes both bipartite treewidth and graphs of bounded OCP. A graph has OCP-treewidth at most kk if it admits a tree decomposition such that all adhesions have size at most kk and all bags have OCP at most kk, together with a further restriction that does not allow odd cycles to cross between bags outside a small hitting set. The definition of OCP-treewidth does not require adhesions to have size 1 outside a hitting set as in the definition of bipartite treewidth, but there is a notion of a tame decomposition that has such a constraint, which turns out to be useful both structurally and algorithmically. Choi et al. also give a forbidden odd-minor characterization of classes that have bounded OCP-treewidth. They show that an odd-minor closed class has bounded OCP treewidth if and only if it excludes a planar graph with two odd faces and excludes a planar graph with all odd faces sharing a vertex with the outer face.

Separate from the approaches mentioned thus far is the result of Gerards [26], who proved that MIS admits a polynomial time algorithm on graphs with no K4K_4 odd-minor. This implies that MIS is tractable on planar graphs with 2 odd faces. In fact, planar graphs with 2 odd faces are the key class in his theorem, as Gerards proves in his thesis [27] that graphs with no K4K_4 odd-minor decompose into parts which are either planar with 2 odd faces, have OCT at most 1, or are equal to a single fixed graph. As previously noted, planar graphs with 2 odd faces can have unbounded OCP, and even unbounded OCP-treewidth. Since 1989 when Gerards’ published his result, there have been no generalizations even to planar graphs with 4 odd faces (recall that the number of odd faces must be even). We generalize his result to planar graphs with any constant number of odd faces, and perhaps just as importantly, we give an independent proof of his result using techniques developed by Conforti et al. [13] which more easily allow for generalizations to odd-minor-free classes as in [21]. On the surface Gerards’ approach is similar to that of Conforti et al.; he finds a special orientation of the graph and uses this orientation to set up a minimum cost circulation. However, Gerards’ algorithm is a “dual” algorithm in the sense that it computes the maximum weight of an independent set and then uses this to obtain an optimal independent set. In comparison, our algorithm qualifies more as a “primal” algorithm; we find the optimal independent set directly.

Our approach gives some hints as to why Gerards’ result [26] was not extended to planar graphs with more odd faces before. One way to use our approach to solve MIS in planar graphs with two odd faces is to compute an minimum cost (s,t)(s,t)-path in the dual of the bipartite double cover (see § 5) which in this case will be planar. Hence the minimum cost flow problem will not have any extra topological constraints. However in the case of four or more odd faces, the bipartite double cover will embed on a surface of higher genus, and topological constraints on the flow problem become necessary.

While MIS is NP-hard on any odd-minor closed class containing all planar graphs, Tazari [67] showed that MIS admits a polynomial time approximation scheme on HH-odd-minor-free graph classes for every graph HH. This is in stark contrast to the general case, where it is NP-hard to approximate the maximum size of an independent set to within a factor of n1−εn^{1-\varepsilon} for every ε>0\varepsilon> 0 [32, 41].

The MIS problem has also been studied in graph classes which are closed under induced subgraphs [31, 51, 47, 11, 10], induced minors [68, 14, 15, 12, 3, 42], and vertex minors [58, 25]. Dallard, Milanič, and Štorgel asked whether Conjecture 1.4 holds when “odd-minor closed” is replaced by “induced minor closed” [15]. This was recently disproven by Bonnet and Chang [2]. Korhonen [42] showed that MIS admits a subexponential time algorithm on the class of HH-induced-minor-free graphs for every planar graph HH. For vertex-minors on the other hand, Geelen [48] conjectured that MIS admits a polynomial-time algorithm on every proper vertex-minor closed class.

Graphs admitting an even-faced embedding have previously been studied in the context of vertex coloring [16, 44, 34] and face coloring [54, 33, 43, 4], in the context of complete odd-minors [20], and in the context of ribbon graphs [49, 50].

Extensions

There is still much to be learned about even-faced embeddings of graphs. For instance, can one recognize when a graph has an even-faced embedding in a surface of small genus?

Conjecture 1.5. For each g≥0g \ge0, there exists an algorithm running in time f(g)nO(1)f(g)n^{O(1)} for some computable function ff which takes as input a graph GG and either returns an even-faced embedding in a surface of genus gg or correctly identifies that no such embedding exists.

If so, this would give an “even-faced” analogue of a classic result of Mohar [53] (see also [40]), and would allow us to drop the condition that the embedding of GG is given as input in Theorem 1.1. Even a runtime of the form nf(g)n^{f(g)} would be interesting. We note that the signed graph minor relation, and hence the odd-minor relation, is expected to be a well-quasi-order; this was announced by Geelen, Gerards, and Whittle [24] as part of their Matroid Minors Project. It is also expected that one can test for a fixed odd-minor in fixed-parameter tractable time; this should follow from machinery developed by Huynh [35] and Liu and Yoo [46]. In particular, Huynh [35] gives an XP algorithm in his thesis. Together, this would imply a nonconstructive algorithm for the decision version of the problem.

We conjecture that our algorithm can be made fixed-parameter tractable (FPT). By Subsection 4.1, it suffices to give an algorithm for even-face embedded graphs.

Conjecture 1.6. Let g∈Z≥0g \in\mathbb{Z}_{\ge0} be fixed. There exists an algorithm that, given a graph GG together with a cellular even-face embedding in a surface of Euler genus gg and vertex weights w:V(G)→Q≥0w : V(G) \to\mathbb{Q}_{\ge0}, finds a maximum weight independent set in GG in time f(g)nO(1)f(g)n^{O(1)} for some computable function ff.

Following this paper’s acceptance to SODA 2027, Barish [62] claimed a proof of the above conjecture in a Lean repository without an accompanying writeup. Because the case when the odd cycles are exactly the 1-sided cycles reduces to finding a minimum cost flow in a particular homology class, we expect that any answer to the above would also solve the following, which asks for an FPT algorithm to the problem considered in [56].

Conjecture 1.7. Let g∈Z≥0g \in\mathbb{Z}_{\ge0} be fixed. There exists an algorithm that, given a directed graph DD together with a cellular embedding in a surface of Euler genus gg, edge costs c:E(G)→Q≥0c : E(G) \to\mathbb{Q}_{\ge0}, and an integer circulation xx on DD, finds a minimum cost integer circulation homologous to xx in time f(g)nO(1)f(g)n^{O(1)} for some computable function ff.

Algorithm overview

We first provide an overview of our algorithm. We will assume familiarity with surfaces and graph embeddings in this section, see Subsection 3.3 for relevant background. In particular, we assume that the graph comes together with an embedding scheme (π,λ)(\pi,\lambda). Recall that we consider the following problem.

Problem 2.1. Given a graph GG with a cellular embedding in a surface of Euler genus gg with at most kk vertex-disjoint odd faces and vertex weights w:V(G)→Q≥0w:V(G)\to\mathbb{Q}_{\geq0}, compute a maximum ww-weight independent set in GG.

We first reduce to the case when GG has an even-faced embedding in a surface of slightly higher genus in Subsection 4.1. Using results from [28], we show that we may delete at most O(k2g)O(k^2g) vertices to reduce to the case when GG has a constant number of odd faces. Then we may add a handle between odd faces to increase the genus while removing odd faces. We must do these operations while preserving that the graph has a cellular embedding, so instead of deleting vertices we introduce a small gadget with the same effect, see Subsection 4.1 for details. Hence we reduce to the following problem.

Problem 2.2. Given a graph GG with a cellular even-faced embedding in a surface of Euler genus gg and vertex weights w:V(G)→Q≥0w:V(G)\to\mathbb{Q}_{\geq0}, compute a maximum ww-weight independent set in GG.

In Subsection 4.2 we apply some preprocessing to reduce to a more structured instance. We summarize the desired properties below. (The notation δ(v)\delta(v) is defined in Subsection 3.1 below, together with other preliminaries.)

Definition 2.3. Let GG be a graph. A vertex weighting w:V(G)→Q≥0w:V(G)\to\mathbb{Q}_{\geq0} is called edge-induced if there is a nonnegative edge weighting c:E(G)→Q≥0c:E(G)\to\mathbb{Q}_{\geq0} such that w(v)=∑e∈δ(v)c(e)w(v)=\sum_{e\in\delta(v)}c(e) for every vertex v∈V(G)v\in V(G).

Definition 2.4. A weighted graph (G,w)(G,w) is said to satisfy the standard assumptions if GG is 2-connected, non-bipartite, and even-faced embedded in a surface of Euler genus gg with facewidth at least 2, and the weighting ww is edge-induced.

Because our weights are edge-induced by c:E(G)→Q≥0c:E(G)\to\mathbb{Q}_{\geq0}, which we think of as the cost of an edge, it now suffices to find a minimum cost set of edges which are given by the uncovered edges of some independent set. We call such edges slack. We note already that edge-induced weights intrinsically encode that the problem is easy for bipartite graphs, as for bipartite graphs choosing one side of the bipartition will have maximum total weight.

In Subsection 4.3 we recall the results of Conforti et al. [13] to precisely describe which sets of edges appear as slack edges in an independent set. That is, if A∈{0,1}E(G)×V(G)A\in\{0,1\}^{E(G)\times V(G)} is the edge-vertex incidence matrix of GG, then y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} is called a slack vector if there exists x∈ZV(G)x\in\mathbb{Z}^{V(G)} such that Ax+y=1Ax+y=\mathbf{1}. For C=(v0,e1,v1,e2,v2,…,vk−1,ek,v0)C=(v_0,e_1,v_1,e_2,v_2,\ldots,v_{k-1},e_k,v_0) a closed walk in GG and y∈ZE(G)y\in\mathbb{Z}^{E(G)}, we define

ωC(y):=∑i=1k(−1)i−1y(ei).\omega_C(y):=\sum_{i=1}^{k}(-1)^{i-1}y(e_i).

Conforti et al. showed that y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} is a slack vector if and only if ωC(y)=0\omega_C(y)=0 for all even closed walks and ωC(y)≡1(mod2)\omega_C(y)\equiv1\pmod{2} for all odd closed walks. We show that when GG is 2-connected and non-bipartite, there is a collection of ∣E(G)∣−∣V(G)∣+1|E(G)|-|V(G)|+1 cycles whose constraints imply the above constraints for every closed walk, and hence we reduce to the below problem.

Problem 2.5. Given a graph GG satisfying the standard assumptions, non-negative edge costs c:E(G)→Q≥0c:E(G)\to\mathbb{Q}_{\geq0}, and a collection C\mathcal{C} of ∣E(G)∣−∣V(G)∣+1|E(G)|-|V(G)|+1 cycles with exactly one of them odd, minimize c(y)=∑e∈E(G)c(e)y(e)c(y)=\sum_{e\in E(G)}c(e)y(e) over all y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} satisfying ωC(y)=0\omega_C(y)=0 for every even cycle C∈CC\in\mathcal{C} and ωC(y)≡1(mod2)\omega_C(y)\equiv1\pmod{2} for the unique odd cycle C∈CC\in\mathcal{C}. Furthermore, C\mathcal{C} is such that the above constraints exactly characterize the slack vectors y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)}.

In the work of Conforti et al. [13], the authors then find a special orientation of the dual graph such that the solution y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} can be interpreted as a circulation in this orientation. This has the advantage that the constraint ωC(y)=0\omega_C(y)=0 for facial cycles of GG is implied by flow conservation in this dual graph. The type of orientation needed is an alternating orientation. An orientation of an embedded graph G∗G^* is called alternating if for each vertex v∈V(G∗)v\in V(G^*), edges alternately leave and enter vv in the local cyclic order of edges incident to vv. Finding such an alternating orientation of G∗G^* is only possible in the setting of [13] (see Lemma 3.3).

To get around this problem, we consider the derived graph G^\widehat{G} of GG (for a particular signing of GG), see § 5. The derived graph G^\widehat{G} is constructed as follows. The graph GG is equipped with an embedding scheme (π,λ)(\pi,\lambda), where π\pi gives the local cyclic orientation around each vertex and λ:E(G)→Z2\lambda:E(G)\to\mathbb{Z}_2 encodes whether an edge is “twisted”, see Subsection 3.3. The vertex set of G^\widehat{G} consist of two copies of V(G)V(G), and we denote for each vertex v∈V(G)v\in V(G) its two copies by v0v_0, v1v_1. For each edge uv∈E(G)uv \in E(G) with λ(uv)=0\lambda(uv)=0, one adds two edges in E(G~)E(\widetilde{G}) between opposite copies of uu and vv, that is, one adds the edges u0v1u_0v_1 and u1v0u_1v_0. For each edge uv∈E(G)uv \in E(G) with λ(uv)=1\lambda(uv)=1, one adds two edges in E(G~)E(\widetilde{G}) between the same copies of uu and vv, that is, one adds the edges u0v0u_0v_0 and u1v1u_1v_1. It turns out that G~\widetilde{G} embeds in a surface of genus 2g−22g-2, and that its dual G~∗\widetilde{G}^{*} has an alternating orientation. We defer the reader to § 5 for a topological construction of G~\widetilde{G}.

We now have an alternating orientation D∗D^{*} of G~∗\widetilde{G}^{*}. We map circulations f∈Z≥0E(D∗)f \in\mathbb{Z}_{\geq0}^{E(D^{*})} to vectors y∈Z≥0E(G)y \in\mathbb{Z}_{\geq0}^{E(G)} via the natural projection ρ:ZE(D∗)→ZE(G)\rho:\mathbb{Z}^{E(D^{*})}\to\mathbb{Z}^{E(G)} where y=ρ(f)y=\rho(f) is given by y(e)=f(e⃗0)+f(e⃗1)y(e)=f(\vec{e}_0)+f(\vec{e}_1) for e0,e1∈E(G~)e_0,e_1\in E(\widetilde{G}) the copies of e∈E(G)e\in E(G). Now flow conservation at each vertex in D∗D^{*} implies ωC(y)=0\omega_C(y)=0 for every facial cycle CC. By Euler’s formula, it suffices to add at most gg extra constraints ωC1(ρ(f))≡1(mod2)\omega_{C_1}(\rho(f))\equiv1\pmod2 for odd cycle C1C_1 and ωCi(ρ(f))=0\omega_{C_i}(\rho(f))=0 for even cycles C2,…,CgC_2,\ldots,C_g. Somewhat surprisingly, we show that an optimal solution y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} to Problem 2.5 can be found as the image of a minimum cost circulation ff in D∗D^{*} satisfying the above constraints, and hence we reduce to the following problem in Theorem 6.3.

Problem 2.6. Let D∗D^{*} be an alternating orientation of G~∗\widetilde{G}^{*} for GG satisfying the standard assumptions, and let C1,…,CgC_1,\ldots,C_g be cycles in GG where C1C_1 is odd and C2,…,CgC_2,\ldots,C_g are even. Find a minimum cc-cost nonnegative integer circulation ff in D∗D^{*} satisfying the linear constraints

  1. ωCi(ρ(f))=0\omega_{C_i}(\rho(f))=0 for every even cycle C2,…,CgC_2,\ldots,C_g, and

  1. ωC1(ρ(f))≡1(mod2)\omega_{C_1}(\rho(f))\equiv1\pmod2.

Finally, in § 7, we show that the constraints on the circulation ff in D∗D^{*} only depend on the Z\mathbb{Z}-homology of ff (see Subsection 3.4 for related definitions). This implies that we can solve Problem 2.6 in polynomial time by using the work of Chambers, Erickson, and Nayyeri [7] for the orientable case and Morell, Seidel, and Weltge [56] for the nonorientable case.

Preliminaries

Definitions

All graphs will be simple unless otherwise stated. We use standard graph theory notation. In particular, we use V(G)V(G) and E(G)E(G) to denote the vertex and edge set of a graph respectively, and we use δ(v)\delta(v) to denote the set of edges incident to v∈V(G)v\in V(G). We will often identify a function x:A→Bx:A\to B with a vector x∈BAx\in B^A, and for instance use the notation x(a)x(a) to denote the aa-th entry of x∈BAx\in B^A. We use the notation [k]:={1,2,…,k}[k]:=\{1,2,\ldots,k\}.

In Subsection 4.1 we will need the following definition.

Definition 3.1. A tree-decomposition of a graph GG is a pair (T,β)(T,\beta) where TT is a tree and β:V(T)→2V(G)\beta:V(T)\to2^{V(G)} is such that

  1. for every edge e∈E(G)e\in E(G), there exists t∈V(T)t\in V(T) such that both ends of ee are contained in β(t)\beta(t), and

  1. for every v∈V(G)v\in V(G), the set β−1(v)\beta^{-1}(v) induces a connected, non-empty subtree of TT.

The width of a tree decomposition is max⁡t∈V(T)∣β(t)∣−1\max_{t\in V(T)}|\beta(t)|-1. The treewidth of a graph GG is the minimum width over all tree decompositions of GG. We call β(t)\beta(t) the bag of tt.

Signed graphs

To understand our algorithm it will be most convenient to work with signed graphs. A signed graph is a pair (G,γ)(G,\gamma) where GG is a graph and γ:E(G)→Z2\gamma:E(G)\to\mathbb{Z}_2 assigns a parity to every edge. The parity of a cycle C=v1v2…vkv1C=v_1v_2\ldots v_kv_1 in (G,γ)(G,\gamma) is given by ∑i=1kγ(vivi+1)\sum_{i=1}^{k}\gamma(v_iv_{i+1}) where indices are taken modulo kk, and the sum is computed in Z2\mathbb{Z}_2. In the context of this paper we typically associate an unsigned graph GG with the signed graph (G,1)(G,\mathbf{1}) where 1:E(G)→Z2\mathbf{1}:E(G)\to\mathbb{Z}_2 maps every edge to 11.

A signed graph (G,γ′)(G,\gamma') is obtained from (G,γ)(G,\gamma) by shifting at v∈V(G)v\in V(G) if γ′(e)=γ(e)\gamma'(e)=\gamma(e) for all e∈E(G)∖δ(v)e\in E(G)\setminus\delta(v) and γ′(e)=γ(e)+1\gamma'(e)=\gamma(e)+1 for all e∈δ(v)e\in\delta(v). More generally, (G,γ′)(G,\gamma') is obtained from (G,γ)(G,\gamma) by shifting if (G,γ′)(G,\gamma') is obtained from (G,γ)(G,\gamma) by a sequence of shiftings at vertices. It is well known that two signed graphs have the same collection of odd cycles if and only if one is obtained from the other by shifting.

A signed graph (G,γG)(G,\gamma_G) contains another signed graph (H,γH)(H,\gamma_H) as a minor if (H,γH)(H,\gamma_H) can be obtained from (G,γ)(G,\gamma) by shifting, deleting vertices, deleting edges, and contracting even edges. We note that we disallow the contraction of odd-loops; this is sometimes called a link minor in the associated matroid. We can use this to give an equivalent definition of odd-minors: GG contains HH as an odd-minor if and only if the signed graph (G,1)(G,\mathbf{1}) contains the signed graph (H,1)(H,\mathbf{1}) as a minor.

In the below, the parity of a face in a signed graph (G,γ)(G,\gamma) is the sum of γ(e)\gamma(e) over all edges ee on its boundary, where edges that appear twice along the boundary are counted twice. The parity of a face in an unsigned graph GG is the parity of the face in (G,1)(G,1).

Lemma 3.2. Let CC denote the class of graphs that admit an embedding in a surface Σ\Sigma with at most kk vertex-disjoint odd faces. Then CC is odd-minor-closed.

Proof. This follows from the more general fact that the class C′C' of signed graphs with an embedding in Σ\Sigma with at most kk vertex-disjoint odd faces is minor-closed. Indeed, G∈CG \in C if and only if (G,1)∈C′(G,1) \in C'. Then for any odd-minor HH of GG, (H,1)(H,1) is a minor of (G,1)(G,1), and hence (H,1)(H,1) is in C′C'.

We then simply note the following properties. Clearly shifting, deleting edges, deleting vertices, and contracting even edges leaves the signed graph embeddable in Σ\Sigma, so we argue that the number of vertex-disjoint odd faces does not increase. Shifting at a vertex does not change the parity of any face. Deleting an edge either doesn’t change the parity of any face (if that edge appears twice on the boundary of some face), or it merges two faces such that the new face has parity equal to the sum of the previous faces. It suffices to only ever delete isolated vertices, and clearly this does not change the parity of a face. Finally, contracting an even edge is either the same as deleting an edge (if the edge is a loop) or does not affect the parity of any incident faces.

We note some subtlety here. The class of graphs with a cellular embedding in a surface with a bounded number of (vertex-disjoint) odd faces is not odd-minor closed. Deleting vertices and edges may cause the embedding to be non-cellular.

Surfaces and graph embeddings

In this subsection we review the basics of surfaces and combinatorial graph embeddings. We refer the reader to Mohar and Thomassen’s book [55] for further background.

Throughout the paper a surface Σ\Sigma is a compact 2-dimensional manifold without boundary. We let Σ(h,c)\Sigma(h,c) be the surface obtained by cutting 2h+c2h+c disjoint open disk from the sphere and gluing hh handles and cc crosscaps to the boundaries of these disks. By the classification theorem for surfaces, every surface is homeomorphic to Σ(h,c)\Sigma(h,c) for some hh and cc. If c=0c=0 the surface is said to be orientable, otherwise the surface is said to be non-orientable. The Euler genus of a surface Σ≅Σ(h,c)\Sigma\cong\Sigma(h,c) is 2h+c2h+c.

A simple closed curve in Σ\Sigma is said to be 1-sided if it has a neighborhood that is homeomorphic to a Möbius strip, and 2-sided if it has a neighborhood that is homeomorphic to a cylinder. A simple, closed curve CC in Σ\Sigma is said to be contractible if some component of Σ∖C\Sigma\setminus C is an open disk whose boundary is CC. Otherwise we say CC is non-contractible.

An embedding ψ\psi of a graph GG in Σ\Sigma is a map from vertices of GG to distinct points of Σ\Sigma and edges of GG to internally disjoint simple open curves in Σ\Sigma between the image of its endpoints. We use ψ(G)\psi(G) to denote the union of all points and curves in the image of ψ\psi. The faces of an embedded graph GG are the connected components of Σ∖ψ(G)\Sigma\setminus\psi(G), and we denote the set of faces by F(G)F(G). If every face is homeomorphic to an open disk, then we say ψ\psi is a cellular embedding.

A curve in Σ\Sigma is GG-normal if it only meets ψ(G)\psi(G) in vertices. If Σ\Sigma is not the sphere, the facewidth of the embedded graph GG is the minimum number of vertices intersected by a GG-normal, non-contractible, simple closed curve in Σ\Sigma. Facewidth is not defined for graphs embedded in the sphere. If GG is 2-connected and cellularly embedded in Σ\Sigma with facewidth at least 2, then the boundary of each face is a cycle in GG [55 Proposition 5.5.11].

If GG is connected and cellularly embedded in a surface Σ\Sigma of Euler genus gg, then

∣V(G)∣−∣E(G)∣+∣F(G)∣=2−g.|V(G)|-|E(G)|+|F(G)|=2-g.

Given a cycle CC in a graph GG with embedding ψ\psi in Σ\Sigma, we say that CC is 1-sided (resp. 2-sided) if the simple closed curve ψ(C)\psi(C) is 1-sided (resp. 2-sided).

A cellular embedding of a graph GG on a surface Σ\Sigma is determined by its embedding scheme (π,λ)(\pi,\lambda) where π\pi associates to each vertex of GG a cyclic ordering of its incident edges, which one thinks of as the “clockwise ordering” of edges around a vertex, and λ:E(G)→Z2\lambda:E(G)\to\mathbb{Z}_2 takes value 1 if and only if the orientation given by π\pi of the edge’s endpoints disagree. Because a cyclic ordering of the edges incident to a vertex of degree at most 2 does not encode a clockwise direction, the above definition only makes sense for graphs of minimum degree 3. To extend the definition to all graphs GG, we first suppress degree 2 vertices to get a multigraph G′G' and we define the embedding scheme (π′,λ′)(\pi',\lambda') as above, where every edge incident to a vertex of degree 1 may have an arbitrary λ′\lambda' label. Now for each edge e′e' of G′G' obtained by suppressing degree 2 vertices along a path PP in GG, we assign the value of λ(e)\lambda(e) for edges e∈E(P)e \in E(P) such that the total λ\lambda-weight of PP is equal to λ′(e′)\lambda'(e'). This defines an embedding scheme for GG. We note a cycle in GG is one-sided if and only if it is odd with respect to λ\lambda. All embeddings in this paper will be stored as embedding schemes for algorithmic purposes.

Note that if one reverses the orientation of π\pi at a vertex v∈V(G)v \in V(G) and adds 1 (over Z2\mathbb{Z}_2) to the label λ(e)\lambda(e) for all non-loop edges e∈δ(v)e \in\delta(v), then this defines the same embedding. We say an embedding scheme (π′,λ′)(\pi',\lambda') is obtained from (π,λ)(\pi,\lambda) by shifting at vv if it is obtained in this way. We say that two embeddings (π,λ)(\pi,\lambda) and (π′,λ′)(\pi',\lambda') of a graph GG are (shifting) equivalent if (π′,λ′)(\pi',\lambda') is obtained from (π,λ)(\pi,\lambda) by a sequence of shiftings at vertices. Note that if (π,λ)(\pi,\lambda) and (π′,λ′)(\pi',\lambda') are shifting equivalent, then the signed graph (G,λ′)(G,\lambda') is obtained from (G,λ)(G,\lambda) by shifting.

Given an embedding scheme (π,λ)(\pi,\lambda) of a graph GG, we can naturally define the set of facial walks as walks which, at every vertex vv, choose the next edge in the cyclic ordering π(v)\pi(v) with a direction that swaps whenever the traversed edge has λ(e)=1\lambda(e)=1.

We are now equipped to say exactly when the dual of a graph has an alternating orientation.

Lemma 3.3. Let GG be cellularly embedded in a surface such that the boundary of every face is a cycle in GG. Then the following are equivalent.

  1. G∗G^* admits an alternating orientation,

  2. A cycle in GG is odd if and only if it is one-sided,

  3. The constraints {ωC(y)=0∣C is a facial cycle}\{\omega_C(y)=0 \mid C\text{ is a facial cycle}\} are not linearly independent.

Proof. Consider an embedding scheme (π,λ)(\pi,\lambda) for GG. Such an embedding satisfies that the odd cycles are exactly the one-sided cycles if and only if (π,λ)(\pi,\lambda) is shifting equivalent to (π′,1)(\pi',1). That is, we have a local orientation π′\pi' around each vertex such that for every edge, the orientations of its ends disagree. We may then orient each facial cycle of G∗G^* to be a directed cycle agreeing with the orientation of π′\pi'; such an orientation is an alternating orientation of G∗G^*. See Figure 3.1 (see also [13 Lemma 17]).

Figure 3.1. The graph GG is shown with dashed edges, and circular arrows displaying the local orientation π′\pi'. Note that neighboring local orientations disagree, which gives an alternating orientation of the dual graph G∗G^* depicted with the solid black arcs.

Conversely, suppose G∗G^* admits an alternating orientation. Then each facial cycle of G∗G^* is a directed cycle in this orientation. This naturally gives a local orientation around the corresponding vertex in GG, and these orientations have the property that for any edge of GG, the orientation of its ends disagree. Thus the first two items are equivalent.

Now suppose G∗G^* admits an alternating orientation. Then, for each facial cycle CC corresponding to v∈V(G∗)v \in V(G^*), sign its edges such that edges leaving vv get a positive sign and edges entering vv get a negative sign. We can possibly negate ωC(y)\omega_C(y) to match this signing, and summing this up over every facial cycle gives a linear dependence between ωC(y)=0\omega_C(y)=0 for facial cycles CC.

Conversely, suppose that there exists some linear dependence among {ωC(y)=0}\{\omega_C(y)=0\}. Write the constraints as My=0My=0, where M∈{−1,0,1}F(G)×E(G)M \in\{-1,0,1\}^{F(G)\times E(G)}. Note the support of MM is the incidence matrix of G∗G^*. By assumption, there is some nonzero vector μ\mu such that μTM=0\mu^{\mathsf{T}}M = 0. Since G∗G^* is connected and μ≠0\mu\ne0, it must be that μ\mu is nonzero in every entry. Since MM has two nonzero entries per column, we may assume μ∈{−1,1}F(G)\mu\in\{-1,1\}^{F(G)} by scaling μ\mu. By multiplying each row ff of MM by μ(f)\mu(f), we may assume μ=1\mu= 1. The new matrix MM has two nonzero entries per column, and every column contains a 11 and −1-1. Then MM defines an alternating orientation of G∗G^* (recall that the rows are scalings of ωC\omega_C).

Homology and even-faced embeddings

Let (G,γ)(G,\gamma) be an embedded signed graph. Given a face with facial walk (v0,e1,v1,e2,v2,…,vk−1,ek,v0)(v_0,e_1,v_1,e_2,v_2,\ldots,v_{k-1},e_k,v_0), the face’s parity is given by ∑i=1kγ(ei)∈Z2\sum_{i=1}^{k}\gamma(e_i) \in\mathbb{Z}_2. (We define the parity of a face in an unsigned embedded graph by identifying the unsigned graph GG with the signed graph (G,1)(G,\mathbb{1}).) We say a face is even or odd if its parity is 00 or 11 in Z2\mathbb{Z}_2 respectively. We say the embedding is even-faced if no odd cycle bounds a disk in Σ\Sigma. If the embedding is cellular, this is equivalent to requiring that every face is even.

Let DD be a directed graph cellularly embedded in a surface Σ\Sigma. Two circulations f,g∈ZE(D)f,g \in\mathbb{Z}^{E(D)} are said to be Z\mathbb{Z}-homologous if f−gf-g is a linear combination of facial circulations with integer coefficients. The first homology group of Σ\Sigma over the integers, denoted H1(Σ;Z)H_1(\Sigma;\mathbb{Z}), is the quotient group of all integer circulations in DD by the subgroup of all circulations which are Z\mathbb{Z}-homologous to the zero circulation. We note that the resulting group does not depend on our choice of DD. It is well known that if Σ\Sigma is orientable of Euler genus gg then H1(Σ;Z)≅ZgH_1(\Sigma;\mathbb{Z}) \cong\mathbb{Z}^g, and if Σ\Sigma is non-orientable of Euler genus gg then H1(Σ;Z)≅Z2×Zg−1H_1(\Sigma;\mathbb{Z}) \cong\mathbb{Z}_2 \times\mathbb{Z}^{g-1}.

When (G,γ)(G,\gamma) is a signed graph with an even-faced cellular embedding in a surface Σ\Sigma, the parity of a cycle only depends on the “Z\mathbb{Z}-homology” of the cycle. We now make this precise. Let DD be an arbitrary orientation of GG. We define the parity of an integer circulation ff in DD to be ∑e∈E(D)f(e)γ(e)∈Z2\sum_{e\in E(D)}f(e)\gamma(e) \in\mathbb{Z}_2. Because (G,γ)(G,\gamma) is even-faced, the parity of any facial circulation is 00. Hence the parity of ff depends only on the Z\mathbb{Z}-homology of ff (in fact, this defines a homomorphism φ:H1(Σ;Z)→Z2\varphi: H_1(\Sigma;\mathbb{Z}) \to\mathbb{Z}_2). Then, for any cycle CC in GG, the parity of CC is equal to the parity of a {−1,0,1}\{-1,0,1\}-circulation ff supported on E(C)E(C). Hence the parity of CC depends only on the Z\mathbb{Z}-homology of the corresponding circulation. In cases such as this when the direction of flow around CC does not matter, we may speak of the “Z\mathbb{Z}-homology” of CC to mean the Z\mathbb{Z}-homology of the corresponding circulation ff in an arbitrary orientation DD of GG.

Preprocessing

Removing odd faces

In this section we will reduce from Problem 2.1 to Problem 2.2. That is, we will reduce to the case when all faces are even by possibly guessing on a small number of vertices and increasing the genus.

We first reduce to the case with a constant number of odd faces, not just a constant number of vertex-disjoint odd faces. For this we use an Erdős-Posá property for odd faces, which is implied for instance by a more general result due to the authors of [28] which says that Erdős-Posá holds even when replacing “odd faces” by any property for faces. To derive the below statement from [28], Corollary 4.7, consider coloring every odd face by a unique color and coloring every even face by the same color. We give the proof here for completeness. Recall that a face is odd if its facial walk has odd length.

Theorem 4.1. [28] Let g,k∈Z≥0g,k \in\mathbb{Z}_{\ge0}. Let GG be a graph embedded on a surface Σ\Sigma of Euler genus gg. Then either there exist kk odd faces F1,…,FkF_1,\ldots,F_k of GG whose boundaries are pairwise vertex-disjoint, or there exists a set X⊆V(G)X \subseteq V(G) of size at most O(k2)O(k^2) such that every odd face contains some vertex in XX.

Moreover, there exists an algorithm running in time 2O(g2)poly⁡(k)∣V(G)∣42^{O(g^2)}\operatorname{poly}(k)|V(G)|^4 that finds either the faces F1,…,FkF_1,\ldots,F_k or the set XX with the properties promised above.

We will skip the proof of the FPT algorithm which finds XX. It will become clear from the proof that this reduces to finding XX in the low treewidth case, which one can do via dynamic programming. We first show that the above holds for graphs of small treewidth.

Lemma 4.2. [28] Let k∈Z≥0k \in\mathbb{Z}_{\ge0}. Let GG be a graph with treewidth at most η\eta embedded in a surface Σ\Sigma, and let C1,…,CmC_1,\ldots,C_m be the boundaries of some collection of faces. Then either there exist kk vertex disjoint facial boundaries Ci1,…,CikC_{i_1},\ldots,C_{i_k}, or there exists a set X⊆V(G)X \subseteq V(G) of size at most (k−1)(η+1)(k-1)(\eta+1) hitting all CiC_i.

Proof. Let (T,β)(T,\beta) be a tree decomposition of GG of width at most η\eta. For each i∈[m]i \in[m], let TiT_i be the subtree of TT induced by all bags containing a vertex of CiC_i. That is, V(Ti)={t∈V(T):β(t)∩V(Ci)≠∅}V(T_i) = \{t \in V(T) : \beta(t) \cap V(C_i) \ne\varnothing\}. We now show that either there exists kk vertex disjoint subtrees Ti1,…,TikT_{i_1},\ldots,T_{i_k} from our collection, or there exists a set $X \subseteq V(T) of size at most k−1k-1 hitting all subtrees in our collection. We proceed by induction on ∣V(T)∣|V(T)|. Clearly we may assume ∣V(T)∣≥2|V(T)| \ge2, and let ℓ∈V(T)\ell\in V(T) be a leaf. If there exists a subtree TiT_i in our collection consisting only of the vertex ℓ\ell, then we apply induction to T−ℓT-\ell with the collection obtained from deleting all subtrees containing ℓ\ell. If we obtain a packing of disjoint subtrees then we may add TiT_i to the packing, and if we obtain a hitting set then we may add ℓ\ell to the hitting set. If there is no such tree with vertex set equal to ℓ\ell, then we delete ℓ\ell from TT and from every subtree of our collection, and again the desired statement then follows by induction.

If we obtain the packing of disjoint subtrees Ti1,…,TikT_{i_1},\ldots,T_{i_k}, then the corresponding collection of facial boundaries Ci1,…,CikC_{i_1},\ldots,C_{i_k} are vertex disjoint. If we instead obtain the hitting set Y⊆V(T)Y \subseteq V(T) then the set X={v∈β(t):t∈Y}X=\{v\in\beta(t):t\in Y\} is a hitting set of size at most (k−1)(η+1)(k-1)(\eta+1) hitting all facial boundaries CiC_i.

We can now give the proof of Theorem 4.1. This essentially follows from greedily packing odd faces and using the fact that in a graph of bounded genus, any collection of faces that all intersect a common face in at least one vertex induces a graph of bounded treewidth.

Proof of Theorem 4.1. We first greedily pack odd faces F1,…,FbF_1,\ldots,F_b whose boundaries are vertex disjoint. We may assume b<kb<k, otherwise we obtain the desired collection of faces. Now every other odd face shares some vertex with one of F1,…,FbF_1,\ldots,F_b.

For each i∈[b]i\in[b], let GiG_i be the graph induced on the boundary of FiF_i and all faces which share a vertex with FiF_i. We first claim that GiG_i has treewidth O(g)O(g). Let Gi′G'_i be formed from GiG_i by adding a vertex vFv_F inside every face FF of GiG_i which is also a face in GG and making vFv_F incident to every vertex on the facial boundary of FF. We then note that Gi′G'_i has radius at most 33; by definition every vertex is distance at most 33 from vFiv_{F_i}. Eppstein [18 Theorem 2] proved that graphs of radius rr embedded in a surface of Euler genus gg have treewidth O(rg)O(rg). Because GiG_i is a subgraph of Gi′G'_i, we immediately obtain that GiG_i has treewidth O(g)O(g).

Now in each GiG_i, we apply Lemma 4.2 to the collection of odd faces which are also faces of GG. We may assume each GiG_i does not contain a packing of kk such odd faces, else we obtain a packing in GG. Thus we obtain a set of O(kg)O(kg) vertices XiX_i hitting all such faces in GiG_i. Then X=⋃i=1bXiX=\bigcup_{i=1}^{b}X_i is the desired hitting set in GG.

Now suppose the graph is embedded on a surface of Euler genus gg with kk vertex-disjoint odd faces. By the above, there exists a set XX of at most O(k2g)O(k^2g) vertices hitting all odd faces. We guess the intersection of a maximum independent set with XX. Call this intersection Y⊆XY\subseteq X. Guessing YY increases the running time by a factor of 2O(k2g)2^{O(k^2g)} which we assume to be constant. One would like to delete X∪NG(Y)X\cup N_G(Y) and find a maximum independent set in the resulting graph, but doing so may destroy that the embedding is cellular. Instead, we do the following. We first set the weight of XX and all neighbors of YY to zero. We may assume that no zero-weight vertex is chosen in a maximum weight independent set, and so any optimal solution can be extended to an independent set by including YY.

Now, for each x∈Xx\in X, xx may be contained in the boundary of many odd faces. However, because xx has weight 00, we may subdivide edges incident to xx with weight 00 vertices without changing an optimal solution. We now show that, for each x∈Xx\in X, we may subdivide incident edges in such a way that at most one of the faces containing xx on the boundary is odd after subdivision. By doing this one at a time for each vertex in XX, we reduce to an instance with at most O(k2g)O(k^2g) odd faces which is cellularly embedded.

For each x∈Xx \in X, we construct an auxiliary multigraph HxH_x as follows, see Figure 4.1 for an illustration. HxH_x is a subgraph of the dual G∗G^* consisting of all vertices and edges lying on the face xx of G∗G^*. That is, the vertex set of HxH_x is the set of faces of GG with xx on their boundary. The edge set of HxH_x is in bijection with δ(x)\delta(x), where each edge e∈δ(x)e \in\delta(x) corresponds to an edge in HxH_x between the faces containing ee. We note that HxH_x is not necessarily a cycle as xx may appear multiple times on a facial walk in GG, and in fact HxH_x may contain parallel edges or loops. However, we note that HxH_x is connected. We let T⊆V(Hx)T \subseteq V(H_x) be the set of odd faces containing xx on their boundary. If ∣T∣|T| is even, we let T′=TT' = T, otherwise we let T′T' be formed from TT by removing a single element. Because HxH_x is connected, there exists a set F⊆E(Hx)F \subseteq E(H_x) which is a T′T'-join. That is, every vertex v∈V(Hx)v \in V(H_x) has odd FF-degree if v∈T′v \in T' and even FF-degree if v∈V(Hx)∖T′v \in V(H_x) \setminus T'. Then by subdividing the edges of δ(x)\delta(x) which correspond to an edge in FF, we have that every face except possibly the single face in T∖T′T \setminus T' is even in the resulting graph.

Figure 4.1. The left and right images show the local structure in GG around vertex xx. The image in the center shows the subgraph Hx⊆G∗H_x\subseteq G^*. In this example, one has T=T′={f2,f4,f5,f7}T=T'=\{f_2,f_4,f_5,f_7\}. The T′T'-join is shown in bold red.

We have now reduced to the case when GG is cellularly embedded in a surface of Euler genus gg with a constant number, say kk, of odd faces. Clearly kk must be even by considering the number of odd degree vertices in the dual. We can then arbitrarily pair up these odd faces, and for each pair we add two vertex disjoint paths between them consisting of new vertices, and we give these new vertices weight 00, see Figure 4.2. We think of these new paths as being embedded in a new handle added between the faces. We can do this such that the resulting graph has an even faced embedding in a surface of Euler genus g+kg+k.

Figure 4.2. An illustration of the process of adding a handle to connect a pair of odd faces. The left graph has exactly two odd faces, shown in red. In the right graph, the odd faces are connected by the gray handle, as well as the four green edges and two green vertices on the handle. Note that the resulting graph has two new faces, shaded in blue and orange, which are both even. Moreover, the red cycles do not bound faces anymore.

Standard assumptions

Let GG be a graph with an even-faced embedding in a surface of Euler genus gg. We now record a list of assumptions that we may assume when solving Problem 2.2, which we refer to as the “standard assumptions”.

We say a vertex weighting w:V(G)→Q≥0w : V(G) \to\mathbb{Q}_{\ge0} is edge-induced if there is a nonnegative edge weighting c:E(G)→Q≥0c : E(G) \to\mathbb{Q}_{\ge0} such that for every vertex vv we have w(v)=∑e∈δ(v)c(e)w(v) = \sum_{e \in\delta(v)} c(e).

Assumption 4.3. The vertex weights are edge-induced, and we can compute the corresponding edge weighting in polynomial time.

Proof. This follows from solving the linear programming relaxation, applying a result of Nemhauser and Trotter [57], and complementary slackness, see [13 Section 4]. We note that in the reduction to edge-induced weights given by Conforti et al. [13] they possibly delete vertices, but we may instead set their weight to 00 (and set c(e)=0c(e) = 0 for all incident edges) in order to preserve a cellular embedding. □\square

Assumption 4.4. GG has minimum degree 22.

Proof. Clearly we may assume GG has no isolated vertices. Suppose GG contains a vertex vv of degree 11 with single neighbour uu. Because weights are edge induced, w(v)=c(uv)≥0w(v) = c(uv) \ge0. Without loss of generality we can assume that one of uu or vv will be picked in a maximum weight independent set (even if c(uv)=0c(uv)=0). That is, uvuv will never be slack. Then we may delete vv and add c(uv)c(uv) to our final weight (in doing so, the weight of uu decreases by c(uv)c(uv)). By repeating this at most ∣V(G)∣|V(G)| times we reduce to an instance with minimum degree 2. We note that after deleting a vertex of degree 1 our embedding is still cellular and even-faced.

Assumption 4.5. GG is non-bipartite.

Proof. It is well known that we can find a maximum weight independent set in GG in polynomial time if GG is bipartite.

We note the above implies GG is not embedded in the plane.

Assumption 4.6. GG is 2-connected and the embedding of GG has facewidth at least 2.

Proof. We will use that for any cellularly embedded graph HH, the faces of HH are all bounded by cycles if and only if HH is 2-connected with facewidth at least 2, see [52 Proposition 3.8]. Hence, it suffices to force every face to be bounded by a cycle. For a vertex vv appearing on the boundary of a face FF, we define the FF-multiplicity of vv to be the number of times that vv appears on the facial walk of FF. We define the excess of vv to be the sum over the faces FF containing vv on their boundary of the FF-multiplicity of vv minus 1. We define the excess of GG to be the sum of the excess of every vertex. If GG has excess 0, then every face is bounded by a cycle. We note that each vertex has excess at most its degree, so the excess of GG is bounded by O(∣E(G)∣)O(|E(G)|).

We do the following for each face FF of GG. Consider a facial walk of FF, and suppose that some vertex vv appears twice on this facial walk. Let uu and ww be the vertices preceding and following vv on this facial walk respectively. Because GG is simple and does not contain vertices of degree 1, u≠wu\ne w. We add a new vertex v′v' of weight 0 adjacent to uu and ww, and we embed v′v' in the face FF. By setting the cost cc of the edges v′uv'u and v′wv'w to be zero we preserve that the weights are edge induced, and clearly any optimal solution remains optimal. By adding the vertex v′v' we have divided the even face FF into two even faces, and the resulting graph has smaller excess than GG. Hence by repeating this a polynomial number of times we arrive at a graph of excess 0, and hence a graph where every face is bounded by a cycle. We note this preprocessing step is similar to one used in [21 Section 6.4].

Slack vectors

As it turns out, in order to solve MIS instances on surfaces, it is useful to think of independent sets as integer vectors in the edge space. The goal of this section is characterize these vectors and explain how to formulate MIS in the edge space. Although most of the results follow from known results, in particular, from Confòrti et al. [13 Proposition 14, Lemma 16], this section is self-contained, except for Lemma 4.12 which we do not reprove.

Let GG be a graph, and let A∈{0,1}E(G)×V(G)A\in\{0,1\}^{E(G)\times V(G)} denote its (edge-vertex) incidence matrix. Throughout this section, we assume that GG is connected, although the entire discussion easily generalizes to arbitrary graphs. Consider the set Φ(G):={y∈QE(G)∣∃x∈QV(G):Ax+y=1}\Phi(G):=\{y\in\mathbb{Q}^{E(G)}\mid\exists x\in\mathbb{Q}^{V(G)}:Ax+y=\mathbf{1}\}. This is an affine subspace of the edge space QE(G)\mathbb{Q}^{E(G)} that we call the slack space. In fact, Φ(G)\Phi(G) is a linear subspace of the edge space, since 0∈Φ(G)\mathbf{0}\in\Phi(G). Indeed, we have A1=2⋅1A\mathbf{1}=2\cdot\mathbf{1} (the first 1\mathbf{1} is the all-one vector in the vertex space and the second the all-one vector in the edge space). Hence, letting x:=121x:=\frac{1}{2}\mathbf{1} and y:=0y:=\mathbf{0}, we find Ax+y=A(121)+0=1Ax+y=A(\frac{1}{2}\mathbf{1})+\mathbf{0}=\mathbf{1}, proving that 0∈Φ(G)\mathbf{0}\in\Phi(G). This also shows that λ1=0\lambda\mathbf{1}=\mathbf{0} for all λ∈ker⁡(AT)\lambda\in\ker(A^{\mathsf T}). (We point out that the above arguments break in characteristic 2: it is important that we are working over Q\mathbb{Q} and not say over GF(2)GF(2).)

Our first lemma gives a characterization of Φ(G)\Phi(G) that follows directly from the Fredholm alternative.

Lemma 4.7. The slack space Φ(G)\Phi(G) is the set of all y∈QE(G)y\in\mathbb{Q}^{E(G)} such that λTy=0\lambda^{\mathsf T}y=0 for all λ∈ker⁡(AT)\lambda\in\ker(A^{\mathsf T}).

Next, we make Lemma 4.7 more explicit and provide a non-redundant set of linear equations describing the slack space. An elementary vector of ATA^{\mathsf T} is a support-minimal element of ker⁡(AT)∖{0}\ker(A^{\mathsf T})\setminus\{\mathbf{0}\}. These are sometimes called minimal linear dependences between the columns of ATA^{\mathsf T}. Note that, up to scaling, every elementary vector is determined by its support. The supports of elementary vectors coincide with the circuits of the (column) vector matroid M(AT)M(A^{\mathsf T}). Every λ∈ker⁡(AT)\lambda\in\ker(A^{\mathsf T}) can be written as a linear combination of elementary vectors. In fact, we can even say more.

Let BB denote a (column) basis of ATA^{\mathsf T}. This is a maximal set of linearly independent columns of ATA^{\mathsf T}, or equivalently a basis of the vector matroid M(AT)M(A^{\mathsf T}). Every column of ATA^{\mathsf T} that is not in the basis can be expressed in a unique way as a linear combination of the columns in the basis. The corresponding elementary vector λ\lambda is called the fundamental elementary vectors of ATA^{\mathsf T} with respect to BB. (By convention, we scale λ\lambda so that $\lambda(j)=-1, where jj is the label of the column that is not in the basis, and expressed in the basis.) Then, every element of ker⁡(A⊤)\ker(A^\top) can be written as a linear combination of the fundamental elementary vectors of A⊤A^\top with respect to BB.

We conclude the following. Let BB be any basis of A⊤A^\top. Then, the slack space Φ(G)\Phi(G) is the set of all y∈QE(G)y \in\mathbb{Q}^{E(G)} such that λ⊤y=0\lambda^\top y = 0 for all fundamental elementary vectors λ\lambda of A⊤A^\top with respect to BB.

Now, since A⊤A^\top is the vertex-edge incidence matrix of graph GG, the bases and circuits of M(A⊤)M(A^\top), seen as subgraphs of GG, are easy to describe. Since we assume GG is connected, the bases of M(A⊤)M(A^\top) are either the spanning trees (in case GG is bipartite), or a maximal set of edges in which every component contains at most 1 odd cycle (in case GG is non-bipartite). In the second case, every component of the basis is an odd 1-tree. An odd 1-tree is a tree with a single extra edge whose unique cycle is odd. In particular, if GG is not bipartite, then it contains a basis formed from a spanning, odd 1-tree. The circuits of M(A⊤)M(A^\top) are exactly the even cycles and odd bicycles, that is, the union of two odd cycles and a single path between them (the odd cycles are disjoint unless the path between them is trivial, in which case they share a single vertex). We describe the corresponding elementary vectors in terms of even closed walks.

A walk in GG is a sequence W=(v0,e1,v1,e2,v2,…,ek,vk)W = (v_0, e_1, v_1, e_2, v_2, \ldots, e_k, v_k) where v0,v1,…,vkv_0, v_1, \ldots, v_k are vertices and e1,e2,…,eke_1, e_2, \ldots, e_k are edges such that ei=vi−1vie_i = v_{i-1}v_i for each i∈[k]i \in[k]. The length of walk WW is kk. Walk WW is closed if v0=vkv_0 = v_k. We call WW a cycle walk if it is closed and v0,…,vk−1v_0, \ldots, v_{k-1} are distinct. We associate to walk WW the vector

λW:=∑i=1k(−1)i−11ei.\lambda_W := \sum_{i=1}^{k}(-1)^{i-1}\mathbf{1}_{e_i}.

Whenever WW is a closed even walk, we have λW∈ker⁡(A⊤)\lambda_W \in\ker(A^\top). Moreover, every elementary vector λ\lambda of A⊤A^\top is the form λ=λW\lambda= \lambda_W, where WW is a walk around an even cycle or odd bicycle. We obtain the following non-redundant description of the slack space.

Lemma 4.8. Let BB denote any basis of A⊤A^\top. Let W\mathcal{W} denote the collection of even closed walks arising from fundamental circuits of M(A⊤)M(A^\top) with respect to BB. Hence, ∣W∣=∣E(G)∣−∣V(G)∣+1|\mathcal{W}| = |E(G)| - |V(G)| + 1 if GG is bipartite, and ∣W∣=∣E(G)∣−∣V(G)∣|\mathcal{W}| = |E(G)| - |V(G)| if GG is non-bipartite. The slack space Φ(G)\Phi(G) is the set of all y∈QE(G)y \in\mathbb{Q}^{E(G)} such that λW⊤y=0\lambda_W^\top y = 0 for all W∈WW \in\mathcal{W}.

We call an even closed walk WW a circuit walk if WW is a walk around an even cycle or an odd bicycle. Also, we define the width of such a walk WW as 0 in case WW is an even cycle walk, or as the number of vertices on the connecting path in case WW is a walk around an odd bicycle.

Lemma 4.9. Let WW denote a circuit walk. If GG is 2-connected, then λW\lambda_W can be written as a linear combination of vectors λW′\lambda_{W'} where W′W' is an even cycle walk.

Proof. Let kk denote the width of WW. If k=0k = 0, then there is nothing to prove. Suppose that k≥1k \ge1. We show that λW\lambda_W can be written as the sum of two vectors λW′\lambda_{W'} where W′W' is a circuit walk of width at most k−1k - 1. The result follows by induction on kk.

Suppose we have an even closed walk WW around an odd bicycle consisting of two odd cycles C1,C2C_1, C_2 and a path PP between them. Let v1v_1 and v2v_2 be the ends of PP in C1C_1 and C2C_2 respectively (possibly, v1=v2v_1 = v_2, since PP may be trivial). Since GG is 2-connected, we can find a path QQ from C1−v1C_1 - v_1 to (C2∪P)−v1(C_2 \cup P) - v_1 that is internally disjoint from the odd bicycle. Let w1w_1 and w2w_2 denote the ends of QQ in C1−v1C_1 - v_1 and (C2∪P)−v1(C_2 \cup P) - v_1, respectively.

If w2∈V(C2−v2)w_2 \in V(C_2 - v_2), then we may find two even cycles C1′C'_1 and C2′C'_2 whose union is C1∪C2∪P∪QC_1 \cup C_2 \cup P \cup Q and whose intersection is P∪QP \cup Q. Let W1′W'_1 and W2′W'_2 be corresponding even cycle walks. We can choose W1′W'_1 and W2′W'_2 such that since the signs of λW1′\lambda_{W'_1} and λW2′\lambda_{W'_2} agree on E(P)E(P) and disagree on E(Q)E(Q). Then λW=λW1′+λW2′\lambda_W = \lambda_{W'_1} + \lambda_{W'_2}.

Otherwise, w2∈V(P−v1)w_2 \in V(P - v_1) (notice that this case can arise only when k≥2k \ge2). Let P′P' denote the subpath of PP from v1v_1 to w2w_2. Then we can find an even cycle C1′C'_1 and an odd bicycle C2′C'_2 such that the union of C1′C'_1 and C2′C'_2 is C1∪C2∪P∪QC_1 \cup C_2 \cup P \cup Q and the intersection is P′∪QP' \cup Q. Again, let W1′W'_1 and W2′W'_2 be corresponding circuit walks, thus W1′W'_1 is an even cycle walk and W2′W'_2 is an odd bicycle walk of width at most k−1k - 1. After possibly shifting one of W1′W'_1 and W2′W'_2, we can ensure that the signs of λW1′\lambda_{W'_1} and λW2′\lambda_{W'_2} agree on E(P′)E(P') and disagree on E(Q)E(Q). Once more, we have λW=λW1′+λW2′\lambda_W = \lambda_{W'_1} + \lambda_{W'_2}. □

Together with Lemma 4.8, Lemma 4.9 implies that the slack space has a complete description in the edge space via ∣E(G)∣−∣V(G)∣|E(G)| - |V(G)| (resp. ∣E(G)∣−∣V(G)∣+1|E(G)| - |V(G)| + 1) linear constraints that correspond to even cycles, whenever GG is 2-connected and non-bipartite (resp. bipartite).

Next, consider the set Λ(G):={y∈ZE(G)∣∃x∈ZV(G):Ax+y=1}\Lambda(G) := \{y \in\mathbb{Z}^{E(G)} \mid\exists x \in\mathbb{Z}^{V(G)} : Ax + y = \mathbf{1}\}. This is an affine lattice that we call the slack lattice. We call its elements slack vectors. Observe that Λ(G)\Lambda(G) is contained in the slack space Φ(G)\Phi(G). Clearly, Λ(G)⊆Φ(G)∩ZE(G)\Lambda(G) \subseteq\Phi(G) \cap\mathbb{Z}^{E(G)}. As stated in our next lemma, the converse inclusion holds whenever GG is bipartite, and when GG is non-bipartite adding a single parity constraint yields a complete description of Λ(G)\Lambda(G).

Lemma 4.10. If GG is bipartite, then Λ(G)=ZE(G)∩Φ(G)\Lambda(G)=\mathbb{Z}^{E(G)}\cap\Phi(G). If GG is non-bipartite, then Λ(G)={y∈ZE(G)∩Φ(G)∣λW0Ty≡1(mod2)}\Lambda(G)=\{y\in\mathbb{Z}^{E(G)}\cap\Phi(G)\mid\lambda_{W_0}^{\mathsf{T}}y\equiv1\pmod{2}\}, where W0W_0 is any walk around an odd cycle of GG.

Proof. First, assume that GG is bipartite, and let y∈ZE(G)∩Φ(G)y\in\mathbb{Z}^{E(G)}\cap\Phi(G). Since AA is totally unimodular, there exists x∈ZV(G)x\in\mathbb{Z}^{V(G)} such that Ax=1−yAx=\mathbf{1}-y, showing that y∈Λ(G)y\in\Lambda(G).

Second, assume that GG is non-bipartite. Fix some y∈ZE(G)∩Φ(G)y\in\mathbb{Z}^{E(G)}\cap\Phi(G). We have to prove that Ax=1−yAx=\mathbf{1}-y has a solution x∈ZV(G)x\in\mathbb{Z}^{V(G)} if and only if λW0Ty≡1(mod2)\lambda_{W_0}^{\mathsf{T}}y\equiv1\pmod{2}.

Let C0C_0 denote the subgraph of GG traced by W0W_0. Let B⊂GB\subset G denote any odd, spanning 1-tree containing C0C_0 (so BB is a basis). Consider the subsystem ABx=1B−yBA_Bx=\mathbf{1}_B-y_B, where the subscript BB indicates restriction to rows corresponding to edges of BB. Since GG is non-bipartite, ABA_B is invertible. We put ABA_B in Hermite normal form. Assume that the elements of BB are ordered in such a way that the edges of the odd cycle come last, and in consecutive order. Then, there exists an unimodular matrix UU such that

ABU=[I00C]whereC=[10⋯0001⋯0000⋱00⋮⋮⋱⋮⋮00⋯1011⋯12].A_BU=\begin{bmatrix}\mathbf{I}&0\\0&C\end{bmatrix}\quad\text{where}\quad C=\begin{bmatrix}1&0&\cdots&0&0\\0&1&\cdots&0&0\\0&0&\ddots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&1&0\\1&1&\cdots&1&2\end{bmatrix}.

Since y∈ZE(G)y\in\mathbb{Z}^{E(G)}, we see that ABx=1B−yBA_Bx=\mathbf{1}_B-y_B has a solution x∈ZV(G)x\in\mathbb{Z}^{V(G)} if and only if λW0Ty≡1(mod2)\lambda_{W_0}^{\mathsf{T}}y\equiv1\pmod{2}. Since y∈Φ(G)y\in\Phi(G), this occurs if and only if Ax=1−yAx=\mathbf{1}-y has an integer solution.

Among other things, Lemma 4.10 implies that 0∈Λ(G)0\in\Lambda(G) (that is, Λ(G)\Lambda(G) is a lattice) if and only GG is bipartite.

We wrap up the discussion of the slack lattice, slightly switching notation to be more in line with the literature. We recall the following definition from Section 2: given walk W=(v0,e1,v1,e2,v2,…,ek,vk)W=(v_0,e_1,v_1,e_2,v_2,\ldots,e_k,v_k), we define a linear form ωW\omega_W on QE(G)\mathbb{Q}^{E(G)} by letting ωW(y):=∑i=1k(−1)i−1y(ei)\omega_W(y):=\sum_{i=1}^{k}(-1)^{i-1}y(e_i) for y∈QE(G)y\in\mathbb{Q}^{E(G)}. That is, we let ωW(y)=λWTy\omega_W(y)=\lambda_W^{\mathsf{T}}y.

Lemma 4.11. For every 2-connected graph GG, there exists a collection C\mathcal{C} of ∣E(G)∣−∣V(G)∣+1|E(G)|-|V(G)|+1 cycle walks such that

Λ(G)={y∈ZE(G) | ωW(y)=0for every even cycle walk W∈C,ωW(y)≡1(mod2)for every odd cycle walk W∈C}.\Lambda(G)=\left\{y\in\mathbb{Z}^{E(G)}\ \middle|\ \begin{aligned} \omega_W(y)&=0 &&\text{for every even cycle walk }W\in\mathcal{C},\\ \omega_W(y)&\equiv1\pmod{2} &&\text{for every odd cycle walk }W\in\mathcal{C} \end{aligned}\right\}.

If GG is non-bipartite, then C\mathcal{C} contains a unique odd cycle walk. Moreover, C\mathcal{C} can be constructed in polynomial time.

Proof. The statement follows from our three previous lemmas. To see that the collection C\mathcal{C} can be computed in polynomial time, we start with a basis {λW∣W∈W(B)}\{\lambda_W\mid W\in\mathcal{W}(B)\} of ker⁡(AT)\ker(A^{\mathsf{T}}) where W(B)\mathcal{W}(B) denotes the circuit walks coming from any odd, spanning 1-tree BB (or spanning tree BB, in case GG is non-bipartite). For each WW that is an odd bicycle walk, we perform at most ∣E(G)∣|E(G)| updates as in the proof of Lemma 4.9. Each update finds two vectors λW1′,λW2′\lambda_{W'_1},\lambda_{W'_2} which span λW\lambda_W. We remove λW\lambda_W from the basis and replace it with one of λW1′,λW2′\lambda_{W'_1},\lambda_{W'_2} such that we keep a basis. At the end of this process, we obtain a basis of ker⁡(AT)\ker(A^{\mathsf{T}}) of the form {λW∣W∈C}\{\lambda_W\mid W\in\mathcal{C}\}, where C\mathcal{C} is the resulting collection of even cycle walks. In case GG is non-bipartite, we pick any odd cycle walk W0W_0 and add it to C\mathcal{C}.

Finally, we discuss bounds on x∈ZV(G)x\in\mathbb{Z}^{V(G)} and y∈ZE(G)y\in\mathbb{Z}^{E(G)} on the solutions to Ax+y=1Ax+y=\mathbf{1}. We require that y≥0y\geq0, which implies Ax≤1Ax\leq1. It would be natural to also enforce x≥0x\geq0, since only such integer points correspond to independent sets. However, we will not do this explicitly and rather show that this can be assumed without loss of generality whenever (x,y)(x,y) is optimal. We call a slack vector y∈Λ(G)y\in\Lambda(G) feasible if y≥0y\geq0.

Let c∈Q≥0E(G)c\in\mathbb{Q}_{\geq0}^{E(G)} and let w∈Q≥0V(G)w\in\mathbb{Q}_{\geq0}^{V(G)} satisfy w(v):=c(δ(v))w(v):=c(\delta(v)) for all v∈V(G)v\in V(G). This last condition can be written w=ATcw=A^{\mathsf{T}}c. If x∈ZV(G)x\in\mathbb{Z}^{V(G)} and y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} satisfy Ax+y=1Ax+y=\mathbf{1}, then by multiplying on the left by cTc^{\mathsf{T}} (and letting w(x):=wTxw(x):=w^{\mathsf{T}}x and c(y):=cTyc(y):=c^{\mathsf{T}}y), we get w(x)+c(y)=c(E(G))w(x)+c(y)=c(E(G)). Notice that c(E(G))=12w(V(G))c(E(G))=\frac{1}{2}w(V(G)).

Our next lemma states that finding a maximum independent set in GG with respect to vertex weights w(v)w(v) is equivalent to finding a minimum cost feasible slack vector subject to edge costs c(e)c(e). Notice that, by what precedes, we have c(y′)≤c(y)c(y')\leq c(y) if and only if w(x′)≥w(x)w(x')\geq w(x) for solution pairs (x,y)(x,y) and (x′,y′)(x',y').

Lemma 4.12 (Fiorini et al. [21], Lemma 32). Let GG be a connected, non-bipartite graph and let w∈Q≥0V(G)w\in\mathbb{Q}_{\geq0}^{V(G)} be vertex weights induced by edge costs c∈Q≥0E(G)c\in\mathbb{Q}_{\geq0}^{E(G)}. Given any pair (x,y)∈ZV(G)×Z≥0E(G)(x,y)\in\mathbb{Z}^{V(G)}\times\mathbb{Z}_{\geq0}^{E(G)} with Ax+y=1Ax+y=\mathbf{1},

one can compute in strongly polynomial time a pair (x′,y′)∈{0,1}V(G)×{0,1}E(G)(x',y') \in\{0,1\}^{V(G)} \times\{0,1\}^{E(G)} such that Ax′+y′=1Ax' + y' = 1 and c(y′)≤c(y)c(y') \leq c(y).

By the above we have reduced to Problem 2.5, restated below.

Problem 2.5. Given a graph GG satisfying the standard assumptions, non-negative edge costs c:E(G)→Q≥0c : E(G) \to\mathbb{Q}_{\geq0}, and a collection C\mathcal{C} of ∣E(G)∣−∣V(G)∣+1|E(G)| - |V(G)| + 1 cycles with exactly one of them odd, minimize c(y)=∑e∈E(G)c(e)y(e)c(y) = \sum_{e \in E(G)} c(e)y(e) over all y∈Z≥0E(G)y \in\mathbb{Z}_{\geq0}^{E(G)} satisfying ωC(y)=0\omega_C(y) = 0 for every even cycle C∈CC \in\mathcal{C} and ωC(y)≡1(mod2)\omega_C(y) \equiv1 \pmod{2} for the unique odd cycle C∈CC \in\mathcal{C}. Furthermore, C\mathcal{C} is such that the above constraints exactly characterize the slack vectors y∈Z≥0E(G)y \in\mathbb{Z}_{\geq0}^{E(G)}.

The derived graph

An important object in our algorithm will be the derived graph of a group-labeled graph. Derived graphs are important in topological graph theory. We provide a brief overview here for the specific case of signed graphs, but we refer the reader to [30] for a more in-depth introduction. The derived graph of a signed graph also appears in [69] where the relation between their matroid and the matroid of the signed graph is discussed.

Given a signed graph (G,γ)(G,\gamma) where γ:E(G)→Z2\gamma: E(G) \to\mathbb{Z}_2, we associate a derived (signed) graph (G~,γ~)(\widetilde{G},\widetilde{\gamma}) defined as follows. G~\widetilde{G} has vertex set V(G~)=V(G)×Z2V(\widetilde{G}) = V(G) \times\mathbb{Z}_2. For each edge uv∈E(G)uv \in E(G), we add the edges (u,0)(v,γ(uv))(u,0)(v,\gamma(uv)) and (u,1)(v,1+γ(uv))(u,1)(v,1+\gamma(uv)) to E(G~)E(\widetilde{G}), and give these edges γ~\widetilde{\gamma}-label equal to γ(uv)\gamma(uv). Intuitively, we have two copies of our vertex set, and by traversing an even edge one stays in the same copy and by traversing an odd edge one swaps to the other copy.

For each vertex v∈V(G)v \in V(G), we call the vertices (v,0),(v,1)∈V(G~)(v,0),(v,1) \in V(\widetilde{G}) its copies in G~\widetilde{G}, and we call vv the underlying vertex of (v,0)(v,0) and (v,1)(v,1). Similarly for each edge uv∈E(G)uv \in E(G), we call the edges (u,0)(v,γ(uv))(u,0)(v,\gamma(uv)) and (u,1)(v,1+γ(uv))(u,1)(v,1+\gamma(uv)) in E(G~)E(\widetilde{G}) the copies of uvuv, and we call the edge uvuv the underlying edge of (u,0)(v,γ(uv))(u,0)(v,\gamma(uv)) and (u,1)(v,1+γ(uv))(u,1)(v,1+\gamma(uv)).

In the case of a signed graph where every edge has label 1∈Z21 \in\mathbb{Z}_2, the derived graph is also called a bipartite double cover. We note that for any signed graph (G,γ)(G,\gamma), the derived graph (G~,γ~)(\widetilde{G},\widetilde{\gamma}) has no odd cycles (with respect to γ~\widetilde{\gamma}).

We will use that if (G,γ)(G,\gamma) has an even-faced embedding on a surface of bounded genus, then (G~,γ~)(\widetilde{G},\widetilde{\gamma}) also embeds on a surface of bounded genus. Then we will find an alternating orientation D∗D^* of the dual G~∗\widetilde{G}^* and solve MIS on GG by solving a minimum cost circulation problem on D∗D^* with extra topological constraints.

Given an embedding scheme (π,λ)(\pi,\lambda) of (G,γ)(G,\gamma), we can define an embedding scheme (π~,λ~)(\widetilde{\pi},\widetilde{\lambda}) of (G~,γ~)(\widetilde{G},\widetilde{\gamma}), called the derived embedding, in the following way. Let vv be a vertex of G~\widetilde{G} with incident edges e~1,…,e~k\widetilde{e}_1,\ldots,\widetilde{e}_k, and let e1,…,eke_1,\ldots,e_k be the corresponding underlying edges. Then we simply order the edges e~1,…,e~k\widetilde{e}_1,\ldots,\widetilde{e}_k in π~\widetilde{\pi} to agree with the ordering of e1,…,eke_1,\ldots,e_k in π\pi. We set λ~(e~)=λ(e)\widetilde{\lambda}(\widetilde{e})=\lambda(e) for ee the underlying edge of e~\widetilde{e}. We let Σ~\widetilde{\Sigma} be the surface defined by this derived embedding, and we call Σ~\widetilde{\Sigma} the derived surface. We note that if (G,γ)(G,\gamma) does not contain a γ\gamma-odd cycle, then (G~,γ~)(\widetilde{G},\widetilde{\gamma}) will be two disjoint copies of (G,γ)(G,\gamma), and Σ~\widetilde{\Sigma} will be disconnected.

Theorem 5.1 ([30 Theorem 4.1.1]). If (G,γ)(G,\gamma) is a signed graph containing a γ\gamma-odd cycle with a cellular embedding in a surface Σ\Sigma of Euler genus gg, then the derived graph (G~,γ~)(\widetilde{G},\widetilde{\gamma}) embeds in a surface Σ~\widetilde{\Sigma} such that every even face of (G,γ)(G,\gamma) becomes two faces of the same length in (G~,γ~)(\widetilde{G},\widetilde{\gamma}), and every odd face of (G,γ)(G,\gamma) becomes a single face in (G~,γ~)(\widetilde{G},\widetilde{\gamma}) of twice the length. In particular, if (G,γ)(G,\gamma) is connected, contains a γ\gamma-odd cycle, and has an even-faced embedding in Σ\Sigma, then the Euler genus of Σ~\widetilde{\Sigma} is 2g−22g-2.

By the above it is well defined to talk of the two “copies” of an even face in GG as they appear in the derived embedding of G~\widetilde{G}. We warn the reader that although every vertex of G∗G^* has two copies in the vertices of (G~)∗(\widetilde{G})^* when GG has an even-faced embedding, it is not true that (G~)∗(\widetilde{G})^* is the derived graph of (G∗,γ)(G^*,\gamma). For instance if (G,1)(G,1) is such that every edge is odd, then G~\widetilde{G} is bipartite, but its dual (G~)∗(\widetilde{G})^* may contain odd cycles whenever there is an odd degree vertex of GG. Yet the derived graph of (G∗,1)(G^*,1) is bipartite.

We also note the following.

Theorem 5.2 ([30 Theorem 4.1.4]). Let (G,γ)(G,\gamma) be a signed graph with embedding in Σ\Sigma, and let (G~,γ~)(\widetilde{G},\widetilde{\gamma}) be the derived graph with derived embedding in Σ~\widetilde{\Sigma}. Then Σ~\widetilde{\Sigma} is non-orientable if and only if (G,γ)(G,\gamma) contains a 1-sided even cycle.

We now describe how to obtain the surface Σ~\widetilde{\Sigma} from Σ\Sigma in terms of surface cutting in order to provide the reader with geometric intuition. We first note that if the signed graph (G,γ′)(G,\gamma') is obtained from (G,γ)(G,\gamma) by shifting at the vertex v∈V(G)v \in V(G), then the derived graph of (G,γ′)(G,\gamma') is isomorphic to a shifting of the derived graph of (G,γ)(G,\gamma). The derived graph of (G,γ′)(G,\gamma') can be obtained from the derived graph of (G,γ)(G,\gamma) by exchanging the labels of (v,0)(v,0) and (v,1)(v,1) and shifting at those two vertices. Hence, up to shifting and isomorphism, the derived graph of a signed graph does not depend on the shifting.

Given a signed graph (G,γ)(G,\gamma) with an even-faced embedding in a surface Σ\Sigma, the parity of a cycle depends only on the Z\mathbb{Z}-homology of the cycle in Σ\Sigma. Thus we can find a set of closed curves in Σ\Sigma such that a cycle is odd if and only if it crosses these curves an odd number of times. Then we can shift (G,γ)(G,\gamma) such that the odd edges are exactly the edges which cross these curves an odd number of times. The surface Σ~\widetilde{\Sigma} is formed from Σ\Sigma by cutting at these curves, copying the surface, and then gluing the copies at these curves. We illustrate the process in Figure 5.1 and Figure 5.2.

Figure 5.1. An illustration of the process that lets us obtain the derived graph and the derived embedding starting from a graph GG embedded in an orientable surface of Euler genus 4. The left figure shows the original embedded graph, where the odd edges are the yellow edges, i.e., the edges that cross the red and cyan curve. The right figure shows the process of cutting along the curves while maintaining the embedding of the graph.

Figure 5.2. In the left figure, we can see the two copies of the cut surface, aligned such that the corresponding embeddings fit together. The right figure shows the derived graph together with its derived embedding after gluing the copies at these curves.

Reducing to a circulation problem

Recall from Subsection 4.2 that the standard assumptions for a graph with associated weight function (G,w)(G,w) are the following:

  • GG is embedded in a surface Euler genus g=O(1)g=O(1) with all faces even,

  • GG is non-bipartite,

  • the embedding has facewidth at least 2,

  • GG is 2-connected,

  • and the weight function ww is edge-induced.

The goal of this section is to reduce from Problem 2.5 to Problem 2.6, that is, to describe a feasible slack vector as a circulation over the dual of the derived graph.

Given an (unsigned, undirected) graph GG with an embedding scheme (π,λ)(\pi,\lambda) in a surface Σ\Sigma of Euler genus gg, we define the signed graph (G,1+λ)(G,1+\lambda) where (1+λ)(e)=1+λ(e)∈Z2(1+\lambda)(e)=1+\lambda(e)\in\mathbb{Z}_2 for every edge e∈E(G)e\in E(G). We note that (π,λ)(\pi,\lambda) also gives an even-faced embedding of (G,1+λ)(G,1+\lambda) because every face of GG is homeomorphic to a disk, and hence the λ\lambda-weight of every facial cycle is 0. We denote its derived signed graph by (G~,1+λ~)(\widetilde{G},\mathbb{1}+\widetilde{\lambda}), and note that the label of every edge ee in the derived signed graph is given 1+λ~(e)1+\widetilde{\lambda}(e) where (π~,λ~)(\widetilde{\pi},\widetilde{\lambda}) is the derived embedding in Σ~\widetilde{\Sigma}. By construction (G~,1+λ~)(\widetilde{G},\mathbb{1}+\widetilde{\lambda}) is balanced, i.e., for every cycle C=v1v2…vkv1C=v_1v_2\ldots v_kv_1 we have that ∑i=1k(1+λ~)(vivi+1)=0\sum_{i=1}^{k}(1+\widetilde{\lambda})(v_iv_{i+1})=0 (over Z2\mathbb{Z}_2). This implies that the λ~\widetilde{\lambda}-weight of every cycle is equal to its parity (in the usual sense), or in other words, a cycle in G~\widetilde{G} is odd if and only if it is one-sided.

By Theorem 5.1, the derived embedding (π~,λ~)(\widetilde{\pi},\widetilde{\lambda}) is an embedding of G~\widetilde{G} on a surface Σ~\widetilde{\Sigma} of bounded genus. We take the dual G~∗\widetilde{G}^{*}, and by Lemma 3.3 there exists an orientation D∗D^{*} of G~∗\widetilde{G}^{*} which is alternating. That is, for every vertex v∈V(D∗)v\in V(D^{*}), the edge incident to vv alternatively enter and leave vv in the cyclic ordering given by π~\widetilde{\pi}.

It could be the case that (G,1+λ)(G,\mathbb{1}+\lambda) contains no odd cycles, that is, GG is embedded such that the odd cycles are exactly the one-sided cycles. We will call this case the degenerate case. In this case, the derived graph (G~,1+λ~)(\widetilde{G},\mathbb{1}+\widetilde{\lambda}) is disconnected, and is formed from the disjoint union of two copies of GG. We then work instead directly with the graph GG instead of the derived graph, and we define D∗D^{*} to be an alternating orientation of G∗G^{*}. The proof becomes easier the degenerate case, and we will mention the small necessary changes throughout the proof. This is exactly the case which was solved previously by Conforti et al. [13].

We will need the following property of the orientation D∗D^{*} when we are not in the degenerate case, and we note that the alternating orientation of D∗D^{*} is unique up to reversing every edge.

Lemma 6.1. Suppose we are not in the degenerate case. Then for every edge e∈E(G∗)e\in E(G^{*}) with copies e0,e1∈E(G~∗)e_0,e_1\in E(\widetilde{G}^{*}), the edges e0,e1e_0,e_1 are given opposite orientations by D∗D^{*}. That is, for uv∈E(G∗)uv\in E(G^{*}) where u0,u1u_0,u_1 are the copies of uu and v0,v1v_0,v_1 are the copies of vv in G~∗\widetilde{G}^{*} such that u0v0,u1v1∈E(G~∗)u_0v_0,u_1v_1\in E(\widetilde{G}^{*}), we have u0v0→,v1u1→∈E(D∗)\overrightarrow{u_0v_0},\overrightarrow{v_1u_1}\in E(D^{*}).

Proof. Let (π~,λ~)(\widetilde{\pi},\widetilde{\lambda}) be the derived embedding of G~\widetilde{G}, so in particular for every vertex v∈V(G)v\in V(G) its copies v0,v1∈V(G~)v_0,v_1\in V(\widetilde{G}) have the same cyclic ordering given by π~\widetilde{\pi}. As in Lemma 3.3, the orientation of D∗D^{*} is given by finding a shifting equivalent embedding scheme (π~,λ~′)(\widetilde{\pi},\widetilde{\lambda}') such that λ~′(e~)=1\widetilde{\lambda}'(\widetilde{e})=1 for every edge e~∈E(G~)\widetilde{e}\in E(\widetilde{G}), and then cyclically orienting the faces of D∗D^{*} to match with the cyclic orientation π~′\widetilde{\pi}'. Thus it suffices to show that for each vertex v∈V(G)v\in V(G) with copies v0,v1∈V(G~)v_0,v_1\in V(\widetilde{G}), the cyclic orientations given by π~′(v0),π~′(v1)\widetilde{\pi}'(v_0),\widetilde{\pi}'(v_1) disagree. Recall that V(G~)=V(G)×Z2V(\widetilde{G})=V(G)\times\mathbb{Z}_2, and it follows from the definition of G~\widetilde{G} that (π~′,λ~′)(\widetilde{\pi}',\widetilde{\lambda}') can be obtained from (π~,λ~)(\widetilde{\pi},\widetilde{\lambda}) by shifting at every vertex in {(v,1)∣v∈V(G)}\{(v,1)\mid v\in V(G)\}. Because the orientations given π~(v0)\widetilde{\pi}(v_0) and π~(v1)\widetilde{\pi}(v_1) agree and shifting swaps the orientation, the result follows. □\square

Recall that we have some edge weighting c:E(G)→Q≥0c:E(G)\to\mathbb{Q}_{\geq0}. This naturally gives an edge weighting of G~\widetilde{G} (and hence of D∗D^{*}) by giving each copy of the same edge weight as the underlying edge. We define a linear map ρ:ZE(D∗)→ZE(G)\rho:\mathbb{Z}^{E(D^{*})}\to\mathbb{Z}^{E(G)} such that entry e∈E(G)e\in E(G) of ρ(f)\rho(f) has value f(e~0)+f(e~1)f(\widetilde{e}_0)+f(\widetilde{e}_1) for ee the underlying edge of both e~0,e~1∈E(G~)\widetilde{e}_0,\widetilde{e}_1\in E(\widetilde{G}). Then for any nonnegative integer circulation ff in D∗D^{*}, we associate the vector y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} given by y=ρ(f)y=\rho(f). That is, y(e)=f(e~0)+f(e~1)y(e)=f(\widetilde{e}_0)+f(\widetilde{e}_1) where e~0,e~1∈E(G~)\widetilde{e}_0,\widetilde{e}_1\in E(\widetilde{G}) are the two copies of e∈E(G)e\in E(G). Note that the orientations of e~0\widetilde{e}_0 and e~1\widetilde{e}_1 will disagree in D∗D^{*}, but the flow does not cancel; both f(e~0)f(\widetilde{e}_0) and f(e~1)f(\widetilde{e}_1) are nonnegative. In the degenerate case we define ρ\rho to be the identity function.

We will eventually solve a minimum cost nonnegative circulation problem on D∗D^{*} and return the associated vector y=ρ(f)y=\rho(f). However, we first need to add some extra constraints by the following procedure. Recall from Subsection 4.3 that y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} is feasible if y∈Λ(G)={y∈Z≥0E(G)∣∃x∈ZV(G):Ax+y=1}y\in\Lambda(G)=\{y\in\mathbb{Z}^{E(G)}_{\geq0}\mid\exists x\in\mathbb{Z}^{V(G)}:Ax+y=\mathbb{1}\} where AA is the incidence matrix of GG.

Lemma 6.2. Let GG satisfy the standard assumptions and let C\mathcal{C} be the collection of cycles given in Problem 2.5. Then we can in polynomial time find a set of cycles C1,…,CgC_1,\ldots,C_g where C1C_1 is an odd cycle and C2,…,CgC_2,\ldots,C_g are even cycles for gg the Euler genus of Σ\Sigma such that y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} is feasible if and only if

  1. ωC(y)=0\omega_C(y)=0 for every facial cycle CC,

  1. ωCi(y)=0\omega_{C_i}(y)=0 for every even cycle C2,…,CgC_2,\ldots,C_g, and

  1. ωC1(y)≡1(mod2)\omega_{C_1}(y)\equiv1\pmod{2}.

Proof. Let C={C1,…,Ct}\mathcal{C}=\{C_1,\ldots,C_t\} for t=∣E(G)∣−∣V(G)∣+1t=|E(G)|-|V(G)|+1 such that C1C_1 is the unique odd cycle in C\mathcal{C}. Recall that y∈Z≥0E(G)y\in\mathbb{Z}_{\geq0}^{E(G)} is feasible if and only if ωC1(y)≡1(mod2)\omega_{C_1}(y)\equiv1\pmod{2} and ωCi(y)=0\omega_{C_i}(y)=0 for all C2,…,CtC_2,\ldots,C_t. We note that {ωC(y)=0∣C a facial cycle}\{\omega_C(y)=0\mid C\text{ a facial cycle}\} contains at least ∣F(G)∣−1|F(G)|-1 linearly independent constraints. To see this, note that any proper subset of the faces must contain some edge which is in only one face from the collection (because the dual is connected), so there can not be a linear dependence among less than ∣F(G)∣|F(G)| of the faces. In fact, all constraints in {ωC(y)=0∣C a facial cycle}\{\omega_C(y)=0 \mid C\text{ a facial cycle}\} are linearly independent unless we are in the degenerate case, see Lemma 3.3.

Thus we may extend these linearly independent constraints to a basis by including at most (t−1)−(∣F(G)∣−1)=−∣V(G)∣+∣E(G)∣−∣F(G)∣+1=g−1(t-1)-(|F(G)|-1)=-|V(G)|+|E(G)|-|F(G)|+1=g-1 of the constraints given by the cycles C2,…,CtC_2,\ldots,C_t as desired. We note that except in the degenerate case, it suffices to take only a collection C1,…,Cg−1C_1,\ldots,C_{g-1}. We will then add a linearly dependent constraint given by CgC_g for notational convenience.

Each constraint corresponding to a cycle CiC_i above immediately gives a linear constraint for an integer circulation ff of D∗D^* because we set y=ρ(f)y=\rho(f) as above. We then have the following problem.

Problem 2.6. Let D∗D^* be an alternating orientation of G~∗\widetilde{G}^* for GG satisfying the standard assumptions, and let C1,…,CgC_1,\ldots,C_g be cycles in GG where C1C_1 is odd and C2,…,CgC_2,\ldots,C_g are even. Find a minimum cc-cost nonnegative integer circulation ff in D∗D^* satisfying the linear constraints

  1. ωCi(ρ(f))=0\omega_{C_i}(\rho(f))=0 for every even cycle C2,…,CgC_2,\ldots,C_g, and

  1. ωC1(ρ(f))≡1(mod2)\omega_{C_1}(\rho(f))\equiv1\pmod{2}.

We now reduce Problem 2.5 to Problem 2.6.

Theorem 6.3. Let ff be a feasible solution to Problem 2.6. Then ρ(f)\rho(f) is a feasible solution to Problem 2.5 with the same objective value. Conversely there exists an optimal solution y∈{0,1}E(G)y\in\{0,1\}^{E(G)} to Problem 2.5 such that y=ρ(f)y=\rho(f) for some feasible solution ff to Problem 2.6.

Proof. Let ff be a feasible solution to Problem 2.6. We first show that y:=ρ(f)y:=\rho(f) is a feasible solution to Problem 2.5. We proceed by Lemma 6.2. Consider a facial cycle CC in GG, and let v0,v1v_0,v_1 be the associated vertices in D∗D^* that correspond to the two copies of CC in G~\widetilde{G}. Let e1,e2,…,eℓe^1,e^2,\ldots,e^\ell be the edges of CC in cyclic order, and let e⃗i0,e⃗i1\vec e^0_i,\vec e^1_i be the two copies of eie^i for i∈[ℓ]i\in[\ell]. Then because D∗D^* is an alternating orientation and by flow conservation at v0v_0 and v1v_1 we have

0=∑i=1ℓ(−1)i−1f(e⃗i0)+∑i=1ℓ(−1)i−1f(e⃗i1)=∑i=1ℓ(−1)i−1y(ei)=ωC(y)\begin{aligned} 0=\sum_{i=1}^{\ell}(-1)^{i-1}f(\vec e^0_i)+\sum_{i=1}^{\ell}(-1)^{i-1}f(\vec e^1_i) \\ &=\sum_{i=1}^{\ell}(-1)^{i-1}y(e^i) \\ &=\omega_C(y) \end{aligned}

as desired. We also have ωCi(y)=0\omega_{C_i}(y)=0 for every even cycle CiC_i and ωC1(y)≡1(mod2)\omega_{C_1}(y)\equiv1\pmod{2} by assumption. Thus by Lemma 6.2, yy is feasible, and clearly yy has the same objective value as ff.

Now let yy be an optimal solution to Problem 2.5. By Lemma 4.12, we may assume that y∈{0,1}E(G)y\in\{0,1\}^{E(G)}. We now construct a nonnegative integer circulation ff in D∗D^* such that y=ρ(f)y=\rho(f). Let F⊆E(G)F\subseteq E(G) be the set of edges for which yy takes value 1. Let G∗G^* be the dual of GG, and for every vertex v∈V(G∗)v\in V(G^*) we locally assign +1+1 or −1-1 to the incident edges such that the assignment alternates as you traverse the edges clockwise around the vertex. This is possible because every vertex in G∗G^* has even degree. This assignment does not have to be consistent; it could be that ee has ends u,vu,v and uu assigns the value +1+1 and vv assigns the value −1-1. Let us denote the local signing of ee by sgn⁡u(e)∈{−1,1}\operatorname{sgn}_u(e)\in\{-1,1\}. For u∈V(G∗)u\in V(G^*), let CC be the facial walk around the face uu in GG. Then ωC(y)=0\omega_C(y)=0 implies ∑e∈F∩δ(u)sgn⁡u(e)=0\sum_{e\in F\cap\delta(u)}\operatorname{sgn}_u(e)=0. We will now construct a collection of closed walks in G∗G^* using only edges in FF such that each edge of FF is used exactly once over all walks in the collection.

We start at an arbitrary vertex vv incident to an edge of FF, and walk along an arbitrary edge of FF. Each time we enter a vertex uu, we look at the local signing of our edge at uu and exit through an edge of the opposite sign. If u≠vu\ne v, then this is always possible because ∑e∈F∩δ(u)sgn⁡u(e)=0\sum_{e\in F\cap\delta(u)}\operatorname{sgn}_u(e)=0. We continue like this for as long as possible. In particular, we continue even if we again reach the starting vertex vv as long as there is an edge of the opposite sign from which to leave vv. If we ever get stuck, then it must be because we reached the starting vertex vv, and furthermore it must be that the last edge of the walk has the opposite sign from the first edge of our walk. Otherwise, suppose without loss of generality the first traversed edge ee had sgn⁡v(e)=1\operatorname{sgn}_v(e)=1, then the edges of F∩δ(v)F \cap\delta(v) traversed so far have alternating sum equal to 2, so there is some untraversed edge e′e' in F∩δ(v)F \cap\delta(v) with sgn⁡v(e′)=−1\operatorname{sgn}_{v}(e')=-1 for which we may continue the walk.

We may not have used all of the edges of FF in the above closed walk. However we can repeat the above as many times as needed, only using new edges of FF in each walk, to obtain the desired collection of closed walks.

We note that for a vertex uu, the edges of δ(u)\delta(u) traversed in our walk do not have to have strictly alternating signs with respect to sgn⁡u\operatorname{sgn}_{u}. We only require that when we enter through an edge of one sign, we exit through an edge of the opposite sign. It could be, for instance, that the edges of δ(u)\delta(u) are traversed in the order +,−,−,++,-,-,+. However, it will be the case that whenever the alternation switches, this will correspond to walking to the other copy of uu in D∗D^*, which we now describe.

We now claim that each walk in our collection corresponds naturally to a closed walk in D∗D^* which obeys the direction of edges. Then by pushing a unit of flow along each walk in our collection we obtain a nonnegative integer circulation ff of D∗D^* such that ρ(f)=y\rho(f)=y. Let vv be the first vertex of our walk with copies v0,v1v_0,v_1 in D∗D^*, and by possibly reversing our walk we may assume that the first edge of our walk is oriented out of v0v_0, and we can start our walk there. Then if we enter a vertex uu through a directed edge, the next edge of our walk will correspond to an edge directed out of uu because the orientation of D∗D^* is alternating. Thus the walk in G∗G^* corresponds to a walk respecting directions in D∗D^*, and it suffices to show that the walk in D∗D^* is closed. This is clear in the degenerate case, so suppose we are not in that case. Then by Lemma 6.1 recall that for every edge e∈E(G)e \in E(G), its two copies e0,e1e_0,e_1 have different orientations in D∗D^*. Suppose towards contradiction that we end our walk at the copy v1v_1 of vv instead of v0v_0. Then the first edge of our walk is oriented out of v0v_0 and the last edge is oriented into v1v_1. However because the edges incident to v0v_0 and v1v_1 have opposite orientations, this implies that the first and last edge of our walk have the same local signing relative to vv, a contradiction.

Because yy satisfies ωCi(y)=0\omega_{C_i}(y)=0 for every even cycle CiC_i and ωC1(y)=1(mod2)\omega_{C_1}(y)=1 \pmod2, we have that ρ(f)=y\rho(f)=y implies that ff is a feasible solution to Problem 2.6.

Final algorithm

The main result of this section is that we may solve Problem 2.6 in polynomial time. We will solve Problem 2.6 via the following algorithm, which is due to Chambers, Erickson, and Nayyeri [7] in the orientable case and due to Morell, Seidel, and Weltge [56] in the nonorientable case.

Theorem 7.1 ([7, 56]). There exists a polynomial time algorithm which takes as input a directed graph DD cellularly embedded on a surface of bounded genus with nonnegative costs c:E(D)→Q≥0c:E(D)\to\mathbb{Q}_{\geq0} and an integer circulation ff in DD, and finds a minimum-cost nonnegative integer circulation in DD that is Z\mathbb{Z}-homologous to ff.

Theorem 7.2. Problem 2.6 can be solved in polynomial time.

Proof. For a nonnegative integer circulation in D∗D^*, we set ω(f)=(ωC1(ρ(f)),ωC2(ρ(f)),…,ωCg(ρ(f)))∈Z2×Zg−1\omega(f)=(\omega_{C_1}(\rho(f)),\omega_{C_2}(\rho(f)),\ldots,\omega_{C_g}(\rho(f)))\in\mathbb{Z}_2\times\mathbb{Z}^{g-1}. We first claim that ω(f)\omega(f) depends only on the Z\mathbb{Z}-homology of ff. Because ω\omega is linear in ff, it suffices to show that if gg is a circulation consisting of a single unit of flow around a single face, then ω(g)=0\omega(g)=0. Let gg be a circulation sending a single unit of flow around a face CC of D∗D^* corresponding to vertex v~∈V(G~)\widetilde{v}\in V(\widetilde{G}). Let vv be the underlying vertex in GG, so ρ(g)\rho(g) is the indicator of δ(v)\delta(v). Then for each i∈[g]∖{1}i\in[g]\setminus\{1\}, the cycle CiC_i either doesn’t include vv or includes two edges of δ(v)\delta(v) which appear with opposite signs in ωCi\omega_{C_i}. In either case we see that ωCi(ρ(g))=0\omega_{C_i}(\rho(g))=0. Because C1C_1 either doesn’t include vv or includes two edges in δ(v)\delta(v), we also have ωC1(ρ(g))=0∈Z2\omega_{C_1}(\rho(g))=0\in\mathbb{Z}_2 as desired.

Because the feasibility of ff depends only on its Z\mathbb{Z}-homology, we may guess the correct Z\mathbb{Z}-homology of ff and compute a minimum cost circulation with that Z\mathbb{Z}-homology by Theorem 7.1. The main difficulties are obtaining a polynomially bounded region over which to guess, and constructing an integer flow with the guessed Z\mathbb{Z}-homology in order to apply Theorem 7.1. Let g~\widetilde{g} denote the Euler genus of Σ~\widetilde{\Sigma}.

By [56 Corollary 12, Proposition 18], we can efficiently compute a collection of vectors ξ1,…,ξg~∈ZE(D∗)\xi_1,\ldots,\xi_{\widetilde{g}}\in\mathbb{Z}^{E(D^*)} such that the entries of ξi\xi_i are bounded by 2 in absolute value for every i∈[g~]i\in[\widetilde{g}], and two circulations f,f′f,f' of D∗D^* are homologous if and only if

  • ⟨ξi,f⟩=⟨ξi,f′⟩\langle\xi_i,f\rangle=\langle\xi_i,f'\rangle for each i∈[g~]i\in[\widetilde{g}] if Σ~\widetilde{\Sigma} is orientable, or

  • ⟨ξ1,f⟩≡⟨ξ1,f′⟩(mod2)\langle\xi_1,f\rangle\equiv\langle\xi_1,f'\rangle\pmod2 and ⟨ξi,f⟩=⟨ξi,f′⟩\langle\xi_i,f\rangle=\langle\xi_i,f'\rangle for all i∈[g~]∖{1}i\in[\widetilde{g}]\setminus\{1\} if Σ~\widetilde{\Sigma} is non-orientable.

We then define ξ(f)=(⟨ξ1,f⟩,…,⟨ξg~,f⟩)\xi(f)=(\langle\xi_1,f\rangle,\ldots,\langle\xi_{\widetilde{g}},f\rangle) either as a vector in Zg~\mathbb{Z}^{\widetilde{g}} if Σ~\widetilde{\Sigma} is orientable, or as a vector in Z2×Zg~−1\mathbb{Z}_2\times\mathbb{Z}^{\widetilde{g}-1} if Σ~\widetilde{\Sigma} is non-orientable. That is, ξ\xi defines an isomorphism from the first homology group of Σ~\widetilde{\Sigma} over the integers to Zg~\mathbb{Z}^{\widetilde{g}} or Z2×Zg~−1\mathbb{Z}_2\times\mathbb{Z}^{\widetilde{g}-1}. By Theorem 6.3, there is an optimal solution f∗f^{*} to Problem 2.6 such that ρ(f∗)=y\rho(f^{*}) = y for y∈{0,1}E(G)y \in\{0,1\}^{E(G)}. By definition of ρ\rho, we obtain that there exists an optimal solution f∗∈{0,1}E(D∗)f^{*} \in\{0,1\}^{E(D^{*})}. Because ξi\xi_i has entries bounded by 2 in absolute value for every ii, we have that ξ(f∗)\xi(f^{*}) has entries bounded by 2∣E(D∗)∣2|E(D^{*})| in absolute value (where if the first entry is in Z2\mathbb{Z}_2, there is no restriction on this entry). Let Ω\Omega denote the set of all such ξ(f∗)\xi(f^{*}), so ∣Ω∣≤(4∣E(D∗)∣+1)g~|\Omega| \leq(4|E(D^{*})|+1)^{\widetilde{g}}.

It now suffices, for each z∈Ωz \in\Omega, to compute a circulation fz∈ZE(D∗)f_z \in\mathbb{Z}^{E(D^{*})} with ξ(fz)=z\xi(f_z)=z. Suppose we can find such an fzf_z for each zz. Then we check whether ω(fz)=(1,0,…,0)\omega(f_z)=(1,0,\ldots,0). If so, we apply Theorem 7.1 to find a minimum cost nonnegative integer circulation homologous to fzf_z, and we output the circulation of minimum cost over all such zz.

We now show how to compute an integer circulation fzf_z with ξ(fz)=z\xi(f_z)=z for each z∈Ωz \in\Omega. We first compute a collection of cycles in G~\widetilde{G} which generate the first homology group of Σ~\widetilde{\Sigma} over the integers. This can be done by taking a spanning tree T∗T^{*} of G~∗\widetilde{G}^{*} and a spanning tree TT of G~\widetilde{G} which are edge disjoint; this is always possible and can be done in polynomial time [19 Lemma 3.1]. Then the fundamental cycles of edges e∈E(G~∗)∖(E(T)∪E(T∗))e \in E(\widetilde{G}^{*}) \setminus(E(T) \cup E(T^{*})) with respect to T∗T^{*} generate the fundamental group of Σ~\widetilde{\Sigma} [19 Lemma 3.2]. Because the first homology group of Σ~\widetilde{\Sigma} over the integers is the abelianization of its fundamental group, these cycles also generate the first homology group of Σ~\widetilde{\Sigma} over the integers. That is, by sending one unit of flow around these cycles in D∗D^{*} (so that edges in the reverse direction of our cyclic orientation get negative flow), we have that any circulation is an integer combination of these cycles and facial circulations. Note that we have ∣E(G~∗)∣−(∣V(G~∗)∣−1)−(∣F(G~∗)∣−1)=g~|E(\widetilde{G}^{*})|-(|V(\widetilde{G}^{*})|-1)-(|F(\widetilde{G}^{*})|-1)=\widetilde{g} such cycles, and let us denote them by B1,…,Bg~∈ZE(D∗)B_1,\ldots,B_{\widetilde{g}} \in\mathbb{Z}^{E(D^{*})}.

Because B1,…,Bg~B_1,\ldots,B_{\widetilde{g}} generate the first homology group of Σ~\widetilde{\Sigma}, for each z∈Ωz \in\Omega there exists an integer combination a∈Zg~a \in\mathbb{Z}^{\widetilde{g}} such that ξ(∑i=1g~aiBi)=z\xi\left(\sum_{i=1}^{\widetilde{g}} a_iB_i\right)=z. We can solve for aa either by finding an integer solution to the linear system

∑i=1g~aiξ(Bi)=z\sum_{i=1}^{\widetilde{g}} a_i \xi(B_i)=z

in the case that Σ~\widetilde{\Sigma} is orientable, or by finding an integer solution (a1,…,ag~,k)(a_1,\ldots,a_{\widetilde{g}},k) to the linear system

∑i=1g~ai⟨ξ1,Bi⟩=z1+2k\sum_{i=1}^{\widetilde{g}} a_i\langle\xi_1,B_i\rangle=z_1+2k
∑i=1g~ai⟨ξ2,Bi⟩=z2\sum_{i=1}^{\widetilde{g}} a_i\langle\xi_2,B_i\rangle=z_2
⋮\vdots
∑i=1g~ai⟨ξg~,Bi⟩=zg~\sum_{i=1}^{\widetilde{g}} a_i\langle\xi_{\widetilde{g}},B_i\rangle=z_{\widetilde{g}}

where z1∈Z2z_1 \in\mathbb{Z}_2 is interpreted as an element of {0,1}\{0,1\} in the case that Σ~\widetilde{\Sigma} is non-orientable. We may then set fz=∑i=1g~aiBif_z=\sum_{i=1}^{\widetilde{g}} a_iB_i as desired.

In the above proof we use Theorem 7.1 as a black box. It’s not hard to see that in [56 Section 3], they prove Theorem 7.1 by solving a minimum cost circulation with a constant number of extra linear constraints where one of these constraints is taken modulo 2. That is, the same proof as in [56 Section 3] can be used to solve Problem 2.6 directly.

AI disclosure. No AI tools were used in the writing of this manuscript. All proofs and their presentations are entirely due to the authors.

Acknowledgments. We thank Mujin Choi, Maximilian Gorsky, Gunwoo Kim, and Sebastian Wiederrecht for valuable discussions.

References

  1. [1]S. Artmann, R. Weismantel, and R. Zenklusen, A strongly polynomial algorithm for bimodular integer linear programming, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 1206–1219, https://doi.org/10.1145/3055399.3055473.
  2. [2]É. Bonnet and Y. Chang, Max independent set remains np-hard when excluding a planar induced minor, arXiv preprint arXiv:2609.11285, (2026).arxiv.org/abs/2609.11285
  3. [3]E. Bonnet, J. Duron, C. Geniet, S. Thomassé, and A. Wesolek, Maximum independent set when excluding an induced minor: K₁ + K₂ and tC₃ ⊔ C₄, Algorithmica, 88 (2026), pp. Paper No. 16, 19, https://doi.org/10.1007/s00453-025-01356-2, https://doi.org/10.1007/s00453-025-01356-2.
  4. [4]M. Brianski, D. Kral, A. Lamaison, and X. Shu, Four-coloring Eulerian triangulations of the torus, arXiv preprint arXiv:2409.19165, (2024), https://doi.org/10.48550/arXiv.2409.19165, https://doi.org/10.48550/arXiv.2409.19165.
  5. [5]J. Bulian and A. Dawar, Graph isomorphism parameterized by elimination distance to bounded degree, Algorithmica, 75 (2016), pp. 363–382, https://doi.org/10.1007/s00453-015-0045-3, https://doi.org/10.1007/s00453-015-0045-3.
  6. [6]J. Bulian and A. Dawar, Fixed-parameter tractable distances to sparse graph classes, Algorithmica, 79 (2017), pp. 139–158, https://doi.org/10.1007/s00453-016-0235-7, https://doi.org/10.1007/s00453-016-0235-7.
  7. [7]E. W. Chambers, J. Erickson, and A. Nayyeri, Homology flows, cohomology cuts, SIAM Journal on Computing, 41 (2012), pp. 1605–1634, https://doi.org/10.1137/090766863, https://doi.org/10.1137/090766863.
  8. [8]M. Choi, M. Gorsky, G. Kim, C. McFarland, and S. Wiederrecht, Odd-cycle-packing-treewidth: On the maximum independent set problem in odd-minor-free graph classes, arXiv preprint arXiv:2511.10019, (2025).arxiv.org/abs/2511.10019
  9. [9]M. Choi, M. Gorsky, G. Kim, C. McFarland, and S. Wiederrecht, Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes, in 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), S. Bhattacharya, D. Nanongkai, M. Benedikt, and G. Puppis, eds., vol. 374 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2026, pp. 64:1–64:16, https://doi.org/10.4230/LIPIcs.ICALP.2026.64, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.64.
  10. [10]M. Chudnovsky, J. Codsi, D. Lokshtanov, M. Milanič, and V. Sivashankar, Tree independence number V. walls and claws, arXiv preprint arXiv:2501.14658, (2025), https://doi.org/10.48550/arXiv.2501.14658, https://doi.org/10.48550/arXiv.2501.14658.
  11. [11]M. Chudnovsky, P. Gartland, S. Hajebi, D. Lokshtanov, and S. SpirkI, Tree independence number IV. even-hole-free graphs, in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2025, pp. 4444–4461, https://doi.org/10.1137/1.9781611978322.151, https://doi.org/10.1137/1.9781611978322.151.
  12. [12]M. Chudnovsky, S. Hajebi, and N. Trotignon, Tree independence number III. thetas, prisms and stars, Journal of Graph Theory, (2024), https://doi.org/10.1002/jgt.70088, https://doi.org/10.1002/jgt.70088.
  13. [13]M. Conforti, S. Fiorini, T. Huynh, G. Joret, and S. Weltge, The stable set problem in graphs with bounded genus and bounded odd cycle packing number, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 2896–2915, https://doi.org/10.1137/1.9781611975994.176, https://doi.org/10.1137/1.9781611975994.176.
  14. [14]C. Dallard, M. Milanič, and K. Štorgel, Treewidth versus clique number. II. Tree-independence number, J. Combin. Theory Ser. B, 164 (2024), pp. 404–442, https://doi.org/10.1016/j.jctb.2023.10.006, https://doi.org/10.1016/j.jctb.2023.10.006.
  15. [15]C. Dallard, M. Milanič, and K. Štorgel, Treewidth versus clique number. III. tree-independence number of graphs with a forbidden structure, Journal of Combinatorial Theory, Series B, 167 (2024), pp. 338–391, https://doi.org/10.1016/j.jctb.2024.03.005, https://doi.org/10.1016/j.jctb.2024.03.005.
  16. [16]M. Devos, L. Goddyn, B. Mohar, D. Vertigan, and X. Zhu, Coloring-flow duality of embedded graphs, Transactions of the American Mathematical Society, 357 (2005), pp. 3993–4016, https://doi.org/10.1090/S0002-9947-04-03544-5, https://doi.org/10.1090/S0002-9947-04-03544-5.
  17. [17]E. Eiben, R. Ganian, T. Hamm, and O.-J. Kwon, Measuring what matters: a hybrid approach to dynamic programming with treewidth, J. Comput. System Sci., 121 (2021), pp. 57–75, https://doi.org/10.1016/j.jcss.2021.04.005, https://doi.org/10.1016/j.jcss.2021.04.005.
  18. [18]D. Eppstein, Diameter and Treewidth in Minor-Closed Graph Families, Algorithmica, 27 (2000), pp. 275–291, https://doi.org/10.1007/S004530010020.
  19. [19]D. Eppstein, Dynamic generators of topologically embedded graphs, in Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, 2003, pp. 599–608.DOI
  20. [20]G. Fijavž and A. Nakamoto, Odd complete minors in even embeddings on surfaces, Discrete Mathematics, 339 (2016), pp. 165–178, https://doi.org/10.1016/j.disc.2015.07.015, https://doi.org/10.1016/j.disc.2015.07.015.
  21. [21]S. Fiorini, G. Joret, S. Weltge, and Y. Yuditsky, Integer programs with bounded subdeterminants and two nonzeros per row, Journal of the ACM, 72 (2025), pp. 1–50, https://doi.org/10.1145/3695985, https://doi.org/10.1145/3695985.
  22. [22]M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math., 32 (1977), pp. 826–834, https://doi.org/10.1137/0132071, https://doi.org/10.1137/0132071.
  23. [23]J. Geelen, B. Gerards, B. Reed, P. Seymour, and A. Vetta, On the odd-minor variant of Hadwiger’s conjecture, Journal of Combinatorial Theory, Series B, 99 (2009), pp. 20–29, https://doi.org/10.1016/j.jctb.2008.03.006.
  24. [24]J. Geelen, B. Gerards, and G. Whittle, Solving Rota’s conjecture, Notices Amer. Math. Soc., 61 (2014), pp. 736–743, https://doi.org/10.1090/noti1339, https://doi.org/10.1090/noti1339.
  25. [25]J. Geelen, O.-J. Kwon, R. McCarty, and P. Wollan, The Grid Theorem for vertex-minors, Journal of Combinatorial Theory, Series B, 158 (2023), pp. 93–116, https://doi.org/10.1016/j.jctb.2020.08.004.
  26. [26]A. M. H. Gerards, A min-max relation for stable sets in graphs with no odd-K4, Journal of Combinatorial Theory, Series B, 47 (1989), pp. 330–348, https://doi.org/10.1016/0095-8956(89)90032-4, https://doi.org/10.1016/0095-8956(89)90032-4.
  27. [27]A. M. H. Gerards, Graphs and polyhedra. Binary spaces and cutting planes, vol. 73 of CWI Tract, Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1990.
  28. [28]J. P. Gollin, M. Gorsky, M. Hatzel, K. Hendrey, T. Huynh, C. McFarland, M. Sokolowski, S. Wiederrecht, and P. Wollan, An Erdős-Pósa theorem for cycles and faces of distinct lengths, 2026, https://doi.org/10.48550/arXiv.2607.06869, https://doi.org/10.48550/arXiv.2607.06869, https://arxiv.org/abs/2607.06869.
  29. [29]J. P. Gollin and S. Wiederrecht, Structure and algorithms for graphs excluding grids with small parity breaks as odd-minors, Apr. 2023, https://arxiv.org/abs/2304.04504.
  30. [30]J. L. Gross and T. W. Tucker, Topological graph theory, Courier Corporation, 2001.
  31. [31]M. Grötschel, L. Lovász, and A. Schrijver, Polynomial algorithms for perfect graphs, in North-Holland mathematics studies, vol. 88, Elsevier, 1984, pp. 325–356.DOI
  32. [32]J. Håstad, Clique is hard to approximate within \(1-\epsilon\), in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 627–636, https://doi.org/10.1109/SFCS.1996.548522, https://doi.org/10.1109/SFCS.1996.548522.
  33. [33]J. Hutchinson, R. B. Richter, and P. Seymour, Colouring Eulerian triangulations, Journal of Combinatorial Theory, Series B, 84 (2002), pp. 225–239, https://doi.org/10.1006/jctb.2001.2074, https://doi.org/10.1006/jctb.2001.2074.
  34. [34]J. P. Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, Journal of Combinatorial Theory, Series B, 65 (1995), pp. 139–155, https://doi.org/10.1006/jctb.1995.1047, https://doi.org/10.1006/jctb.1995.1047.
  35. [35]T. Huynh, The linkage problem for group-labelled graphs, PhD thesis, University of Waterloo, 2009.
  36. [36]L. Jaffke, L. Morelle, I. Sau, and D. M. Thilikos, Dynamic programming on bipartite tree decompositions, Journal of Computer and System Sciences, (2025), p. 103722, https://doi.org/10.1016/j.jcss.2025.103722, https://doi.org/10.1016/j.jcss.2025.103722.
  37. [37]B. M. P. Jansen and J. J. H. de Kroon, FPT algorithms to compute the elimination distance to bipartite graphs and more, in Graph-theoretic concepts in computer science, vol. 12911 of Lecture Notes in Comput. Sci., Springer, Cham, [2021] ©2021, pp. 80–93, https://doi.org/10.1007/978-3-030-86838-3_6.
  38. [38]B. M. P. Jansen, J. J. H. de Kroon, and M. Włodarczyk, Vertex deletion parameterized by elimination distance and even less, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, New York, NY, USA, 2021, ACM, p. 1757–1769, https://doi.org/10.1145/3406325.3451068.
  39. [39]T. R. Jensen and B. Toft, Graph coloring problems, John Wiley & Sons, 2011.
  40. [40]K.-I. Kawarabayashi, B. Mohar, and B. Reed, A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width, in 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2008, pp. 771–780, https://doi.org/10.1109/FOCS.2008.53.
  41. [41]S. Khot, Improved inapproximability results for maxclique, chromatic number and approximate graph coloring, in Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 2001, pp. 600–609, https://doi.org/10.1109/SFCS.2001.959936.
  42. [42]T. Korhonen, Grid induced minor theorem for graphs of small degree, Journal of Combinatorial Theory, Series B, 160 (2023), pp. 206–214, https://doi.org/10.1016/j.jctb.2023.01.002, https://doi.org/10.1016/j.jctb.2023.01.002.
  43. [43]D. Král’, B. Mohar, A. Nakamoto, O. Pangrác, and Y. Suzuki, Coloring Eulerian triangulations of the Klein bottle, Graphs and Combinatorics, 28 (2012), pp. 499–530, https://doi.org/10.1007/s00373-011-1063-9, https://doi.org/10.1007/s00373-011-1063-9.
  44. [44]D. Král’ and R. Thomas, Coloring even-faced graphs in the torus and the Klein bottle, Combinatorica, 28 (2008), pp. 325–341, https://doi.org/10.1007/s00493-008-2315-z, https://doi.org/10.1007/s00493-008-2315-z.
  45. [45]M. Kühn, L. Sauermann, R. Steiner, and Y. Wigderson, Disproof of the Odd Hadwiger Conjecture, CoRR, abs/2512.20392 (2025), https://doi.org/10.48550/arXiv.2512.20392, https://arxiv.org/abs/2512.20392.
  46. [46]C.-H. Liu and Y. Yoo, Disjoint paths problem with group-expressable constraints, in Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, New York, NY, USA, 2025, Association for Computing Machinery, p. 1933–1943, https://doi.org/10.1145/3717823.3718109, https://doi.org/10.1145/3717823.3718109.
  47. [47]V. V. Lozin and M. Milanič, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Journal of Discrete Algorithms, 6 (2008), pp. 595–604, https://doi.org/10.1016/j.jda.2008.04.001, https://doi.org/10.1016/j.jda.2008.04.001.
  48. [48]R. McCarty, Local Structure for Vertex-Minors, doctoral Thesis, University of Waterloo, Waterloo, Ontario, Canada, 2021.
  49. [49]M. Metsidik, Eulerian and even-face graph partial duals, Symmetry, 13 (2021), p. 1475, https://doi.org/10.3390/sym13081475, https://doi.org/10.3390/sym13081475.
  50. [50]M. Metsidik and X. Jin, Eulerian and even-face ribbon graph minors, Discrete Mathematics, 343 (2020), p. 111953, https://doi.org/10.1016/j.disc.2020.111953, https://doi.org/10.1016/j.disc.2020.111953.
  51. [51]G. J. Minty, On maximal independent sets of vertices in claw-free graphs, Journal of Combinatorial Theory, Series B, 28 (1980), pp. 284–304, https://doi.org/10.1016/0095-8956(80)90074-X.
  52. [52]B. Mohar, Face-width of embedded graphs, Math. Slovaca, 47 (1997), pp. 35–63. Graph theory (DOnovaly, 1994).
  53. [53]B. Mohar, A linear time algorithm for embedding graphs in an arbitrary surface, SIAM Journal on Discrete Mathematics, 12 (1999), pp. 6–26, https://doi.org/10.1137/S089548019529248X, https://doi.org/10.1137/S089548019529248X.
  54. [54]B. Mohar, Coloring Eulerian triangulations of the projective plane, Discrete mathematics, 244 (2002), pp. 339–343, https://doi.org/10.1016/S0012-365X(01)00092-9, https://doi.org/10.1016/S0012-365X(01)00092-9.
  55. [55]B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, 2001.
  56. [56]S. Morell, I. Seidel, and S. Weltge, Minimum-cost integer circulations in given homology classes, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2021, pp. 2725–2739, https://doi.org/10.1137/1.9781611976465.162, https://doi.org/10.1137/1.9781611976465.162.
  57. [57]G. L. Nemhauser and L. E. Trotter Jr, Properties of vertex packing and independence system polyhedra, Mathematical programming, 6 (1974), pp. 48–61.DOI
  58. [58]S.-I. Oum, Rank-width and vertex-minors, J. Combin. Theory Ser. B, 95 (2005), pp. 79–100, https://doi.org/10.1016/j.jctb.2005.03.003, https://doi.org/10.1016/j.jctb.2005.03.003.
  59. [59]S. Poljak, A note on stable sets and colorings of graphs, Comment. Math. Univ. Carolinae, 15 (1974), pp. 307–309.
  60. [60]B. Reed, K. Smith, and A. Vetta, Finding odd cycle transversals, Oper. Res. Lett., 32 (2004), pp. 299–301, https://doi.org/10.1016/j.orl.2003.10.009, https://doi.org/10.1016/j.orl.2003.10.009.
  61. [61]B. A. Reed, Mangoes and Blueberries, Combinatorica, 19 (1999), pp. 267–296, https://doi.org/10.1007/s004930050056.
  62. [62]Robert D. Barish, An FPT Algorithm for Maximum-Weight Independent Set in Embedded Graphs, in Lean 4. Palomar, PALOMAR-2026-10-23-000015 v1, 2026, https://palomar-registry.org/entry?id=PALOMAR-2026-10-23-000015&version=1.
  63. [63]N. Robertson and P. D. Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory, Series B, 41 (1986), pp. 92–114, https://doi.org/10.1016/0095-8956(86)90030-4.
  64. [64]V. N. Shevchenko, Qualitative topics in integer linear programming, American Mathematical Soc., 1996.DOI
  65. [65]S. Spirkl, Open problems for the Barbados Graph Theory Workshop 2018. Problem list, Barbados Graph Theory Workshop, 2018, https://web.math.princeton.edu/~pds/barbados18/openproblems2018.pdf (accessed 2026-06-28). See Problem 8, attributed to Stéphan Thomassé.
  66. [66]R. Steiner, Asymptotic equivalence of Hadwiger’s conjecture and its odd minor-variant, Journal of Combinatorial Theory, Series B, 155 (2022), pp. 45–51, https://doi.org/10.1016/j.jctb.2022.02.002.
  67. [67]S. Tazari, Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs, Theoret. Comput. Sci., 417 (2012), pp. 95–107, https://doi.org/10.1016/j.tcs.2011.09.014, https://doi.org/10.1016/j.tcs.2011.09.014.
  68. [68]N. Yolov, Minor-matching hypertree width, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2018, pp. 219–233, https://doi.org/10.1137/1.9781611975031.16, https://doi.org/10.1137/1.9781611975031.16.
  69. [69]T. Zaslavsky, Signed graphs, Discrete Applied Mathematics, 4 (1982), pp. 47–74, https://doi.org/10.1016/0166-218X(82)90033-6, https://www.sciencedirect.com/science/article/pii/0166218X829000336.

Paper details

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

views · 2

downloads · 0

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

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents