{'fraction_non_alphanumeric': 0.05350277659120034, 'fraction_numerical': 0.012361170439982914, 'mean_word_length': 3.819480185280494, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computing the fully optimal spanning tree of an ordered bipolar directed graph

It has been previously shown by the authors that a directed graph on a linearly ordered set of edges (ordered graph) with adjacent unique source and sink (bipolar digraph) has a unique fully optimal spanning tree, that satisfies a simple criterion on fundamental cycle/cocycle directions. This result yields, for any ordered graph, a canonical bijection between bipolar orientations and spanning trees with internal activity 1 and external activity 0 in the sense of the Tutte polynomial. This bijection can be extended to all orientations and all spanning trees, yielding the active bijection, presented for graphs in a companion paper. In this paper, we specifically address the problem of the computation of the fully optimal spanning tree of an ordered bipolar digraph. In contrast with the inverse mapping, built by a straightforward single pass over the edge set, the direct computation is not easy and had previously been left aside. We give two independent constructions. The first one is a deletion/contraction recursion, involving an exponential number of minors. It is structurally significant but it is efficient only for building the whole bijection (i.e. all images) at once. The second one is more complicated and is the main contribution of the paper. It involves just one minor for each edge of the resulting spanning tree, and it is a translation and an adaptation in the case of graphs, in terms of weighted cocycles, of a general geometrical linear programming type algorithm, which allows for a polynomial time complexity.


Introduction
In a previous paper [5] (see also [8]), we showed that a directed graph − → G on a linearly ordered set of edges, with adjacent unique source and sink connected by the smallest edge (ordered bipolar digraph), has a unique remarkable spanning tree that satisfies a simple criterion on fundamental cycle/cocycle directions, and that we call the fully optimal spanning tree α( − → G ) of − → G . Associating bipolar orientations of an ordered graph with their fully optimal spanning trees provides a canonical bijection with spanning trees with internal activity 1 and external activity 0 in the sense of the Tutte polynomial [14]. It is a classical result from [15] that those two sets have the same size, also known as the β-invariant β(G) of the graph [3]. We call this bijection the uniactive bijection of G.
This bijection can be extended to all orientations and all spanning trees, yielding the active bijection, introduced in terms of graphs first in [5], and detailed next in [6], for which the present paper is a complementary companion paper. Beyond graphs, the general context of the active bijection is oriented matroids, as studied by the authors in a series of papers, even more detailed, notably [8][9][10][11]. See the introductions of [6] (or also [9]) for an overview, more information and references. The general purpose of these works is to study graphs (or hyperplane arrangements, or oriented matroids) on a linearly ordered set of edges (or ground set), under various structural and enumerative aspects.
In the present paper we address the problem of computing the fully optimal spanning tree. Its existence and uniqueness is a tricky combinatorial theorem, proved in [5,Theorem 4] (see also the companion paper [6, Section 4.1] for a short sum up in graphs, see also [8,Theorem 4.5] for a generalization and a geometrical interpretation in oriented matroids, see also [9,Section 5] for a summary of various interpretations and implications of this theorem). As recalled in Section 2.2, the inverse mapping, producing a bipolar orientation for which a given spanning tree is fully optimal, is very easy to compute by a single pass over the ordered set of edges. But the direct computation is complicated and it had not been addressed in previous papers. When generalized to real hyperplane arrangements, the problem contains and strengthens the real linear programming problem (as shown in [8], hence the name fully optimal). This "one way function" feature is a noteworthy aspect of the active bijection. Here, we give two independent constructions to compute the mapping, that is to compute the fully optimal spanning tree of an ordered bipolar digraph.
The first construction, in Section 3, is recursive, by deletion/contraction of the greatest element. Let us observe that it is usual to have some deletion/contraction constructions when the Tutte polynomial is involved, and that this construction fits a general framework involving all orientations and spanning trees, presented in [6,Section 6.4] and detailed in [11]. This construction of the mapping has a short statement and proof, and it can be used to efficiently build the whole bijection at once (i.e. all the images simultaneously, see Remark 3.5). So, it is satisfying for the structural understanding and for a global approach, but it is not satisfying in terms of computational complexity for building one single image as it involves an exponential number of minors.
The second construction, in Section 4, is more technical and is the main contribution of the paper. It is efficient from the computational complexity viewpoint because it involves only one minor for each edge of the resulting spanning tree, and it consists in searching, successively in each minor, for the smallest cocycle with respect to a linear ordering of the set of cocycles induced by a suitable weight function. This algorithm is an adaptation in the case of graphs (implicitly using that graphic matroids are binary) of a general geometrical construction obtained by elaborations on pseudo/real linear programming (in oriented matroids / real hyperplane arrangements). Briefly, the ordering of cocycles is a substitue for some multiobjective programming, where a vertex (geometrical counterpart of a cocycle) is optimized with respect to a sequence of objective functions (transformed here into weights on edges). By this way, the fully optimal spanning tree can be computed in polynomial time. See Remark 4.7 and the end of Section 4 for more discussion. See [10] for the general geometrical construction. See also [7] for a short formulation of the same algorithm in terms of real hyperplane arrangements. See [8] for the primary relations between the full optimality criterion and usual linear programming optimality (see also [4] in the uniform case).
In addition, let us recall from [5, Section 4] (see also [6,Section 4.1] for more details) that the bijection between bipolar orientations and their fully optimal spanning trees directly yields a bijection between cyclic-bipolar orientations (the strongly connected orientations obtained from bipolar orientations by reversing the source-sink edge) and spanning trees with internal activity 0 and external activity 1. Hence, the algorithms developed here can also be used for this second bijection. Let us mention that this framework involves a remarkable duality property, called the active duality, which is reflected in several ways. First, those two bijections are related to each other consistently with cycle/cocycle duality (that is oriented matroid duality, which extends planar graph duality, see [6,Section 4.1] in graphs, see also [8,Section 5], or [9, Section 5] for a complete overview). Second, this duality property can be seen as a strengthening of linear programming duality (see [8,Section 5]). Third, it is related to the equivalence of two dual formulations in the deletion/contraction construction (see Remark 3.7).
Lastly, it is important to point out that the two aforementioned constructions of the fully optimal spanning tree do not give a new proof of its existence and uniqueness: on the contrary, this crucial fundamental result is used to ensure the correctness of these two constructions.

Usual terminology and tools from oriented matroid theory
All graphs considered in this paper will be connected. They can have loops and multiple edges. A digraph is a directed graph, and an ordered graph is a graph G = (V, E) on a linearly ordered set of edges E. Edges of a directed graph are supposed to be directed or equally oriented. A directed graph will be denoted with an arrow, − → G , and the underlying undirected graph without arrow, G. The cycles, cocycles, and spanning trees of a graph G = (V, E) are considered as subsets of E, hence their edges can be called their elements. The cycles and cocycles of G are always understood as being minimal for inclusion. Given F ⊆ E, we denote G(F ) the graph obtained by restricting the edge set of G to F , that is the minor For e ∈ E, we denote − e − → G the digraph obtained by reversing the direction of the edge e in − → G . Let G be an ordered (connected) graph and let T be a spanning tree of G. For t ∈ T , the fundamental cocycle of t with respect to T , denoted C * G (T ; t), or C * (T ; t) for short, is the cocycle joining the two connected components of T \ {t}. Equivalently, it is the unique cocycle contained in (E \ T ) ∪ {t}. For e ∈ T , the fundamental cycle of e with respect to T , denoted C G (T ; e), or C(T ; e) for short, is the unique cycle contained in T ∪ {e}.
The technique used in the paper is close from oriented matroid technique, which notably means that it focuses on edges, whereas vertices are usually not used. Given an orientation − → G of a graph G, we will have to deal with directions of edges in cycles and cocycles of the underlying graph G, and, sometimes, to deal with combinations of cycles or cocycles. To achieve this, it is convenient to use some practical notations and classical properties from oriented matroid theory [2].
A signed edge subset is a subset C ⊆ E provided with a partition into a positive part C + and a negative part C − . A cycle, resp. cocycle, of G provides two opposite signed edge subsets called signed cycles, resp. signed cocycles, of − → G by giving a sign in {+, −} to each of its elements accordingly with the orientation − → G of G the natural way. Precisely: two edges having the same direction with respect to a running direction of a cycle will have the same sign in the associated signed cycles, and two edges having the same direction with respect to the partition of the vertex set induced by a cocycle will have the same sign in the associated signed cocycles. In particular, a directed cycle, resp. a directed cocycle, of − → G corresponds to a signed cycle, resp. a signed cocycle, all the elements of which are positive (and to its opposite, all the elements of which are negative). We will often use the same notation C either for a signed edge subset (formally a couple (C + , C − ), e.g. signed cycle) or for the underlying subset (C + ⊎ C − , e.g. graph cycle). When necessary, given a spanning tree T of G and an edge t ∈ T , resp. an edge e ∈ T , the fundamental cocycle C * (T ; t), resp. the fundamental cycle C(T ; e), induces two opposite signed cocycles, resp. signed cycles, of − → G ; then, by convention, the (signed) fundamental cocycle C * (T ; t), resp. the (signed) fundamental cycle C(T ; e), is considered to be the one in which t is positive, resp. e is positive.
The next three tools can be skipped in a first reading, as they will only be used in the proof of the main result of the paper, namely Theorem 4.3. First, let us recall the definition of the composition C • D between two signed edge subsets as the edge subset C ∪ D with signs inherited from C for the element of C and inherited from D for the elements of D \ C. We will use the classical orthogonality property between a cocycle D and a composition of cycles C of − → G , that is: Second, we recall that, given two cocycles C and C ′ of − → G , and an element f ∈ C ∪ C ′ which does not have opposite signs in C and C ′ , there exists a cocycle D obtained by elimination between C and C ′ preserving f such that f ∈ D, D + ⊆ C + ∪ C ′+ , D − ⊆ C − ∪ C ′− , and D contains no element of C ∩ C ′ having opposite signs in C and C ′ . This last property is a strengthening of the oriented matroid elimination property in the particular case of digraphs, a short proof of which is the following. Assume C defines the partition (C 1 , C 2 ) of the set of vertices, and C ′ defines the partition (C ′ 1 , C ′ 2 ), with a positive sign given to edges from C 1 to C 2 in C and from C ′ 1 to C ′ 2 in C ′ . Then the edges having opposite signs in C and C ′ are those joining , the cut defined by the partition (V ′ , E \ V ′ ) contains a cocycle answering the problem.
Third, we recall the following easy property. Let A, B ⊆ E with A ∩ B = ∅, such that the minor G/B\A is connected (or equivalently: G/B\A has the same rank as G/B). If D ′ is a cocycle of G/B\A, then there exists a unique cocycle D of G such that D ∩ B = ∅ and D \ A = D ′ . If the graphs are directedd then D has the same signs as D ′ on the elements of D ′ . We say that D ′ is induced by D, or that D induces D ′ .

Bipolar orientations and fully optimal spanning trees
We say that a directed graph − → G on the edge set E is bipolar with respect to p ∈ E if − → G is acyclic and has a unique source and a unique sink which are the extremities of p. In particular, if − → G consists in a single edge p which is an isthmus, then − → G is bipolar with respect to p. Equivalently, − → G is bipolar with respect to p if and only if every edge of − → G is contained in a directed cocycle and every directed cocycle contains p (for information: in other words, − → G has dual-orientation-activity 1 and orientation-activity 0, in the sense of [12], see [5,9] or [6, Section 2.4]). Another characterization is the following: is strongly connected (for information: those orientations − p − → G play an equivalent dual role, see the discussion at the end of Section 1 or [6, Section 4.1]).
be a directed graph, on a linearly ordered set of edges, which is bipolar with respect to the minimal element p of E. The fully optimal spanning tree α( • for all b ∈ T \ p, the directions (or the signs) of b and min(C * (T ; b)) are opposite in C * (T ; b); • for all e ∈ E \ T , the directions (or the signs) of e and min(C(T ; e)) are opposite in C(T ; e).
The existence and uniqueness of such a spanning tree is the main result of [5,8], along with the next theorem. Notice that a directed graph and its opposite are mapped onto the same spanning tree. We say that spanning tree T has internal activity 1 and external activity 0, or equivalently that T is uniactive internal, if: min(E) ∈ T ; for every t ∈ T \ min(E) we have t = min(C * (T ; t)); and for every e ∈ E \ T we have e = min(C(T ; e)).
In this paper, it is not necessary to define further the notion of activities of spanning trees, which comes from the theory of the Tutte polynomial (see [5,6,9]). For information (not used in the paper), the number of uniactive internal spanning trees of G does not depend on the linear ordering of E and is known as the β-invariant β(G) of G [3], while the number of bipolar orientations w.r.t. p does not depend on p and is equal to 2.β(G) [15].
Theorem 2.2 (Key Theorem [5,8]). Let G be a graph on a linearly ordered set of edges E with yields a bijection between all bipolar orientations of G w.r.t. p, with the same fixed orientation for p, and all uniactive internal spanning trees of G.
The bijection of Theorem 2.2 is called the uniactive bijection of the ordered graph G. For completeness of the paper (though not used thereafter), let us recall that, from the constructive viewpoint, this bijection was built in [5,8] by the inverse mapping, provided by a single pass algorithm over T and fundamental cocycles, or dually over E \ T and fundamental cycles. This algorithm is illustrated in [5, Figure 1], on the same example that we will use in Section 4. Equivalently, the inverse mapping can be obviously built by a single pass over E, choosing edge directions one by one so that the criterion of Definition 2.1 is satisfied. We recall this algorithm below (as done also in [8] and [6, Section 5.2]). The reader interested in a geometric intuition on the full optimality sign criterion can have a look at the equivalent definitions, illustrations and interpretations given in [8][9][10]. Orient e 1 arbitrarily. For k from 2 to n do if e k ∈ T then let a = min(C * (T ; e k )) orient e k in order to have a and e k with opposite directions in C * (T ; e k ) if e k ∈ T then let a = min(C(T ; e k )) orient e k in order to have a and e k with opposite directions in C(T ; e k ) Lastly, in the proof of the main result Theorem 4.3, we will use the following alternative characterization of the fully optimal spanning tree, equivalent to Definition 2.1 by [5,Proposition 3] or by [8, With the convention that an edge has a positive sign in its fundamental cycle or cocycle w.r.t. a spanning tree, with T = b 1 < b 2 < ... < b r , and with E \ T = {c 1 < ... < c n−r }, we have: Equivalently, as formulated in [8], in terms of compositions of signed subsets (see Section 2.1), the two latter properties can be formulated the following way:

Recursive construction by deletion/contraction
This section investigates a recursive deletion/contraction construction of the fully optimal spanning tree of an ordered bipolar digraph. See Section 1 for an outline. This construction is developed further in [6, Section 6] by giving deletion/contraction constructions involving all orientations and spanning trees 1 , and even more further in [11] by generalizing such constructions in oriented matroids. Let us mention that the construction, as it is formally stated below, extends directly to compute the fully otpimal basis of a bounded region of an oriented matroid, as addressed in [8].
Proof. First, let us recall that if a spanning tree of a directed graph satisfies the criterion of Definition 2.1, then this directed graph is necessarily bipolar w.r.t.its smallest edge. This is implied by [ If both − → G \ω and − → G /ω are bipolar w.r.t. p then: if e and ω have the same directions in C then α( or equivalently: Since it yields the same mapping α, then this second condition is actually equivalent to the first one, and so it can be used as an alternative. Note that the fact that these two conditions are equivalent is difficult and proved here in an indirect way (actually this fact is equivalent to the key result that α yields a bijection), see Remark 3.7.
Proof. Direct by Theorem 3.2 and Theorem 2.2 (bijection property). , that is O(2 n ). In contrast, the algorithm provided in Section 4 involves a linear number of minors (and yields a polynomial time algorithm, see Corollary 4.9). However, the algorithm of Theorem 3.2 is efficient in terms of computational complexity for building the images of all bipolar orientations of G at once, see Remark 3.5.
Remark 3.5 (building the whole bijection at once). By Corollary 3.3, the construction of Theorem 3.2 can be used to build the whole active bijection for G (i.e. the 1 − 1 correspondence between all bipolar orientations of G w.r.t. p with fixed orientation, and all spanning trees of G with internal activity 1 and external activity 0), from the whole active bijections for G/ω and G\ω. For each pair of bipolar orientations { − → G , − ω − → G }, the algorithm provides which "choice" is right to associate one orientation with the orientation induced in G/ω and the other with the orientation induced in G\ω. We mention that this "choice" notion is developed further in [6, Section 6] (and [11]) as the basic component for a deletion/contraction framework. This ability to build the whole bijection at once is interesting from a structural viewpoint, but also from a computational complexity viewpoint. Precisely, with |E| = n, the number of calls to the algorithm to build one image is O(2 n ) (see Remark 3.4), but the number of calls to the algorithm to build the O(2 n ) images of all bipolar orientations is O(2 n × 2 0 + 2 n−1 × 2 1 + . . . + 2 0 × 2 n + 2 1 × 2 n−1 ), that is just O(n.2 n ).
Remark 3.6 (linear programming). As the full optimality notion strengthens real linear programming optimality, the deletion/contraction algorithm of Theorem 3.2 corresponds to a refinement of the classical linear programming solving by constraint/variable deletion, see [4,10] (see also Remark 4.7).
Remark 3.7 (equivalence in Theorem 3.2). The equivalence of the two formulations in the algorithm of Theorem 3.2 is a deep result, difficult to prove if no property of the computed mapping is known. Here, to prove it, we implicitly use that α is already well-defined by Definition 2.1, and bijective for bipolar orientations (Key Theorem 2.2). But if one defines a mapping α from scratch as in the algorithm (with either one of the two formulations) and then investigates its properties, then it turns out that the above equivalence result is equivalent to the existence and uniqueness of the fully optimal spanning tree as defined in Definition 2.1. See [11] for precisions. This equivalence result is also related to the active duality property (see [6,Section 4.1], see also [8,Section 5] or [9, Section 5]). Roughly, in terms of graphs, from [5, Section 4], one defines a bijection between orientations obtained from bipolar orientations by reversing the source-sink edge and spanning trees with internal activity 0 and external activity 1. The full optimality criterion of Definition 2.1 can be directly adapted to these orientations with almost no change (see [6, Section 4.1]). Then, thanks to the equivalence of the two dual formulations in the above algorithm, one can directly adapt the above algorithm for this second bijection, with no risk of inconsistency. In an oriented matroid setting, this equivalence result also means that the same algorithm can be equally used in the dual, with no risk of inconsistency. These subtleties are detailed in [11].

Direct computation by optimization
This section gives a direct and efficient construction of the fully optimal spanning tree of an ordered bipolar digraph, in terms of an optimization based on a linear ordering of cocycles in a minor for each edge of the resulting spanning tree. It is completely independent of Section 3. It is an adaptation for graphs of a general construction by elaborations on linear programming given for oriented matroids in [10] (see Section 1 for an outline, see also [7] for a short statement in real hyperplane arrangements, note that this section could be directly generalized to regular matroids or totally unimodular matrices, and see Remark 4.7 for more information on these linear programming aspects). By this way, the computation of the fully optimal spanning tree can be made in polynomial time (Corollary 4.9). Also, we insist that we do not give here a new proof of the key Theorem 2.2: we use this result to assume that the fully optimal spanning tree exists, and then prove that our algorithm necessarily builds it. . Hence, as T is spanning, the partition into the sets A and B is completely determined by T and U , which implies the uniqueness of C. Now, let us prove the second claim.
which is a contradiction with the first claim for U = T ∩ C = T ∩ D.
• a subset of edges E, called ground set, such that the digraph − → G (E) is acyclic, • a subset of edges F , called objective set, linearly ordered, such that F ∪{p} is a spanning tree of G.
Given an optimizable digraph − → G as defined above, we define a linear ordering for the signed cocycles of − → G containing p as follows. Let C and D be two signed cocycles (see Section 2.1) of − → G containing p. By Lemma 4.1, since F ∪ {p} is a spanning tree of G, there exists an element of F that belongs to C∆D. Let f be the smallest element of F such that either f belongs to C∆D, or f belongs to C ∩ D and has opposite signs in C and D. If f is positive in C or negative in D then set C > D. If f is negative in C or positive in D then set D > C.
Equivalently, we set C > D if f is a positive element of C and not an element of D, or f is a positive element of C and a negative element of D, or f is not an element of C and a negative element of D, where f is the smallest possible element of F that allows for setting C < D or D < C by this way.
Equivalently, it is easy to see that this ordering is provided by the weight function w on signed cocycles of G defined as follows. Denote F = f 2 < ... < f r , and denote f i resp. f i the element with a positive resp. negative sign. For 1 ≤ i ≤ r, set w(f i ) = 2 r−i and w(f i ) = −2 r−i , and set w(e) = 0 if e ∈ E \ F . Then define the weight w(C) of a signed cocycle C as the sum of weights of its elements. The above linear ordering is given by: We define the optimal cocycle of − → G as the maximal signed cocycle of − → G containing p with positive sign, and inducing a directed cocycle of − → G (E). It exists since − → G (E) is acyclic, and it is unique since the ordering is linear. E) be an ordered bipolar digraph with respect to p = min(E). The fully optimal spanning tree α( − → G ) = p < t 2 < ... < t r is computed by the following algorithm.
(1) Initialize − → G as the optimizable digraph given by: • the infinity edge p • the ground set E • the objective set F = f 2 < ... < f r where p < f 2 < ... < f r is the smallest lexicographic spanning tree of − → G (and the linear ordering on F is induced by the linear ordering on E).
(2) For i from 2 to r do: (2.1) Let C opt be the optimal cocycle of − → G .
Scholia: C opt is actually the cocycle induced in the current digraph − → G by the fundamental cocycle of the element t i−1 (computed at the previous step, t 1 = p) of the fully optimal spanning tree of the initial digraph.
is actually the smallest edge not contained in fundamental cocycles of smaller edges of α( − → G ) because the fully optimal spanning tree α( − → G ) is internal uniactive.
and if p ′ ∈ F then let: Equivalently, F ′ is obtained by removing from F the greatest possible element such that the following property holds: as the optimizable digraph given by: in the middle, and the digraph − → G 3 = − → G 2/4\2 on the right. At each step: the bolder edge is p, the other bold edges form the set F , the directed edges within parenthesis are in F but no more in E, and the nearly invisible dashed edge is not part of the graph since it has been deleted from the previous F .  Figure 1 (the same as in [5]).
Example 4.4. Theorem 4.3 might seem rather technical in a pure graph setting, so let us first illustrate it on an example before proving it (see Remark 4.7 or [7,10] for geometrical interpretations). Let us apply the algorithm of Theorem 4.3 to the same example as in [5], where it illustrated the inverse algorithm. The steps of the algorithm are depicted on Figure 1. The output is depicted on Figure 2. One can keep in mind that the successive optimal cocycles built in the algorithm correspond to the fundamental cocycles with respect to the successive edges of the fully optimal spanning tree (cf. scholia above, see details in property (P2 i ) in the proof of Theorem 4.3 below).
-Computation of t 3 . We now consider the optimizable digraph − → G 2 = − → G 1 /{1}\{3} given with p = 4, E = 45678, and F = 26 (the edge 3 is deleted as the greatest belonging to the circuit 134 and to the previous F = 236). The linearly ordered signed cocycles of − → G 2 positive of E and containing p = 4 are: 46 > 2457 (where the bar upon elements represents negative elements). The maximal is C opt = 46. We get t 3 = 5.
-Computation of t 4 . We now consider the optimizable digraph − → G 3 = − → G 2 /{4}\{2} given with p = 5, E = 578, and F = 6 (the edge 2 is deleted as the greatest belonging to the circuit 25 and to the previous F = 26). The linearly ordered signed cocycles of we have f ′ ≥ f since f ′ ∈ D and min(D) = f . Hence f ′ = f , and we have proved D ∩ C = {f }, which contradicts the orthogonality of the cycle C and the cocycle D (see Section 2.1).
So we have min(D ′ ) = min(D). Since the cocycle D 1 of G 1 inducing D in G also induces D ′ in G ′ , and since min(D) = min(D 1 ) by induction hypothesis, we get min(D ′ ) = min(D 1 ).
Finally, if min(D ′ ) ∈ F ′ , since min(D ′ ) = min(D) ∈ F , then min(D ′ ) = f . As above, there are two cases for defining f at step (2.5). In the first case, we have f = p ′ = min(E ′ ), hence min(D ′ ) = f ∈ F ′ ∪ {p ′ }, which is the property that we have to prove. In the second case, we have min(D) = f and the same argument as above leads again to C ∩ D = {f } and to the same contradiction. The invariant is now proved.
Proof of Theorem 4.3. The present proof is a condensed but complete version for graphs of the general geometrical proof that will be given in [10], taking benefit of the linear ordering of cocycles defined above (which is possible in graphs but not in general, see Remark 4.7). We will extensively use the notion of cocycle induced in a minor of a graph by a cocycle of this graph, see Section 2.1. Since − → G 1 is bipolar, its fully optimal spanning tree α( − → G 1 ) exists and satisfies the properties recalled in Section 2.2. By Lemma 4.5, the algorithm given in the theorem statement is well defined. Now, we have to prove that α( − → G 1 ) is necessarily equal to the output of this algorithm. The proof consists in proving by induction that, for every 2 ≤ i ≤ r, the two following properties (P1 i ) and (P2 i ) are true. The property (P1 i ) for 2 ≤ i ≤ r means that the algorithm actually returns α( − → G 1 ). The property (P2 i ) for 2 ≤ i ≤ r means that the optimal cocycles computed in the successive minors are actually induced by the fundamental cocycles of the fully optimal spanning tree α( − → G 1 ), as noted in the first scholia in the algorithm statement. Then, the proof is not long but rather technical. • (P2 i ) The optimal cocycle C opt of − → G i−1 , defined at step (2.1) of the algorithm equals the First, observe that C i−1 is a well defined induced cocycle in property (P2 i ) as soon as (P1 j ) is true for all j < i − 1 (implying Second, let 1 ≤ k ≤ r. Assume that, the property (P2 i ) is true for all 2 ≤ i ≤ k and the property (P1 i ) is true for all 2 ≤ i ≤ k − 1. Then we directly have that the property (P1 i ) is also true for i = k. Indeed, as shown in [5,Proposition 2] (that can be proved easily), the fact that the spanning tree T = b 1 < b 2 < ... < b r has external activity 0 implies that, for all 1 ≤ i ≤ r, we have b i = min E \ ∪ j≤i−1 C * (T ; b j ) . So we have b k = min(E k−1 \ C k−1 ) = · · · = min(E 1 \ ∪ j≤k−1 C j ) = min(E 1 \ ∪ j≤k−1 C * (T ; b j )), and so we have t k = b k . Now, it remains to prove that, under the above assumption, the property (P2 i ) is true for i = k + 1. Consider C opt , denoting the optimal cocycle of − → G k , and C k , denoting the cocycle of − → G k induced by the fundamental cocycle of p k = t k = b k w.r.t. T in − → G 1 . Assume for a contradiction that C opt = C k .
Since properties (P1 i ) and (P2 i ) are true for all 2 ≤ i ≤ k by assumption, and reformulating definition of − → G ′ at step (2.6), we have: and hence, inductively, we have: That is: In particular, we have C k = C * (T ; b k ) \ A. And we also have A ∩ T = ∅. As recalled in Section 2.2, the definition of T implies that C k is positive on E k , that is positive except maybe on elements of F k \ E k , just the same as C opt . By assumption and property (P1), we have b k = t k = min(E k ). Then, by definition of C k = C * (T ; b k )∩(E k ∪F k ), we have b k ∈ C k . Hence, the cocycle C k has been taken into account in the linear ordering of cocycles of the optimizable digraph − → G k defining C opt . So C opt > C k in this linear ordering by definition of C opt .
By definition of this linear ordering, let f be the smallest element of F k with the property of being positive in C opt and not belonging to C k , or positive in C opt and negative in C k , or not belonging to C opt and negative in C k . The edge f does not have opposite signs in C opt and −C k . So let D ′ be a cocycle of − → G k obtained by elimination between C opt and −C k preserving f (see Section 2.1). Necessarily, f is positive in D ′ by definition of f . By definitions of C opt and C k , the element b k is positive in C opt and in C k . Moreover, every edge in F smaller than f belonging to C opt resp. C k also belongs to C k resp. C opt with the same sign, by definition of f . Hence, by properties of elimination, the cocycle D ′ does not contain b k nor any element of F smaller than f belonging to C opt or C k . Since the smallest edge in D ′ belongs to F ∪ {b k }, as shown by the invariant of Lemma 4.6, and since we have b k ∈ D ′ , then we have min(D ′ ) = f . The negative elements of D ′ are either elements of F k \ E k , or elements of C k \ {b k }. In the first case, since E k = E 1 \ A, the negative elements belong to F k ∩ A ⊆ A ⊆ E 1 \ T . In the second case, the negative elements also belong to E 1 \ T by definition of a fundamental cocycle. Finally, let D be the cocycle of The negative elements of D belong to A or are negative in D ′ , then, in every case, they belong to E 1 \ T . Moreover, as shown by the invariant of Lemma 4.6, we have min(D) = min(D ′ ) = f . So we have built a cocycle D such that: In a first case, we assume that f ∈ T . Then f = c j for some c j ∈ E 1 \ T . Let C = C(T ; c 1 ) • ... • C(T ; c j ). As recalled above, this composition of cycles has only positive elements except the first one p 1 = b 1 . The edge f is positive in C and D, hence, by orthogonality (see Section 2.1), there exists an edge e ∈ C ∩ D with opposite signs in C and D. We have b 1 ∈ D, hence e = b 1 , and hence e is positive in C and negative in D. Hence e ∈ E 1 \ T . Since e ∈ C, we must have e = c i for some i ≤ j, that is e ≤ f . But f = min(D) implies e = f , which is a contradiction.
In a second case, we assume that f ∈ T . Let a = min C * (T ; f ) . Since f ∈ F , we have f = min(E 1 ), and so f = a by definition of T , so we have a ∈ T . Then a = c j for some c j ∈ E 1 \ T . Let C = C(T ; c 1 ) • ... • C(T ; c j ), which has only positive elements except the first one p 1 = b 1 . Since a ∈ C * (T ; f ), we have f ∈ C(T ; c j ). As above, by orthogonality, the edge f positive in C and D, together with p 1 ∈ D, implies an edge e ∈ C ∩ D positive in C and negative in D. So e ∈ E 1 \ T , and so e = c i for some i ≤ j, so e ≤ a, which implies e ≤ f by definition of a, leading to the same contradiction as above with f = min(D).
Remark 4.7 (linear programming). The algorithm of Theorem 4.3 actually consists in a translation and an adaptation in the case of graphs of a geometrical algorithm providing in general a strengthening of pseudo/real linear programming (in oriented matroids / real hyperplane arrangements). In this setting, we optimize a sequence of nested faces (the successive optimal cocycles in the above algorithm, a process that we call flag programming), each with respect to a sequence of objective functions (the linearly ordered objective set in the above algorithm, a process that we call multiobjective programming), yielding a unique fully optimal basis for any bounded region. This refines standard linear programming where just one vertex is optimized with respect to just one objective function, but this can be computed inductively using standard pseudo/real linear programming. See [10] for details (see also [7] for a short presentation and formulation of the general algorithm in the real case; see also [8] for the primary relations between full optimality and linear programming; see also [4] in the simple case of the general position/uniform oriented matroids where the first fundamental cocircuit determines the basis; see also Section 1 for complementary information and references notably on duality properties; see also Remark 3.6 in relation with deletion/contraction).
Let us relate that to the present paper. The flag programming can be addressed inductively by means of a sequence of multiobjective programming in minors. This induction is rather similar in the graph case, yielding the successive minors addressed in the above algorithm of Theorem 4.3. The multiobjective programming can be addressed inductively by means of a sequence of standard linear programming in lower dimensional regions. In the graph case, this induction can be avoided and transformed into the linear ordering of cocycles by means of a suitable weight function (Definition 4.2), yielding a unique optimal cocycle. This simplification is possible because U 2,4 is an excluded minor (as for binary matroids), which yields very special properties for the skeleton of regions. Hence, the construction of this section could be readily extended to binary oriented matroids (that is regular oriented matroids, or totally unimodular matrices). See the proof of Proposition 4.8 for technical explanations.
From the computational complexity viewpoint, we get from this approach that the optimal cocycle, and hence the fully optimal spanning tree, can be computed in polynomial time, a result which we state in Proposition 4.8 and Corollary 4.9 below. However, this complexity bound is achieved here by using numerical methods for standard real linear programming. An interesting question is to achieve this bound by staying at the combinatorial level of the graph, see Remark 4.10.
Proposition 4.8. The optimal cocycle of an optimizable digraph can be computed in polynomial time.