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 and a weighting 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 for every constant . 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 be fixed. There exists a polynomial time algorithm that, given a graph together with a cellular embedding in a surface of Euler genus with at most vertex-disjoint odd faces and vertex weights , finds a maximum weight independent set in in time for some computable function .
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 be fixed. There exists a polynomial time algorithm that, given a planar graph with at most odd faces, finds a maximum weight independent set in .
Before our work, the only cases that were known to be polynomially solvable were (bipartite graphs) and (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 with two nonzero entries per row is the edge-vertex incidence matrix of a signed graph if is supported on the incidence matrix of 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 with at most 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 be fixed. There exists a polynomial time algorithm to solve the integer program
when is the edge-vertex incidence matrix of a signed graph with a given cellular embedding in a surface of Euler genus with at most vertex-disjoint odd faces, and .
Our results are motivated by the study of odd-minors. A graph is an odd-minor of a graph if can be obtained from 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 corresponds naturally to a cycle in of the same parity. For example, -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 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 ). 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 be an odd-minor closed class of graphs. Then Maximum Weighted Independent Set admits a polynomial-time algorithm on if and only if 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 -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].
Related work
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 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 if and only if it forbids as an odd-minor. Reed [61] showed that a graph has bounded OCT if and only if it forbids and the Escher wall of order 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 in absolute value admits a polynomial-time algorithm when 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 denote the class of bipartite graphs. Examples of such parameters are elimination distance to [5, 6] and -treewidth [17, 37, 38], which are the minimum such that a graph has a set with and with the torso of in having treedepth (in the case of elimination distance to ) or treewidth (in the case of -treewidth) at most . Another example is -blind-treewidth [29], which measures the largest treewidth over all non-bipartite blocks of . Jaffke, Morelle, Sau, and Thilikos [36] introduced bipartite treewidth, which gives a proper generalization of both -blind-treewidth and -treewidth. A graph has bipartite treewidth at most if it admits a tree decomposition such that every bag has OCT at most 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 if it admits a tree decomposition such that all adhesions have size at most and all bags have OCP at most , 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 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 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 -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 -odd-minor-free graph classes for every graph . 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 for every [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 -induced-minor-free graphs for every planar graph . 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 , there exists an algorithm running in time for some computable function which takes as input a graph and either returns an even-faced embedding in a surface of genus 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 is given as input in Theorem 1.1. Even a runtime of the form 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 be fixed. There exists an algorithm that, given a graph together with a cellular even-face embedding in a surface of Euler genus and vertex weights , finds a maximum weight independent set in in time for some computable function .
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 be fixed. There exists an algorithm that, given a directed graph together with a cellular embedding in a surface of Euler genus , edge costs , and an integer circulation on , finds a minimum cost integer circulation homologous to in time for some computable function .
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 . Recall that we consider the following problem.
Problem 2.1. Given a graph with a cellular embedding in a surface of Euler genus with at most vertex-disjoint odd faces and vertex weights , compute a maximum -weight independent set in .
We first reduce to the case when 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 vertices to reduce to the case when 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 with a cellular even-faced embedding in a surface of Euler genus and vertex weights , compute a maximum -weight independent set in .
In Subsection 4.2 we apply some preprocessing to reduce to a more structured instance. We summarize the desired properties below. (The notation is defined in Subsection 3.1 below, together with other preliminaries.)
Definition 2.3. Let be a graph. A vertex weighting is called edge-induced if there is a nonnegative edge weighting such that for every vertex .
Definition 2.4. A weighted graph is said to satisfy the standard assumptions if is 2-connected, non-bipartite, and even-faced embedded in a surface of Euler genus with facewidth at least 2, and the weighting is edge-induced.
Because our weights are edge-induced by , 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 is the edge-vertex incidence matrix of , then is called a slack vector if there exists such that . For a closed walk in and , we define
Conforti et al. showed that is a slack vector if and only if for all even closed walks and for all odd closed walks. We show that when is 2-connected and non-bipartite, there is a collection of 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 satisfying the standard assumptions, non-negative edge costs , and a collection of cycles with exactly one of them odd, minimize over all satisfying for every even cycle and for the unique odd cycle . Furthermore, is such that the above constraints exactly characterize the slack vectors .
In the work of Conforti et al. [13], the authors then find a special orientation of the dual graph such that the solution can be interpreted as a circulation in this orientation. This has the advantage that the constraint for facial cycles of is implied by flow conservation in this dual graph. The type of orientation needed is an alternating orientation. An orientation of an embedded graph is called alternating if for each vertex , edges alternately leave and enter in the local cyclic order of edges incident to . Finding such an alternating orientation of is only possible in the setting of [13] (see Lemma 3.3).
To get around this problem, we consider the derived graph of (for a particular signing of ), see § 5. The derived graph is constructed as follows. The graph is equipped with an embedding scheme , where gives the local cyclic orientation around each vertex and encodes whether an edge is “twisted”, see Subsection 3.3. The vertex set of consist of two copies of , and we denote for each vertex its two copies by , . For each edge with , one adds two edges in between opposite copies of and , that is, one adds the edges and . For each edge with , one adds two edges in between the same copies of and , that is, one adds the edges and . It turns out that embeds in a surface of genus , and that its dual has an alternating orientation. We defer the reader to § 5 for a topological construction of .
We now have an alternating orientation of . We map circulations to vectors via the natural projection where is given by for the copies of . Now flow conservation at each vertex in implies for every facial cycle . By Euler’s formula, it suffices to add at most extra constraints for odd cycle and for even cycles . Somewhat surprisingly, we show that an optimal solution to Problem 2.5 can be found as the image of a minimum cost circulation in satisfying the above constraints, and hence we reduce to the following problem in Theorem 6.3.
Problem 2.6. Let be an alternating orientation of for satisfying the standard assumptions, and let be cycles in where is odd and are even. Find a minimum -cost nonnegative integer circulation in satisfying the linear constraints
for every even cycle , and
.
Finally, in § 7, we show that the constraints on the circulation in only depend on the -homology of (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 and to denote the vertex and edge set of a graph respectively, and we use to denote the set of edges incident to . We will often identify a function with a vector , and for instance use the notation to denote the -th entry of . We use the notation .
In Subsection 4.1 we will need the following definition.
Definition 3.1. A tree-decomposition of a graph is a pair where is a tree and is such that
for every edge , there exists such that both ends of are contained in , and
for every , the set induces a connected, non-empty subtree of .
The width of a tree decomposition is . The treewidth of a graph is the minimum width over all tree decompositions of . We call the bag of .
Signed graphs
To understand our algorithm it will be most convenient to work with signed graphs. A signed graph is a pair where is a graph and assigns a parity to every edge. The parity of a cycle in is given by where indices are taken modulo , and the sum is computed in . In the context of this paper we typically associate an unsigned graph with the signed graph where maps every edge to .
A signed graph is obtained from by shifting at if for all and for all . More generally, is obtained from by shifting if is obtained from 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 contains another signed graph as a minor if can be obtained from 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: contains as an odd-minor if and only if the signed graph contains the signed graph as a minor.
In the below, the parity of a face in a signed graph is the sum of over all edges on its boundary, where edges that appear twice along the boundary are counted twice. The parity of a face in an unsigned graph is the parity of the face in .
Lemma 3.2. Let denote the class of graphs that admit an embedding in a surface with at most vertex-disjoint odd faces. Then is odd-minor-closed.
Proof. This follows from the more general fact that the class of signed graphs with an embedding in with at most vertex-disjoint odd faces is minor-closed. Indeed, if and only if . Then for any odd-minor of , is a minor of , and hence is in .
We then simply note the following properties. Clearly shifting, deleting edges, deleting vertices, and contracting even edges leaves the signed graph embeddable in , 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 is a compact 2-dimensional manifold without boundary. We let be the surface obtained by cutting disjoint open disk from the sphere and gluing handles and crosscaps to the boundaries of these disks. By the classification theorem for surfaces, every surface is homeomorphic to for some and . If the surface is said to be orientable, otherwise the surface is said to be non-orientable. The Euler genus of a surface is .
A simple closed curve in 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 in is said to be contractible if some component of is an open disk whose boundary is . Otherwise we say is non-contractible.
An embedding of a graph in is a map from vertices of to distinct points of and edges of to internally disjoint simple open curves in between the image of its endpoints. We use to denote the union of all points and curves in the image of . The faces of an embedded graph are the connected components of , and we denote the set of faces by . If every face is homeomorphic to an open disk, then we say is a cellular embedding.
A curve in is -normal if it only meets in vertices. If is not the sphere, the facewidth of the embedded graph is the minimum number of vertices intersected by a -normal, non-contractible, simple closed curve in . Facewidth is not defined for graphs embedded in the sphere. If is 2-connected and cellularly embedded in with facewidth at least 2, then the boundary of each face is a cycle in [55 Proposition 5.5.11].
If is connected and cellularly embedded in a surface of Euler genus , then
Given a cycle in a graph with embedding in , we say that is 1-sided (resp. 2-sided) if the simple closed curve is 1-sided (resp. 2-sided).
A cellular embedding of a graph on a surface is determined by its embedding scheme where associates to each vertex of a cyclic ordering of its incident edges, which one thinks of as the “clockwise ordering” of edges around a vertex, and takes value 1 if and only if the orientation given by 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 , we first suppress degree 2 vertices to get a multigraph and we define the embedding scheme as above, where every edge incident to a vertex of degree 1 may have an arbitrary label. Now for each edge of obtained by suppressing degree 2 vertices along a path in , we assign the value of for edges such that the total -weight of is equal to . This defines an embedding scheme for . We note a cycle in is one-sided if and only if it is odd with respect to . All embeddings in this paper will be stored as embedding schemes for algorithmic purposes.
Note that if one reverses the orientation of at a vertex and adds 1 (over ) to the label for all non-loop edges , then this defines the same embedding. We say an embedding scheme is obtained from by shifting at if it is obtained in this way. We say that two embeddings and of a graph are (shifting) equivalent if is obtained from by a sequence of shiftings at vertices. Note that if and are shifting equivalent, then the signed graph is obtained from by shifting.
Given an embedding scheme of a graph , we can naturally define the set of facial walks as walks which, at every vertex , choose the next edge in the cyclic ordering with a direction that swaps whenever the traversed edge has .
We are now equipped to say exactly when the dual of a graph has an alternating orientation.
Lemma 3.3. Let be cellularly embedded in a surface such that the boundary of every face is a cycle in . Then the following are equivalent.
admits an alternating orientation,
A cycle in is odd if and only if it is one-sided,
The constraints are not linearly independent.
Proof. Consider an embedding scheme for . Such an embedding satisfies that the odd cycles are exactly the one-sided cycles if and only if is shifting equivalent to . That is, we have a local orientation around each vertex such that for every edge, the orientations of its ends disagree. We may then orient each facial cycle of to be a directed cycle agreeing with the orientation of ; such an orientation is an alternating orientation of . See Figure 3.1 (see also [13 Lemma 17]).
Figure 3.1. The graph is shown with dashed edges, and circular arrows displaying the local orientation . Note that neighboring local orientations disagree, which gives an alternating orientation of the dual graph depicted with the solid black arcs.
Conversely, suppose admits an alternating orientation. Then each facial cycle of is a directed cycle in this orientation. This naturally gives a local orientation around the corresponding vertex in , and these orientations have the property that for any edge of , the orientation of its ends disagree. Thus the first two items are equivalent.
Now suppose admits an alternating orientation. Then, for each facial cycle corresponding to , sign its edges such that edges leaving get a positive sign and edges entering get a negative sign. We can possibly negate to match this signing, and summing this up over every facial cycle gives a linear dependence between for facial cycles .
Conversely, suppose that there exists some linear dependence among . Write the constraints as , where . Note the support of is the incidence matrix of . By assumption, there is some nonzero vector such that . Since is connected and , it must be that is nonzero in every entry. Since has two nonzero entries per column, we may assume by scaling . By multiplying each row of by , we may assume . The new matrix has two nonzero entries per column, and every column contains a and . Then defines an alternating orientation of (recall that the rows are scalings of ).
Homology and even-faced embeddings
Let be an embedded signed graph. Given a face with facial walk , the face’s parity is given by . (We define the parity of a face in an unsigned embedded graph by identifying the unsigned graph with the signed graph .) We say a face is even or odd if its parity is or in respectively. We say the embedding is even-faced if no odd cycle bounds a disk in . If the embedding is cellular, this is equivalent to requiring that every face is even.
Let be a directed graph cellularly embedded in a surface . Two circulations are said to be -homologous if is a linear combination of facial circulations with integer coefficients. The first homology group of over the integers, denoted , is the quotient group of all integer circulations in by the subgroup of all circulations which are -homologous to the zero circulation. We note that the resulting group does not depend on our choice of . It is well known that if is orientable of Euler genus then , and if is non-orientable of Euler genus then .
When is a signed graph with an even-faced cellular embedding in a surface , the parity of a cycle only depends on the “-homology” of the cycle. We now make this precise. Let be an arbitrary orientation of . We define the parity of an integer circulation in to be . Because is even-faced, the parity of any facial circulation is . Hence the parity of depends only on the -homology of (in fact, this defines a homomorphism ). Then, for any cycle in , the parity of is equal to the parity of a -circulation supported on . Hence the parity of depends only on the -homology of the corresponding circulation. In cases such as this when the direction of flow around does not matter, we may speak of the “-homology” of to mean the -homology of the corresponding circulation in an arbitrary orientation of .
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 . Let be a graph embedded on a surface of Euler genus . Then either there exist odd faces of whose boundaries are pairwise vertex-disjoint, or there exists a set of size at most such that every odd face contains some vertex in .
Moreover, there exists an algorithm running in time that finds either the faces or the set with the properties promised above.
We will skip the proof of the FPT algorithm which finds . It will become clear from the proof that this reduces to finding 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 . Let be a graph with treewidth at most embedded in a surface , and let be the boundaries of some collection of faces. Then either there exist vertex disjoint facial boundaries , or there exists a set of size at most hitting all .
Proof. Let be a tree decomposition of of width at most . For each , let be the subtree of induced by all bags containing a vertex of . That is, . We now show that either there exists vertex disjoint subtrees from our collection, or there exists a set $X \subseteq V(T) of size at most hitting all subtrees in our collection. We proceed by induction on . Clearly we may assume , and let be a leaf. If there exists a subtree in our collection consisting only of the vertex , then we apply induction to with the collection obtained from deleting all subtrees containing . If we obtain a packing of disjoint subtrees then we may add to the packing, and if we obtain a hitting set then we may add to the hitting set. If there is no such tree with vertex set equal to , then we delete from and from every subtree of our collection, and again the desired statement then follows by induction.
If we obtain the packing of disjoint subtrees , then the corresponding collection of facial boundaries are vertex disjoint. If we instead obtain the hitting set then the set is a hitting set of size at most hitting all facial boundaries .
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 whose boundaries are vertex disjoint. We may assume , otherwise we obtain the desired collection of faces. Now every other odd face shares some vertex with one of .
For each , let be the graph induced on the boundary of and all faces which share a vertex with . We first claim that has treewidth . Let be formed from by adding a vertex inside every face of which is also a face in and making incident to every vertex on the facial boundary of . We then note that has radius at most ; by definition every vertex is distance at most from . Eppstein [18 Theorem 2] proved that graphs of radius embedded in a surface of Euler genus have treewidth . Because is a subgraph of , we immediately obtain that has treewidth .
Now in each , we apply Lemma 4.2 to the collection of odd faces which are also faces of . We may assume each does not contain a packing of such odd faces, else we obtain a packing in . Thus we obtain a set of vertices hitting all such faces in . Then is the desired hitting set in .
Now suppose the graph is embedded on a surface of Euler genus with vertex-disjoint odd faces. By the above, there exists a set of at most vertices hitting all odd faces. We guess the intersection of a maximum independent set with . Call this intersection . Guessing increases the running time by a factor of which we assume to be constant. One would like to delete 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 and all neighbors of 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 .
Now, for each , may be contained in the boundary of many odd faces. However, because has weight , we may subdivide edges incident to with weight vertices without changing an optimal solution. We now show that, for each , we may subdivide incident edges in such a way that at most one of the faces containing on the boundary is odd after subdivision. By doing this one at a time for each vertex in , we reduce to an instance with at most odd faces which is cellularly embedded.
For each , we construct an auxiliary multigraph as follows, see Figure 4.1 for an illustration. is a subgraph of the dual consisting of all vertices and edges lying on the face of . That is, the vertex set of is the set of faces of with on their boundary. The edge set of is in bijection with , where each edge corresponds to an edge in between the faces containing . We note that is not necessarily a cycle as may appear multiple times on a facial walk in , and in fact may contain parallel edges or loops. However, we note that is connected. We let be the set of odd faces containing on their boundary. If is even, we let , otherwise we let be formed from by removing a single element. Because is connected, there exists a set which is a -join. That is, every vertex has odd -degree if and even -degree if . Then by subdividing the edges of which correspond to an edge in , we have that every face except possibly the single face in is even in the resulting graph.
Figure 4.1. The left and right images show the local structure in around vertex . The image in the center shows the subgraph . In this example, one has . The -join is shown in bold red.
We have now reduced to the case when is cellularly embedded in a surface of Euler genus with a constant number, say , of odd faces. Clearly 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 , 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 .
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 be a graph with an even-faced embedding in a surface of Euler genus . 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 is edge-induced if there is a nonnegative edge weighting such that for every vertex we have .
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 (and set for all incident edges) in order to preserve a cellular embedding.
Assumption 4.4. has minimum degree .
Proof. Clearly we may assume has no isolated vertices. Suppose contains a vertex of degree with single neighbour . Because weights are edge induced, . Without loss of generality we can assume that one of or will be picked in a maximum weight independent set (even if ). That is, will never be slack. Then we may delete and add to our final weight (in doing so, the weight of decreases by ). By repeating this at most 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. is non-bipartite.
Proof. It is well known that we can find a maximum weight independent set in in polynomial time if is bipartite.
We note the above implies is not embedded in the plane.
Assumption 4.6. is 2-connected and the embedding of has facewidth at least 2.
Proof. We will use that for any cellularly embedded graph , the faces of are all bounded by cycles if and only if 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 appearing on the boundary of a face , we define the -multiplicity of to be the number of times that appears on the facial walk of . We define the excess of to be the sum over the faces containing on their boundary of the -multiplicity of minus 1. We define the excess of to be the sum of the excess of every vertex. If 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 is bounded by .
We do the following for each face of . Consider a facial walk of , and suppose that some vertex appears twice on this facial walk. Let and be the vertices preceding and following on this facial walk respectively. Because is simple and does not contain vertices of degree 1, . We add a new vertex of weight 0 adjacent to and , and we embed in the face . By setting the cost of the edges and to be zero we preserve that the weights are edge induced, and clearly any optimal solution remains optimal. By adding the vertex we have divided the even face into two even faces, and the resulting graph has smaller excess than . 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 be a graph, and let denote its (edge-vertex) incidence matrix. Throughout this section, we assume that is connected, although the entire discussion easily generalizes to arbitrary graphs. Consider the set . This is an affine subspace of the edge space that we call the slack space. In fact, is a linear subspace of the edge space, since . Indeed, we have (the first is the all-one vector in the vertex space and the second the all-one vector in the edge space). Hence, letting and , we find , proving that . This also shows that for all . (We point out that the above arguments break in characteristic 2: it is important that we are working over and not say over .)
Our first lemma gives a characterization of that follows directly from the Fredholm alternative.
Lemma 4.7. The slack space is the set of all such that for all .
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 is a support-minimal element of . These are sometimes called minimal linear dependences between the columns of . 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 . Every can be written as a linear combination of elementary vectors. In fact, we can even say more.
Let denote a (column) basis of . This is a maximal set of linearly independent columns of , or equivalently a basis of the vector matroid . Every column of 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 is called the fundamental elementary vectors of with respect to . (By convention, we scale so that $\lambda(j)=-1, where is the label of the column that is not in the basis, and expressed in the basis.) Then, every element of can be written as a linear combination of the fundamental elementary vectors of with respect to .
We conclude the following. Let be any basis of . Then, the slack space is the set of all such that for all fundamental elementary vectors of with respect to .
Now, since is the vertex-edge incidence matrix of graph , the bases and circuits of , seen as subgraphs of , are easy to describe. Since we assume is connected, the bases of are either the spanning trees (in case is bipartite), or a maximal set of edges in which every component contains at most 1 odd cycle (in case 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 is not bipartite, then it contains a basis formed from a spanning, odd 1-tree. The circuits of 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 is a sequence where are vertices and are edges such that for each . The length of walk is . Walk is closed if . We call a cycle walk if it is closed and are distinct. We associate to walk the vector
Whenever is a closed even walk, we have . Moreover, every elementary vector of is the form , where 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 denote any basis of . Let denote the collection of even closed walks arising from fundamental circuits of with respect to . Hence, if is bipartite, and if is non-bipartite. The slack space is the set of all such that for all .
We call an even closed walk a circuit walk if is a walk around an even cycle or an odd bicycle. Also, we define the width of such a walk as 0 in case is an even cycle walk, or as the number of vertices on the connecting path in case is a walk around an odd bicycle.
Lemma 4.9. Let denote a circuit walk. If is 2-connected, then can be written as a linear combination of vectors where is an even cycle walk.
Proof. Let denote the width of . If , then there is nothing to prove. Suppose that . We show that can be written as the sum of two vectors where is a circuit walk of width at most . The result follows by induction on .
Suppose we have an even closed walk around an odd bicycle consisting of two odd cycles and a path between them. Let and be the ends of in and respectively (possibly, , since may be trivial). Since is 2-connected, we can find a path from to that is internally disjoint from the odd bicycle. Let and denote the ends of in and , respectively.
If , then we may find two even cycles and whose union is and whose intersection is . Let and be corresponding even cycle walks. We can choose and such that since the signs of and agree on and disagree on . Then .
Otherwise, (notice that this case can arise only when ). Let denote the subpath of from to . Then we can find an even cycle and an odd bicycle such that the union of and is and the intersection is . Again, let and be corresponding circuit walks, thus is an even cycle walk and is an odd bicycle walk of width at most . After possibly shifting one of and , we can ensure that the signs of and agree on and disagree on . Once more, we have . □
Together with Lemma 4.8, Lemma 4.9 implies that the slack space has a complete description in the edge space via (resp. ) linear constraints that correspond to even cycles, whenever is 2-connected and non-bipartite (resp. bipartite).
Next, consider the set . This is an affine lattice that we call the slack lattice. We call its elements slack vectors. Observe that is contained in the slack space . Clearly, . As stated in our next lemma, the converse inclusion holds whenever is bipartite, and when is non-bipartite adding a single parity constraint yields a complete description of .
Lemma 4.10. If is bipartite, then . If is non-bipartite, then , where is any walk around an odd cycle of .
Proof. First, assume that is bipartite, and let . Since is totally unimodular, there exists such that , showing that .
Second, assume that is non-bipartite. Fix some . We have to prove that has a solution if and only if .
Let denote the subgraph of traced by . Let denote any odd, spanning 1-tree containing (so is a basis). Consider the subsystem , where the subscript indicates restriction to rows corresponding to edges of . Since is non-bipartite, is invertible. We put in Hermite normal form. Assume that the elements of 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 such that
Since , we see that has a solution if and only if . Since , this occurs if and only if has an integer solution.
Among other things, Lemma 4.10 implies that (that is, is a lattice) if and only 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 , we define a linear form on by letting for . That is, we let .
Lemma 4.11. For every 2-connected graph , there exists a collection of cycle walks such that
If is non-bipartite, then contains a unique odd cycle walk. Moreover, can be constructed in polynomial time.
Proof. The statement follows from our three previous lemmas. To see that the collection can be computed in polynomial time, we start with a basis of where denotes the circuit walks coming from any odd, spanning 1-tree (or spanning tree , in case is non-bipartite). For each that is an odd bicycle walk, we perform at most updates as in the proof of Lemma 4.9. Each update finds two vectors which span . We remove from the basis and replace it with one of such that we keep a basis. At the end of this process, we obtain a basis of of the form , where is the resulting collection of even cycle walks. In case is non-bipartite, we pick any odd cycle walk and add it to .
Finally, we discuss bounds on and on the solutions to . We require that , which implies . It would be natural to also enforce , 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 is optimal. We call a slack vector feasible if .
Let and let satisfy for all . This last condition can be written . If and satisfy , then by multiplying on the left by (and letting and ), we get . Notice that .
Our next lemma states that finding a maximum independent set in with respect to vertex weights is equivalent to finding a minimum cost feasible slack vector subject to edge costs . Notice that, by what precedes, we have if and only if for solution pairs and .
Lemma 4.12 (Fiorini et al. [21], Lemma 32). Let be a connected, non-bipartite graph and let be vertex weights induced by edge costs . Given any pair with ,
one can compute in strongly polynomial time a pair such that and .
By the above we have reduced to Problem 2.5, restated below.
Problem 2.5. Given a graph satisfying the standard assumptions, non-negative edge costs , and a collection of cycles with exactly one of them odd, minimize over all satisfying for every even cycle and for the unique odd cycle . Furthermore, is such that the above constraints exactly characterize the slack vectors .
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 where , we associate a derived (signed) graph defined as follows. has vertex set . For each edge , we add the edges and to , and give these edges -label equal to . 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 , we call the vertices its copies in , and we call the underlying vertex of and . Similarly for each edge , we call the edges and in the copies of , and we call the edge the underlying edge of and .
In the case of a signed graph where every edge has label , the derived graph is also called a bipartite double cover. We note that for any signed graph , the derived graph has no odd cycles (with respect to ).
We will use that if has an even-faced embedding on a surface of bounded genus, then also embeds on a surface of bounded genus. Then we will find an alternating orientation of the dual and solve MIS on by solving a minimum cost circulation problem on with extra topological constraints.
Given an embedding scheme of , we can define an embedding scheme of , called the derived embedding, in the following way. Let be a vertex of with incident edges , and let be the corresponding underlying edges. Then we simply order the edges in to agree with the ordering of in . We set for the underlying edge of . We let be the surface defined by this derived embedding, and we call the derived surface. We note that if does not contain a -odd cycle, then will be two disjoint copies of , and will be disconnected.
Theorem 5.1 ([30 Theorem 4.1.1]). If is a signed graph containing a -odd cycle with a cellular embedding in a surface of Euler genus , then the derived graph embeds in a surface such that every even face of becomes two faces of the same length in , and every odd face of becomes a single face in of twice the length. In particular, if is connected, contains a -odd cycle, and has an even-faced embedding in , then the Euler genus of is .
By the above it is well defined to talk of the two “copies” of an even face in as they appear in the derived embedding of . We warn the reader that although every vertex of has two copies in the vertices of when has an even-faced embedding, it is not true that is the derived graph of . For instance if is such that every edge is odd, then is bipartite, but its dual may contain odd cycles whenever there is an odd degree vertex of . Yet the derived graph of is bipartite.
We also note the following.
Theorem 5.2 ([30 Theorem 4.1.4]). Let be a signed graph with embedding in , and let be the derived graph with derived embedding in . Then is non-orientable if and only if contains a 1-sided even cycle.
We now describe how to obtain the surface from in terms of surface cutting in order to provide the reader with geometric intuition. We first note that if the signed graph is obtained from by shifting at the vertex , then the derived graph of is isomorphic to a shifting of the derived graph of . The derived graph of can be obtained from the derived graph of by exchanging the labels of and 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 with an even-faced embedding in a surface , the parity of a cycle depends only on the -homology of the cycle in . Thus we can find a set of closed curves in such that a cycle is odd if and only if it crosses these curves an odd number of times. Then we can shift such that the odd edges are exactly the edges which cross these curves an odd number of times. The surface is formed from 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 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 are the following:
is embedded in a surface Euler genus with all faces even,
is non-bipartite,
the embedding has facewidth at least 2,
is 2-connected,
and the weight function 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 with an embedding scheme in a surface of Euler genus , we define the signed graph where for every edge . We note that also gives an even-faced embedding of because every face of is homeomorphic to a disk, and hence the -weight of every facial cycle is 0. We denote its derived signed graph by , and note that the label of every edge in the derived signed graph is given where is the derived embedding in . By construction is balanced, i.e., for every cycle we have that (over ). This implies that the -weight of every cycle is equal to its parity (in the usual sense), or in other words, a cycle in is odd if and only if it is one-sided.
By Theorem 5.1, the derived embedding is an embedding of on a surface of bounded genus. We take the dual , and by Lemma 3.3 there exists an orientation of which is alternating. That is, for every vertex , the edge incident to alternatively enter and leave in the cyclic ordering given by .
It could be the case that contains no odd cycles, that is, 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 is disconnected, and is formed from the disjoint union of two copies of . We then work instead directly with the graph instead of the derived graph, and we define to be an alternating orientation of . 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 when we are not in the degenerate case, and we note that the alternating orientation of is unique up to reversing every edge.
Lemma 6.1. Suppose we are not in the degenerate case. Then for every edge with copies , the edges are given opposite orientations by . That is, for where are the copies of and are the copies of in such that , we have .
Proof. Let be the derived embedding of , so in particular for every vertex its copies have the same cyclic ordering given by . As in Lemma 3.3, the orientation of is given by finding a shifting equivalent embedding scheme such that for every edge , and then cyclically orienting the faces of to match with the cyclic orientation . Thus it suffices to show that for each vertex with copies , the cyclic orientations given by disagree. Recall that , and it follows from the definition of that can be obtained from by shifting at every vertex in . Because the orientations given and agree and shifting swaps the orientation, the result follows.
Recall that we have some edge weighting . This naturally gives an edge weighting of (and hence of ) by giving each copy of the same edge weight as the underlying edge. We define a linear map such that entry of has value for the underlying edge of both . Then for any nonnegative integer circulation in , we associate the vector given by . That is, where are the two copies of . Note that the orientations of and will disagree in , but the flow does not cancel; both and are nonnegative. In the degenerate case we define to be the identity function.
We will eventually solve a minimum cost nonnegative circulation problem on and return the associated vector . However, we first need to add some extra constraints by the following procedure. Recall from Subsection 4.3 that is feasible if where is the incidence matrix of .
Lemma 6.2. Let satisfy the standard assumptions and let be the collection of cycles given in Problem 2.5. Then we can in polynomial time find a set of cycles where is an odd cycle and are even cycles for the Euler genus of such that is feasible if and only if
for every facial cycle ,
for every even cycle , and
.
Proof. Let for such that is the unique odd cycle in . Recall that is feasible if and only if and for all . We note that contains at least 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 of the faces. In fact, all constraints in 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 of the constraints given by the cycles as desired. We note that except in the degenerate case, it suffices to take only a collection . We will then add a linearly dependent constraint given by for notational convenience.
Each constraint corresponding to a cycle above immediately gives a linear constraint for an integer circulation of because we set as above. We then have the following problem.
Problem 2.6. Let be an alternating orientation of for satisfying the standard assumptions, and let be cycles in where is odd and are even. Find a minimum -cost nonnegative integer circulation in satisfying the linear constraints
for every even cycle , and
.
We now reduce Problem 2.5 to Problem 2.6.
Theorem 6.3. Let be a feasible solution to Problem 2.6. Then is a feasible solution to Problem 2.5 with the same objective value. Conversely there exists an optimal solution to Problem 2.5 such that for some feasible solution to Problem 2.6.
Proof. Let be a feasible solution to Problem 2.6. We first show that is a feasible solution to Problem 2.5. We proceed by Lemma 6.2. Consider a facial cycle in , and let be the associated vertices in that correspond to the two copies of in . Let be the edges of in cyclic order, and let be the two copies of for . Then because is an alternating orientation and by flow conservation at and we have
as desired. We also have for every even cycle and by assumption. Thus by Lemma 6.2, is feasible, and clearly has the same objective value as .
Now let be an optimal solution to Problem 2.5. By Lemma 4.12, we may assume that . We now construct a nonnegative integer circulation in such that . Let be the set of edges for which takes value 1. Let be the dual of , and for every vertex we locally assign or 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 has even degree. This assignment does not have to be consistent; it could be that has ends and assigns the value and assigns the value . Let us denote the local signing of by . For , let be the facial walk around the face in . Then implies . We will now construct a collection of closed walks in using only edges in such that each edge of is used exactly once over all walks in the collection.
We start at an arbitrary vertex incident to an edge of , and walk along an arbitrary edge of . Each time we enter a vertex , we look at the local signing of our edge at and exit through an edge of the opposite sign. If , then this is always possible because . We continue like this for as long as possible. In particular, we continue even if we again reach the starting vertex as long as there is an edge of the opposite sign from which to leave . If we ever get stuck, then it must be because we reached the starting vertex , 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 had , then the edges of traversed so far have alternating sum equal to 2, so there is some untraversed edge in with for which we may continue the walk.
We may not have used all of the edges of in the above closed walk. However we can repeat the above as many times as needed, only using new edges of in each walk, to obtain the desired collection of closed walks.
We note that for a vertex , the edges of traversed in our walk do not have to have strictly alternating signs with respect to . 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 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 in , which we now describe.
We now claim that each walk in our collection corresponds naturally to a closed walk in 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 of such that . Let be the first vertex of our walk with copies in , and by possibly reversing our walk we may assume that the first edge of our walk is oriented out of , and we can start our walk there. Then if we enter a vertex through a directed edge, the next edge of our walk will correspond to an edge directed out of because the orientation of is alternating. Thus the walk in corresponds to a walk respecting directions in , and it suffices to show that the walk in 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 , its two copies have different orientations in . Suppose towards contradiction that we end our walk at the copy of instead of . Then the first edge of our walk is oriented out of and the last edge is oriented into . However because the edges incident to and have opposite orientations, this implies that the first and last edge of our walk have the same local signing relative to , a contradiction.
Because satisfies for every even cycle and , we have that implies that 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 cellularly embedded on a surface of bounded genus with nonnegative costs and an integer circulation in , and finds a minimum-cost nonnegative integer circulation in that is -homologous to .
Theorem 7.2. Problem 2.6 can be solved in polynomial time.
Proof. For a nonnegative integer circulation in , we set . We first claim that depends only on the -homology of . Because is linear in , it suffices to show that if is a circulation consisting of a single unit of flow around a single face, then . Let be a circulation sending a single unit of flow around a face of corresponding to vertex . Let be the underlying vertex in , so is the indicator of . Then for each , the cycle either doesn’t include or includes two edges of which appear with opposite signs in . In either case we see that . Because either doesn’t include or includes two edges in , we also have as desired.
Because the feasibility of depends only on its -homology, we may guess the correct -homology of and compute a minimum cost circulation with that -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 -homology in order to apply Theorem 7.1. Let denote the Euler genus of .
By [56 Corollary 12, Proposition 18], we can efficiently compute a collection of vectors such that the entries of are bounded by 2 in absolute value for every , and two circulations of are homologous if and only if
for each if is orientable, or
and for all if is non-orientable.
We then define either as a vector in if is orientable, or as a vector in if is non-orientable. That is, defines an isomorphism from the first homology group of over the integers to or . By Theorem 6.3, there is an optimal solution to Problem 2.6 such that for . By definition of , we obtain that there exists an optimal solution . Because has entries bounded by 2 in absolute value for every , we have that has entries bounded by in absolute value (where if the first entry is in , there is no restriction on this entry). Let denote the set of all such , so .
It now suffices, for each , to compute a circulation with . Suppose we can find such an for each . Then we check whether . If so, we apply Theorem 7.1 to find a minimum cost nonnegative integer circulation homologous to , and we output the circulation of minimum cost over all such .
We now show how to compute an integer circulation with for each . We first compute a collection of cycles in which generate the first homology group of over the integers. This can be done by taking a spanning tree of and a spanning tree of 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 with respect to generate the fundamental group of [19 Lemma 3.2]. Because the first homology group of over the integers is the abelianization of its fundamental group, these cycles also generate the first homology group of over the integers. That is, by sending one unit of flow around these cycles in (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 such cycles, and let us denote them by .
Because generate the first homology group of , for each there exists an integer combination such that . We can solve for either by finding an integer solution to the linear system
in the case that is orientable, or by finding an integer solution to the linear system
where is interpreted as an element of in the case that is non-orientable. We may then set 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]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]É. 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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]D. Eppstein, Diameter and Treewidth in Minor-Closed Graph Families, Algorithmica, 27 (2000), pp. 275–291, https://doi.org/10.1007/S004530010020.
- [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]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]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]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]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]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]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]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]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]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]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]J. L. Gross and T. W. Tucker, Topological graph theory, Courier Corporation, 2001.
- [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]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]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]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]T. Huynh, The linkage problem for group-labelled graphs, PhD thesis, University of Waterloo, 2009.
- [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]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]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]T. R. Jensen and B. Toft, Graph coloring problems, John Wiley & Sons, 2011.
- [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]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]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]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]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]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]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]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]R. McCarty, Local Structure for Vertex-Minors, doctoral Thesis, University of Waterloo, Waterloo, Ontario, Canada, 2021.
- [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]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]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]B. Mohar, Face-width of embedded graphs, Math. Slovaca, 47 (1997), pp. 35–63. Graph theory (DOnovaly, 1994).
- [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]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]B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, 2001.
- [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]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]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]S. Poljak, A note on stable sets and colorings of graphs, Comment. Math. Univ. Carolinae, 15 (1974), pp. 307–309.
- [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]B. A. Reed, Mangoes and Blueberries, Combinatorica, 19 (1999), pp. 267–296, https://doi.org/10.1007/s004930050056.
- [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]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]V. N. Shevchenko, Qualitative topics in integer linear programming, American Mathematical Soc., 1996.DOI
- [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]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]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]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]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.




