## Matroid reinforcement and sparsification ∗

Huy Truong 1 and Pietro Poggi-Corradini 1

1 Dept. of Mathematics, Kansas State University, Manhattan, KS 66506, USA.

## Abstract

Homogeneous matroids are characterized by the property that strength equals fractional arboricity, and arise in the study of base modulus [22]. For graphic matroids, Cunningham [9] provided efficient algorithms for calculating graph strength, and also for determining minimum cost reinforcement to achieve a desired strength. This paper extends this latter problem by focusing on two optimal strategies for transforming a matroid into a homogeneous one, by either increasing or decreasing element weights. As an application to graphs, we give algorithms to solve this problem in the context of spanning trees.

Keywords: Homogeneous matroids, uniformly dense matroids, modulus, strength, fractional arboricity, matroid reinforcement.

2020 Mathematics Subject Classification: 05C85 (Primary) ; 90C27 (Secondary).

## 1 Introduction

The authors have studied the modulus of bases of matroids in [22], and have shown that base modulus is closely related to strength and fractional arboricity. Let us recall these notions. For a loopless matroid M E, ( I ) on a ground set E with a family of independent sets I and a rank function r , let σ ∈ R E &gt; 0 be the weights assigned to each element e in E . For X ⊆ E , denote σ X ( ) = ∑ e ∈ X σ e ( ).

Then, the strength of M is defined as:

$$S _ { \sigma } ( M ) & \coloneqq \min \left \{ \frac { \sigma ( X ) } { r ( E ) - r ( E - X ) } \, \colon X \subseteq E, r ( E ) > r ( E - X ) \right \},$$

and the fractional arboricity of M is defined as:

$$D _ { \sigma } ( M ) & \coloneqq \max \left \{ \frac { \sigma ( X ) } { r ( X ) } \, \colon \, X \subseteq E, r ( X ) > 0 \right \}.$$

An unweighted matroid ( σ ≡ 1) is said to be homogeneous if its strength equals its fractional arboricity. This class of matroids is also called uniformly dense matroids and it was studied extensively

∗ This material is based upon work supported by the National Science Foundation under Grant n. 2154032.

in the literature, see for instance [3, 7, 19]. For an unweighted matroid M , let B denote the family of all bases of M . The modulus of the base family B is related to the minimum expected overlap (MEO) problem of B (see equation (2.8)), the strength, the fractional arboricity, and the theory of principal partitions of matroids, see [22]. The theory of principal partitions of graphs, matroids, and submodular systems has been developed over several decades. For an overview of this theory, we recommend the survey paper [13]. Furthermore, this theory has been generalized to weighted matroids (also see [13]).

In this paper, a weighted matroid M with element weights σ is said to be ( σ )-homogeneous if

$$S _ { \sigma } ( M ) = D _ { \sigma } ( M ).$$

In Section 2.2, we introduce the minimum expected weighted overlap problem for the base family of M and generalize the results in [22] for the case of weighted matroids. In doing this, we provide a definition for homogeneous matroids in the context of base modulus (see Definition 2.3), which is different from the one given in (1.3), but turns out to be equivalent. Moreover, we demonstrate that M is homogeneous if and only if σ ∈ conic( B ), where conic( B ) is the conical hull of B (see Theorem 2.5).

In the case of graphic matroids, let's consider an undirected, connected, and weighted graph G = ( V, E ) with edge weights σ ∈ R E &gt; 0 . The graphic matroid associated with the graph G is the matroid M = ( E, I ) where a subset A ⊆ E is independent if and only if A does not contain any cycles in G . For every subset A ⊂ E , its rank f ( A ) is given by | V ( A ) | -r A , where V ( A ) is the set of vertices of the edge-induced subgraph H A induced by A , and r A is the number of connected components in H A [10]. Then, the family of all spanning trees of the graph G is the base family of the graphic matroid M [10]. In [9], Cunningham provides an efficient algorithm for computing the graph strength of G . Additionally, Cunningham studies the problem of strength reinforcement. Consider a scenario where increasing the weight σ e ( ) of each edge e ∈ E incurs a cost of m e ( ) per unit increase. Given a threshold s 0 &gt; 0, the strength reinforcement problem aims to find the most cost-effective method to enhance edge strengths, ensuring that the resulting graph's strength is at least s 0 . This problem can be formulated as follows:

$$\underset { z \in \mathbb { R } ^ { E } \geq 0 } { \min i z e } \ \ m \cdot z \\ \text{simize} \ \ t \in \mathbb { R } ^ { E } \geq 0 \\ \text{subject to} \ \ S _ { \sigma + z } ( G ) \geq s _ { 0 }.$$

Cunningham [9] proposes an efficient solution to this problem, which is based on a greedy algorithm for polymatroids. This requires solving 2 | E | minimum cut problems.

This led us to study the following related problem. Consider a weighted matroid M = ( E, I ) with element weights σ and assume that M is not homogeneous. We are interested in identifying a minimum-cost strategy to increase edge weights in order to transform the matroid M into a homogeneous one. Given a per-unit increasing cost m e ( ) ≥ 0 for each e ∈ E , we introduce the matroid reinforcement problem

$$\underset { z \in \mathbb { R } ^ { E } _ { \geq 0 } } { \min i z e } \quad m \cdot z \\ \text{subject to } \ \sigma + z \in \text{conic} ( \mathcal { B } ).$$

Likewise, we study a minimum-cost strategy to decrease edge weights that gives rise to the following

matroid sparsification problem

$$\min _ { z \in \mathbb { R } ^ { E } _ { \geq 0 } } \quad & m \cdot z \\ \text{subject to } \ \sigma - z \in \text{conic} ( \mathcal { B } ).$$

For a matroid M E, ( I ) with the rank function r , it is well-known that the rank function r is a polymatroid function defined on subsets of E (see Definition 3.2). For any polymatroid function f , we associate to it a polyhedron P f :

$$P _ { f } \coloneqq \left \{ x \in \mathbb { R } ^ { E } \, \colon x \geq 0, x ( A ) \leq f ( A ), \forall A \subseteq E \right \}. \text{ } \\ \text{en shown that } P _ { f } \text{ is a polynatroid, see Definition 3.1. } \text{We also define the base polytope}$$

It has been shown that P f is a polymatroid, see Definition 3.1. We also define the base polytope B f of the polymatroid function f as follows:

$$B _ { f } \coloneqq \left \{ x \in \mathbb { R } ^ { E } \, \colon x \in P _ { f }, x ( E ) = f ( E ) \right \}. \\ \intertext { k function of a matroid } M ( E \, \mathcal { T } ) \, \text{ with the base family } \mathcal { B } \, \text{ Edmonds } \text{10} \text{ Theorem}$$

If f is the rank function of a matroid M E, ( I ) with the base family B , Edmonds [10, Theorem 39] showed that the set of vertices of the polymatroid P f associated with f precisely corresponds to the set of incidence vectors of I . Edmonds [10, Theorem 43] also demonstrated that the set of vertices of the base polytope B f is the set of incidence vectors of B . In other words, the base polytope B f is the convex hull of incidence vectors of B . For any positive real number h , we define hB f := { hx : x ∈ B f } . Then, we have conic(

B

) =

hB .

f

h&gt;

⋃

0

Here are the main results of this paper. Let f be an arbitrary polymatroid function. In Section 3.2, we introduce a generalized version of problem (1.5), the so-called polymatroid reinforcement problem:

$$\underset { z \in \mathbb { R } _ { \geq 0 } ^ { E } } { \minimize } \ \ m \cdot z \\ \text{subject to} \ \ \sigma + z \in h B _ { f } \text{ for some } h > 0.$$

In Theorem 3.9, we show that the polymatroid reinforcement problem (1.9) is equivalent to

$$\underset { z \in \mathbb { R } ^ { E } _ { \geq 0 } } { \min i z e } \quad m \cdot z \\ \text{subject to} \quad \sigma + z \in \alpha B _ { f },$$

where

$$\alpha \coloneqq \min \left \{ h > 0 \, \colon \sigma \in h P _ { f } \right \}.$$

In Section 3.3, we also introduce a generalized version of problem (1.6), the so-called polymatroid sparsification problem:

$$\text{summ.} \quad \underset { z \in \mathbb { R } _ { \geq 0 } ^ { E } } { \text{minize} } \quad m \cdot z \\ \text{subject to} \quad \sigma - z \in h B _ { f } \text{ for some } h > 0.$$

We define the set function g as follows: g U ( ) := f ( E ) -f ( E \ U ) for all subsets U ⊆ E . Then, we associate the following polyhedron with g :

$$Q _ { g } \coloneqq \left \{ x \in \mathbb { R } ^ { E } \colon x \geq 0, x ( A ) \geq g ( A ), \forall A \subseteq E \right \}. \quad \text{(1.13)} \\ \text{ure, see for instance [20], the polyhedron } Q _ { g } \text{ is known as a corapolymatroid.  We also}$$

In the literature, see for instance [20], the polyhedron Q g is known as a contrapolymatroid. We also define

$$C _ { g } \coloneqq \{ x \in Q _ { g } \, \colon x ( E ) = g ( E ) \} \,.$$

It is well-known that B f = C g [20, Section 44.5]. Let c be a constant such that c ≥ max { f ( E , ) ‖ σ ‖ ∞ } and denote c to be the vector of all c . We introduce the following polytope:

$$\times \, \infty \, \infty \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources}) \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources}\, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \, \text{sources} \\ \text{s main results in this direction:}$$

Here are the main results in this direction:

In Theorem 3.10, we define a map t : R E → R E by t ( x ) = -x + c , x ∈ R E , and show that t ( Q g,c ) is a polymatroid. Using this, in Theorem 3.16, we show that the polymatroid sparsification problem is equivalent to

$$\minimize _ { z \in \mathbb { R } ^ { E } _ { \geq o } } \ & m \cdot z \\ \text{subject to} \ & \sigma - z \in \beta C _ { g },$$

where

$$\beta \coloneqq \max \left \{ h > 0 \, \colon \sigma \in h Q _ { g } \right \}.$$

When f is the rank function of a matroid M E, ( I ), using (1.11) and (1.17), we get α = D σ ( M ) and β = S σ ( M ). Therefore, we can generalize the relationship between strength and fractional arboricity (see Theorem 2.8) in the context of polymatroids. In particular, in Theorem 3.19, we demonstrate that α ≥ β , and σ ∈ hB f = hC g if and only if h = α = β .

Finally, Theorem 3.9 shows that we can reduce the feasible set of the matroid reinforcement problem. Moreover, the reduced feasible set contains every z ∈ R E ≥ 0 such that σ + z is maximal in αP f . Similarly, Theorem 3.16 shows that we can reduce the feasible set of the matroid sparsification problem and the reduced feasible set contains z ∈ R E ≥ 0 such that σ -z is minimal in βQ g . Consequently, we may use the greedy algorithm to solve both problems. In Section 4, we provide Algorithm 1 and Algorithm 2 for solving these two problems.

In Section 5, we apply Algorithm 1 and Algorithm 2 to the case of graphic matroids. In particular, we provide detailed methods to implement Algorithm 1 and 2 using Cunningham's minimum-cut formulations. Furthermore, we provide Algorithm 3 to compute the fractional arboricity and, as a consequence, we provide Algorithm 4 for computing the spanning tree modulus using the fractional arboricity.

## 2 Matroid base modulus

## 2.1 Preliminaries

## Matroid

First, let us recall the definition of matroids. For a set X , we denote its cardinality by | X | . If Y is another set, then X -Y represents the relative complement of Y in X .

Definition 2.1. Let E be a finite set, let I be a set of subsets of E , the set system M E, ( I ) is a matroid if the following axioms are satisfied:

- (I1) ∅ ∈ I .
- (I2) If X ∈ I and Y ⊆ X then Y ∈ I ( Hereditary property ).
- (I3) If X,Y ∈ I and | X &gt; Y | | | , then there exists x ∈ X -Y such that Y ∪ { x } ∈ I ( Exchange property ).

Every set in I is called an independent set .

Let M E, ( I ) be a matroid on the ground set E with the set of independent sets I . The maximal independent sets are called bases , the minimal dependent sets are called circuits . The rank function, r : 2 E → Z + , defined on all subsets X ⊂ E is given by:

$$r ( X ) \coloneqq \max \left \{ | Y | \, \colon Y \subseteq X, Y \in \mathcal { I } \right \}.$$

The closure operator cl : 2 E → 2 E is a set function, defined as:

$$\text{cl} ( X ) \coloneqq \{ y \in E \, \colon r ( X \cup \{ y \} ) = r ( X ) \} \,.$$

A set X ⊆ E is said to be closed if cl( X ) = X . For a subset X ⊆ E , let C ( M ) be the family of circuits of M . Then, the set

$$\mathcal { C } ( M \, \searrow \, X ) \, \coloneqq \, \{ C \subseteq E - X \, \colon C \in \mathcal { C } ( M ) \},$$

defines the family of circuits for a matroid on E -X . The matroid M \ X is called the deletion of X from M . The restriction to X in M is denoted by M X | , and is defined as the matroid on X given by M X | := M \ ( E -X ).

## Base modulus

Let M E, ( I ) be a matroid on the ground set E with weights σ ∈ R E &gt; 0 assigned to each element e in E . Let B be the family of bases of M . Each base B ∈ B is associated to a usage vector N ( B, · ) T : E → R ≥ 0 . In this paper, we define N ( B, · ) T to be the indicator function of B . In other words, B is associated with a |B| × | E | usage matrix N . A density ρ ∈ R E ≥ 0 is a vector such that ρ e ( ) represents the cost of using the element e ∈ E . We define the total usage cost of each base B with respect to ρ

$$\ell _ { \rho } ( B ) \coloneqq \sum _ { e \in E } \mathcal { N } ( B, e ) \rho ( e ) = ( \mathcal { N } \rho ) ( B ). \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon$$

A density ρ ∈ R E ≥ 0 is called admissible for B , if for all B ∈ B , /lscript ρ ( B ) ≥ 1 . The admissible set Adm( B ) of B is defined as the set of all admissible densities for B ,

Fix 1 ≤ p &lt; ∞ , the energy of the density ρ is defined as follows

$$\text{ all admissible densities for $B$,} \\ \text{Adm} ( \mathcal { B } ) \coloneqq \left \{ \rho \in \mathbb { R } _ { \geq 0 } ^ { E } \colon \mathcal { N } \rho \geq 1 \right \}. \\ \text{$\prime$ of the density $\rho$ is defined as follows}$$

$$\colon & \text{ensify $\rho$ is channel as follows} \\ \mathcal { E } _ { p, \sigma } ( \rho ) \coloneqq \sum _ { e \in E } \sigma ( e ) \rho ( e ) ^ { p }.$$

The p -modulus of B is

$$\text{Mod} _ { p, \sigma } ( \mathcal { B } ) \coloneqq \inf _ { \rho \in \text{Adam} ( \mathcal { B } ) } \mathcal { E } _ { p, \sigma } ( \rho ).$$

When σ is the vector of all ones, we omit σ and write E p ( ρ ) := E p,σ ( ρ ) and Mod ( p B ) := Mod p,σ ( B ).

## Fulkerson dual families and the MEO problem

We will routinely identify B with the set of its usage vectors { N ( B, · ) T : B ∈ B } in R E ≥ 0 . We define the dominant of B as

$$\text{Dom} ( \mathcal { B } ) \coloneqq \text{co} ( \mathcal { B } ) + \mathbb { R } _ { \geq 0 } ^ { E }$$

where co( B ) denotes the convex hull of B in R E . Next, we recall Fulkerson duality for modulus. The Fulkerson blocker family ̂ B of B is defined as the set of all the extreme points of Adm( B ).

Then, Fulkerson blocker duality [14] states that

$$\widehat { \mathcal { B } } \coloneqq & \text{Ext} \$$

Dom( ̂ B ) = Adm( B ) , (2.2) Dom( B ) = Adm( ̂ B ) . (2.3) Let ˜ B be a set of vectors in R E ≥ 0 . We say that B and ˜ B are a Fulkerson dual pair (or ˜ B is a Fulkerson dual family of B ) if

̂ ̂ ˜ When 1 &lt; p &lt; ∞ , let q := p/ p ( -1) be the H¨lder conjugate exponent of o p . For any set of weights σ ∈ R E &gt; 0 , define the dual set of weights ˜ σ as ˜ σ e ( ) := σ e ( ) -q p for all e ∈ E . Let ˜ B be a Fulkerson dual family of B . Fulkerson duality for modulus [2, Theorem 3.7] states that

Adm( ˜ B ) = Dom( B ) . Then, B is the smallest Fulkerson dual family of B , meaning that B ⊂ B [21].

$$\text{Mod} _ { p, \sigma } ( \mathcal { B } ) ^$$

$$\varpi \text{w}, & & \eta ^ { * } ( e ) =$$

Moreover, the optimal ρ ∗ of Mod p,σ ( B ) and the optimal η ∗ of Mod q,σ ˜ ( ˜ B ) always exist, are unique, and are related as follows,

When p = 2, we have

$$\begin{array} {$$

Let P B ( ) be the set of all probability mass functions (pmf) on B . According to the probabilistic interpretation of modulus [6], we can express

$$\text{Mod} _ { 2 } ( \mathcal { B } ) ^ { - 1 }$$

Consider the scenario where B is a collection of subsets of E with usage vector given by the indicator function. Given a pmf µ ∈ P B ( ), let B and B ′ be two independent random bases in B , identically distributed with law µ . The cardinality of the overlap between B and B ′ , is | B ∩ B ′ | and is a random variable whose expectation is denoted by E µ | B ∩ B ′ | , which equals µ T NN T µ . Then, the minimum expected overlap (MEO) problem for B is formulated as

$$\min _ { \mu \in \mathcal { P } ( \mathcal { B } ) } \mathbb { E } _ { \mu } | \underline { B } \cap \underline { B } ^ { \prime } |.$$

Moreover, any pmf µ ∈ P B ( ) is optimal if and only if

$$( \mathcal { N } \mu ) ( e ) = \rho ^ { * } ( e ) / \text{ Mod} _ { 2 } ( \mathcal { B } ) \quad \forall e \in E.$$

## 2.2 Matroid base modulus with weights

Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 , let B be the base family of M . A set X ⊆ E is said to be complement-closed if E -X is closed. Let Φ be the family of all nonempty complement-closed sets X ⊆ E with usage vectors:

$$\widetilde { \mathcal { N } } ( X, \cdot ) ^ { T } \coloneqq \frac { 1 } { r ( E ) - r ( E - X ) } \mathbb { 1 } _ { X }. & & ( 2. 1 0 ) \\ \text{on dual family of } \mathcal { B } \, [ 2 2, \, \text{Theorem } 6. 2 ].$$

Then, Φ is a Fulkerson dual family of B [22, Theorem 6.2].

Base modulus for unweighted matroids was thoroughly studied in [22]. In this section, we generalize the results of base modulus for unweighted matroids to weighted matroids. We start by considering a matroid M E, ( I ) with weights σ ∈ Z E &gt; 0 .

/negationslash

/negationslash

For each e ∈ E M ( ), we create a set X e containing σ e ( ) copies of e . Let X e := { e , e 1 2 , . . . , e σ e ( ) } be a set such that X e ∩ X e ′ = ∅ , for all e, e ′ ∈ E M ( ) with e = e ′ . Next, we define the σ -parallel extension M σ of M as follows. The σ -parallel extension M σ is obtained by replacing each element e ∈ E M ( ) by X e . In specific, the ground set E M ( σ ) of M σ is ⋃ e ∈ E M ( ) X e . A subset Y ∈ E M ( σ ) is independent in M σ if and only if ∀ e ∈ E M , X ( ) | e ∩ Y | ≤ 1 and the set { e ∈ E M ( ) : X e ∩ Y = ∅} is independent in M . In the case where every element e is assigned a constant weight r , we write M r for M σ ≡ r and call M r the r -parallel extension of M .

Let E ′ = { e 1 : e ∈ E M ( ) } ⊆ E M ( σ ) . There is a matroid isomorphism between M and M E σ | ′ with the bijection e ↔ e 1 between E M ( ) and E ′ . Thus, we can see M as the restriction M E σ | ′ of M σ . Moreover, based on the definition of M σ , we have that S σ ( M ) = S M ( σ ), D σ ( M ) = D M ( σ ), and Mod p,σ ( B ( M )) = Mod ( p B ( M σ )). Then, by continuity and 1-homogeneity of modulus (meaning that Mod p,kσ ( B ( M )) = k Mod p,σ ( B ( M )) for k &gt; 0), it is then straightforward to generalize our results to weighted matroids with weights σ ∈ R E &gt; 0 . In the rest of this section, we give results without proofs for weighted base modulus generalized from the unweighted case.

We begin by introducing the minimum expected weighted overlap problem. Let P B ( ) be the set of all probability mass functions (or pmf) on B . Given a pmf µ ∈ P B ( ), let B and B ′ be two independent random bases, identically distributed by the law µ . We measure the weighted overlap between B and B ′ ,

$$\sigma ^ { - 1 } ( \underline { B } \cap \underline { B } ^ { \prime } ) \coloneqq \sum _ { e \in \underline { B } \cap \underline { B } ^ { \prime } } \sigma ^ { - 1 } ( e ),$$

which is a random variable whose expectation is denoted by E µ [ σ -1 ( B ∩ B ′ )]. Then, the minimum expected weighted overlap (MEO σ -1 ) problem is the following problem:

$$\underset { \text{subject to} } { \minimize} \quad \mathbb { E } _ { \mu } \left [ \sigma ^ { - 1 } ( \underline { B } \cap \underline { B ^ { \prime } } ) \right ] }$$

Next, we present a theorem that characterizes the relationship between base modulus and the MEO σ -1 problem.

Theorem 2.2. Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let B be the base family with usage vectors given by the indicator functions and let ˜ B be a Fulkerson dual family of B . Then, ρ ∈ R E ≥ 0 , η ∈ R E ≥ 0 and µ ∈ P ( B ) are optimal respectively for Mod 2 ,σ ( B ) , Mod 2 ,σ -1 ( ˜ B ) and MEO σ -1 ( B ) if and only if the following conditions are satisfied.

$$( i ) \quad \rho \in \text{Adm} ( \mathcal { B } ), \quad \eta = \mathcal { N } ^ { T } \mu,$$

$$( i i ) \quad \eta ( e ) = \frac { \sigma ( e ) \rho ( e ) } { \text{Mod} _ { 2, \sigma } ( \mathcal { B } ) } \quad \forall e \in E,$$

$$( i i i ) \quad \mu ( B ) ( 1 - \ell _ { \rho } ( B ) ) = 0 \quad \forall B \in \mathcal { B }.$$

In particular,

$$\text{MEO} _ { \sigma ^ { - 1 } } ( \mathcal { B } ) = \text{Mod} _ { 2, \sigma } ( \mathcal { B } ) ^ { - 1 } = \text{Mod} _ { 2, \sigma ^ { - 1 } } ( \widetilde { \mathcal { B } } ). & & ( 2. 1 3 ) \\ \text{s introduce the definition of a homogeneous matroid.}$$

Next, let us introduce the definition of a homogeneous matroid.

Definition 2.3. Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let B be the base family with usage vectors given by the indicator functions. Let ˜ B be a Fulkerson dual family of B . Let ρ ∗ and η ∗ be the unique optimal densities for Mod 2 ,σ ( B ) and Mod 2 ,σ -1 ( ˜ B ) respectively. Then, the matroid M is said to be homogeneous if σ -1 η ∗ is constant, or equivalently, ρ ∗ is constant.

Several properties of the weighted base modulus can be proved in the same manner as those for the weighted spanning tree modulus on graphs. See [21] for details on the weighted spanning tree modulus.

Theorem 2.4. Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let B be the base family of M . Let ˜ B be a Fulkerson dual family of B . Define the density n σ :

$$n _ { \sigma } ( e ) \coloneqq \frac { \sigma ( e ) } { \sigma ( E ) } r ( E ) \quad \ \forall e \in E.$$

Then, M is homogeneous if and only if η σ ∈ Adm( ˜ B ) .

Theorem 2.5. Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let B be the base family of M . Then, M is homogeneous if and only if σ ∈ conic( B ) , where conic( B ) is the conical hull of B .

Proof. The proof is the same as Proof of Theorem 7.5 in [21].

Theorem 2.6. Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let B be the base family of M . Let S σ ( M ) be the strength of M . Let ˜ B be a Fulkerson dual family of B . Let η ∗ be the optimal density for Mod 2 ,σ -1 ( ˜ B ) . Denote

$$\stackrel { \ast \ast } { \Gamma \ast } \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon \\ E _ { m a x } \coloneqq \left \{ e \in E \, \colon \sigma ^ { - 1 } ( e ) \eta ^ { * } ( e ) = \max _ { e \in E } \sigma ^ { - 1 } ( e ) \eta ^ { * } ( e ) = \colon ( \sigma ^ { - 1 } \eta ^ { * } ) _ { m a x } \right \}.$$

Then, E max is optimal for the strength of M , and

$$( \sigma ^ { - 1 } \eta ^ { * } ) _ { m a x } = \frac { 1 } { S _ { \sigma } ( M ) }.$$

Theorem 2.7. Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let B be the base family of M . Let D σ ( G ) be the fractional arboricity of M . Let ˜ B be a Fulkerson dual family of B . Let η ∗ be the optimal density for Mod 2 ,σ -1 ( ˜ B ) . Denote

$$\Phi _ { \begin{array} { c c c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phigma _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin {array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Phi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \end{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{any} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi } { \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin {array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psigma _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{\array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{{ c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psappa _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \beginct } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _ { \begin{array} { c } \Psi _$$

Then, E min is optimal for the fractional arboricity of M , and

$$( \sigma ^ { - 1 } \eta ^ { * } ) _ { m i n } = \frac { 1 } { D _ { \sigma } ( M ) }.$$

Theorem 2.8. Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let B be the base family of M . Let S σ ( M ) be the strength of M . Let D σ ( G ) be the fractional arboricity of M . Let ˜ B be a Fulkerson dual family of B . Let η ∗ be the optimal density for Mod 2 ,σ -1 ( ˜ B ) . Then,

$$\frac { 1 } { ( \sigma ^ { - 1 } \eta ^ { * } ) _ { m a x } } = S _ { \sigma } ( G ) \leq \frac { \sigma ( E ) } { r ( E ) } \leq D _ { \sigma } ( G ) = \frac { 1 } { ( \sigma ^ { - 1 } \eta ^ { * } ) _ { m i n } }.$$

Moreover, the matroid M is homogeneous if and only if S σ ( M ) = D σ ( M ) .

## 3 Polymatroid reinforcement and polymatroid sparsification

## 3.1 Preliminaries

Polymatroids were introduced by Edmonds [11], who also established many profound insights into the topic. Let E be a finite set, we recall the definition of polymatroids as follows.

Definition 3.1. Let P ⊆ R E . Then P is called a polymatroid if P is a compact non-empty subset of R E ≥ 0 satisfying the following properties:

- (i) If 0 ≤ x ≤ y and y ∈ P , then x ∈ P .
- (ii) For any x ∈ R E ≥ 0 , any maximal vector y ∈ P with y ≤ x (such y is called a P -basic of x ) has the same component sum y E ( ).

Let f be a real-valued function defined on subsets of E . The function f is said to be submodular if for all subsets A, B of E , we have

$$f ( A \cap B ) + f ( A \cup B ) \leq f ( A ) + f ( B ).$$

Conversely, f is said to be supermodular if -f is submodular. Next, we recall the definition of polymatroid functions .

Definition 3.2. A polymatroid function is a real-valued function f defined on subsets of E , which is normalized, nondecreasing, and submodular, meaning that

- (i) f ( ∅ ) = 0;
- (ii) f ( A ) ≤ f ( B ) if A ⊆ B ⊆ E ;
- (iii) f ( A ∩ B ) + f ( A ∪ B ) ≤ f ( A ) + f ( B ) for all subsets A, B ⊆ E .

Let P f be the polyhedron associated with a polymatroid function f defined as in (1.7). It is well-known that P f is a polymatroid. It is important to note that every polymatroid P can be represented in the form of P f for some polymatroid function f . We let B f be the base polytope of the polymatroid function f defined as in (1.8).

Let P be a polymatroid, one interesting problem in this field is finding a P -basis y of a given vector x ∈ R E ≥ 0 . An algorithm for solving this problem is a greedy algorithm which starts with y = 0 and successively increases each component of y as much as possible, subject to the constraints y ≤ x and y ∈ P , see [10]. Given a vector m ∈ R E , the greedy algorithm can be generalized to solve the following optimization problem:

$$\min \left \{ m \cdot y \colon y \text{ is a P-basis of } x \right \},$$

as discussed in [9], [10]. For (3.2), we increase successively each component in the order j , j 1 2 , . . . , j k where k = | E | and m j 1 ≤ m j 2 ≤ · · · ≤ m j k . The well-known greedy algorithm for finding a minimum spanning tree in a graph (Kruskal's algorithm) is a special case of this greedy algorithm. It arises by choosing x = 1 ∈ R E where 1 is the vector containing all ones. Cunningham [9] proved the generalized algorithm does solve (3.2). To implement this algorithm, we need an oracle that computes

$$\max \left \{ \epsilon \, \colon y + \epsilon \mathbb { I } _ { \{ j \} } \in P \right \} \quad \text{ for any } y \in P \text{ and } j \in E. \quad \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{  \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{} \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{$$

## /BD 3.2 Polymatroid reinforcement

Let f be a polymatroid function on E . Let P = P f be the associated polymatroid with f . Let B f be the base polytope defined as in (1.8). For h &gt; 0, we define hB f := { hx : x ∈ B f } , and hP f := { hx : x ∈ P f } . Then, we have that hP f is also a polymatroid with the polymatroid function hf , and hB f is its base polytope. Given a per-unit increasing cost m e ( ) ≥ 0 for each e ∈ E and s ∈ R E &gt; 0 . We recall the polymatroid reinforcement problem in (1.9) where σ = s . To study this problem, we start by characterizing maximal vectors in the associated polymatroid P = P f .

Lemma 3.3. Let P = P f be the associated polymatroid of a polymatroid function f . Let B f be the base polytope of f . Given x ∈ P . Then, x is a maximal vector in P if and only if x ∈ B f .

This fact should be standard, but we provide a proof for the reader's convenience.

Proof. Assume that x ∈ B f . Then, we have x E ( ) = f ( E ). Hence, x is maximal because if we increase any component of x , then x E ( ) &gt; f E ( ), contradiction with the definition of P in (1.7).

Assume that x ∈ P is a maximal vector in P . Let c be a number such that c ≥ f ( E ). Let c ∈ R E be the column vector of all c . We have

$$x ( e ) \leq f ( \{ e \} ) \leq c, \quad \forall e \in E & & \text{(by the definition $(1.7))$} \,.$$

Hence, we obtain x ≤ c . Combine with the fact that x is maximal in P , we achieve that x is a P -basis of c . Let y ∈ B f , then y is maximal and is a P -basis of c . By Definition 3.1 of polymatroid, x and y has the same component sum, in other words, x E ( ) = y E ( ) = f ( E . ) Thus, we obtain x ∈ B f .

The following lemma defines a polymatroid generated by any element s ∈ P f .

Lemma 3.4. Let P = P f be the associated polymatroid of a polymatroid function f . Let B f be the base polytope of f . Given s ∈ P , we define the following polyhedron

## Then, P s is a polymatroid.

$$\L n \, s \in \, \L i \, \, w e \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ v v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v\ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u v \ u } \, \quad \, P ^ { s } s \colon = \left \{ x \in \, \mathbb { R } ^ { E } } _ { \geq 0 } \colon s + x \in \, P ^ { s } \right \}.$$

Proof. We aim to show that P s satisfies Definition 3.1. Since s ∈ P , then P s contains the vector 0. Moreover, P s is compact by its definition. For any vectors x, y such that x ≤ y and y ∈ P s , we have s + y ∈ P and s + x ≤ s + y . Then, s + x ∈ P by Definition 3.1 (i), which implies x ∈ P s . Hence, P s satisfies Definition 3.1 (i).

For any y ∈ R E ≥ 0 , let x be a maximal vector among all vectors satisfying x ≤ y and x ∈ P s . By the definition of P s , s + x ∈ P . We want to show that: s + x is a P -basis of s + . Indeed, suppose y that s + x is not a P -basis of s + . Then, there exists y /epsilon1 &gt; 0 and e ∈ E satisfying

$$s + x + \epsilon \mathbb { I } _ { \{ e \} } < s + y \text{ \ and \ } s + x + \epsilon \mathbb { I } _ { \{ e \} } \in P.$$

This is equivalent to

$$x + \epsilon \mathbb { 1 } _ { \{ e \} } < y \text{ \ and \ } x + \epsilon \mathbb { 1 } _ { \{ e \} } \in P ^ { s },$$

/BD

/BD

/BD /BD contradicting the definition of x . Thus, s + x is a P -basis of s + y . By Definition 3.1 (ii), we have ( s + x )( E ) does not depend on x , it only depends on y and s . This implies that x E ( ) = ( s + x )( E ) -s E ( ) does not depend on x . Therefore, P s satisfies Definition 3.1 (ii). In conclusion, P s is a polymatroid.

The following lemma characterizes maximal vectors in the polymatroid P s .

Lemma 3.5. Let P = P f be the associated polymatroid of a polymatroid function f . Let B f be the base polytope of f . Given s ∈ P , let P s be defined as in (3.4). Given x ∈ P s , then, x is maximal in P s if and only if ( s + x )( E ) = f ( E ) .

Proof. Assume that ( s + )( x E ) = f ( E ). By Lemma 3.3, s + x is maximal in P , this implies that x is maximal in P s by the definition of P s .

Conversely, assume that x is maximal in P s . To prove that ( s + x )( E ) = f ( E ), we first claim that there exists x ′ ∈ P s such that ( s + x ′ )( E ) = f ( E ).

If s is maximal in P , by Lemma 3.3, we obtain s E ( ) = f ( E ). Then, we choose x ′ = 0 ∈ R E . If s is not maximal in P , then we can increase successively each component of s as much as possible subject to s ∈ P , the resulting vector has the form s + x ′ for some x ′ ≥ 0. The vector s + x ′ is maximal in P because if there exists some e ∈ E and /epsilon1 &gt; 0 such that ( s + x ′ + /epsilon1 /BD { } e ) ∈ P , then during the process, we must have been increased the e -component of s to at least x ′ ( e ) + /epsilon1 , a contradiction. Hence, by Lemma 3.3, ( s + x ′ )( E ) = f ( E ) . Therefore, there exists x ′ ∈ P s such that ( s + x ′ )( E ) = f ( E ).

By the above argument, x ′ is also maximal in P s . By the Definition 3.1 (ii), x and x ′ has the same component sum, this implies that ( s + x )( E ) = ( s + x ′ )( E ) = f ( E ).

The feasible set of the reinforcement problem is ⋃ h&gt; 0 A h where

$$\begin{array} { c } h > 0 \\ A _ { h } \coloneqq \left \{ z \in \mathbb { R } _ { \geq 0 } ^ { E } \colon s + z \in h B _ { f } \right \}. \\ = P _ { f } \text{ be the associated polymatroid of a polymatroid function } f. \text{ Let } B _ { f } \text{ be the} \end{array}$$

/negationslash

Lemma 3.6. Let P = P f be the associated polymatroid of a polymatroid function f . Let B f be the base polytope of f . Let A h be defined as in (3.5). Let α := min { h &gt; 0 : s ∈ hP f } be defined as in (1.11). Then, A h = ∅ if and only if h ≥ α .

Proof. Let h &gt; 0. If there exists z ∈ A h . Then, we have s + z ∈ hB f ⊂ hP . f Because s ≤ s + , we z have s ∈ hP f , hence h ≥ α by the definition of α . If h ≥ α , then 0 ∈ A h .

Remark 3.7 . Let α be defined as in (1.11). For h ≥ α , we have

By Lemma 3.5, we obtain

$$\det \alpha & \text{e camel as in } ( 1. 1 1 ). \text{ for } n \geq \alpha, \, \text{we have} \\ A _ { h } & = \left \{ z \in \mathbb { R } _ { \geq 0 } ^ { E } \colon s + z \in h P _ { f }, ( s + z ) ( E ) = h f ( E ) \right \}. \\ 5, \, \text{we obtain}$$

$$A _ { h } = \left \{ z \in ( h P _ { f } ) ^ { s } \, \colon z \text{ is maximal in } ( h P _ { f } ) ^ { s } \right \}.$$

Remark 3.8 . Let h 1 ≥ h 2 ≥ α , and let z 1 ∈ A h 1 , z 2 ∈ A h 2 . Then

$$z _ { 1 } ( E ) = h _ { 1 } f ( E ) - s ( E ) \geq h _ { 2 } f ( E ) - s ( E ) = z _ { 2 } ( E ).$$

Therefore, if the cost m e ( ) = 1 for all e ∈ E , then

$$\min _ { z \in A } { \mathbf 1 } \cdot z = \min _ { z \in A _ { \alpha } } { \mathbf 1 } \cdot z = \alpha f ( E ) - s ( E ).$$

Now, we consider any costs m ∈ R E ≥ 0 . The following theorem is one of our main results.

Theorem 3.9. Let P = P f be the associated polymatroid of a polymatroid function f . Let B f be the base polytope of f . Given s ∈ R E &gt; 0 and m ∈ R E ≥ 0 . Let A h , and α be defined as in (3.5), and (1.11) respectively. For every h ≥ α , let z ∗ h be an optimal solution of the problem min z ∈ A h m z · . Then,

$$m \cdot z _ { h } ^ { * } \geq m \cdot z _ { \alpha } ^ { * } \quad \forall h \geq \alpha.$$

In other words, the polymatroid reinforcement problem is equivalent to min z ∈ A α m z. ·

Proof. Let h ≥ α . Assume that there exists y ∈ A α such that y ≤ z ∗ h . Then

$$m \cdot y \leq m \cdot z _ { h } ^ { * },$$

and by the definition of z ∗ α , we obtain

$$m \cdot z _ { \alpha } ^ { * } \leq m \cdot y.$$

Hence, we have (3.7).

The rest of the proof is to show that such y exists. Let ( αP f ) s be defined as in (3.4), and let y be an ( αP f ) -basic of s z ∗ h . Then, we obtain that y ≤ z ∗ h and s + y is an ( αP f )-basic of s + z ∗ h . The proof is completed if we can show that y ∈ A α , i.e., ( s + )( y E ) = αf E ( ). To that end, we denote

$$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cd

 \cdots \cdots \cdots \cdots \frac { \alpha } { h } ( s + z _ { h } ^ { * } ) \leq ( s + z _ { h } ^ { * } ). \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon$$

By the definition of z ∗ h , we have s + z ∗ h ∈ hB f . Thus, x ∈ αB f , this implies that x E ( ) = αf E ( ). By Lemma 3.3, x is maximal in αP f . Moreover, since x ≤ ( s + z ∗ h ), we have that x is an ( αP f )-basic of s + z ∗ h . Note that s + y is also an ( αP f )-basic of s + z ∗ h . By Definition 3.1 (ii), ( s + )( y E ) = x E ( ) = αf E ( ). The proof is completed.

## 3.3 Polymatroid sparsification

Given a polymatroid function f on E , then f is normalized, nondecreasing, and submodular. We define the set function g as follows:

$$g ( U ) \coloneqq f ( E ) - f ( E \, \sum U )$$

for all subsets U ⊆ E . It follows that g ( ∅ ) = f ( E ) -f ( E ) = 0. For any set A ⊆ B ⊆ E , we have

$$g ( A ) = f ( E ) - f ( E \, \sum A ) \leq f ( E ) - f ( E \, \sum B ) = g ( B ).$$

Furthermore, for all subsets A, B ⊆ E , by definition of g , we have

$$g ( A \cap B ) + g ( A \cup B ) \geq g ( A ) + g ( B ).$$

Hence, the function g is normalized, nondecreasing and supermodular. Next, we associate the contrapolymatroid Q g with g . Notice that for any e ∈ E , we have g ( { } e ) ≥ g ( ∅ ) = 0. Thus, the polyhedron Q g can be described as

$$\dots \dots \dots \dots \dots \dots \\ Q _ { g } = \left \{ x \in \mathbb { R } ^ { E } \colon x ( A ) \geq g ( A ), \forall A \subseteq E \right \}. \\ \intertext { n ( 1. 1 4 ). \, Let c be a constant such that $c>f(E)$. Den}$$

Let C g be defined as in (1.14). Let c be a constant such that c ≥ f ( E ). Denote c to be the vector of all c . Consider the following polyhedron:

$$\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \\ Q _ { g, c } \coloneqq \left \{ x \in \mathbb { R } ^ { E } \colon \mathbf c \geq x, x ( A ) \geq g ( A ), \forall A \subseteq E \right \}. \\ \text{dron is bounded and hence is a polvtoe. Additionally. we define}$$

This polyhedron is bounded and hence is a polytope. Additionally, we define

$$C _ { g, c } \coloneqq \{ x \in Q _ { g, c } \colon x ( E ) = g ( E ) \} \,.$$

We aim to demonstrate that, under some translation, the polytope Q g,c maps to a polymatroid.

Theorem 3.10. Let t : R E → R E such that t ( x ) = -x + c , x ∈ R E . Then, t ( Q g,c ) is a polymatroid.

Proof. Let x ∈ Q g,c , and y = -x + . Then, we have c y ≥ 0. Next, note that

$$x ( A ) \geq g ( A ) & \Leftrightarrow - y ( A ) + c | A | \geq f ( E ) - f ( E \, \sum A ) \\ & \Leftrightarrow y ( A ) \leq - f ( E ) + f ( E \, \sum A ) + c | A |.$$

We define a set function h A ( ) := -f ( E )+ f ( E A \ )+ c A | | . Then, h is normalized, nondecreasing, and submodular. Indeed, by defintion of h , we have that h is normalized, and submodular. For A /subsetnoteql B ⊆ E , we have

$$- f ( E ) + f ( E \, \Lambda \, A ) + c | A | & \leq - f ( E ) + f ( E \, \Lambda \, B ) + c | B | \\ & \Leftrightarrow f ( E \, \Lambda \, A ) - f ( E \, \Lambda \, B ) & \leq c | B \, \Lambda \, A |,$$

which is true because c ≥ f ( E ) ≥ f ( E \ A ). So, the function h is nondecreasing. Therefore, t ( Q r,c ) is a polymatroids.

In the rest of this section, we apply Theorem 3.10 to provide corresponding results from Section 3.2.

Lemma 3.11. Let Q := Q g,c be defined as in (3.11). A vector x ∈ Q is minimal in Q if and only if x E ( ) = g E ( ) = f ( E ) .

Lemma 3.12. Given s ∈ Q , then, Q s := { z ∈ R E ≥ 0 : s -z ∈ Q } is a polymatroid under some translation.

Lemma 3.13. Given s ∈ Q and z ∈ Q s where Q s := { z ∈ R E ≥ 0 : s -z ∈ Q } , then, z is minimal in Q s if and only if ( s -z )( E ) = f ( E ) .

h&gt;

Given a per-unit increasing cost m e ( ) ≥ 0 for each e ∈ E and s ∈ R E &gt; 0 . Let c be a constant such that c ≥ max { f ( E , ) ‖ ‖ s ∞ } . We recall the polymatroid sparsification problem in (1.12) where we replace C g by C g,c and σ = s . In fact, we have C g = C g,c (see Theorem 3.18). The feasible set of the polymatroid sparsification problem is ⋃ F h where F h := { z ∈ R E ≥ 0 : s -z ∈ hC g,c } .

0

Remark 3.14 . Let β := max { h &gt; 0 : s ∈ hQ g } be defined as in (1.17). Since we assume that c ≥ max { f ( E , ) ‖ ‖ s ∞ } , we have that β = max { h &gt; 0 : s ∈ hQ g,c } .

/negationslash

Lemma 3.15. Let β = max { h &gt; 0 : s ∈ hQ g,c } . Then, F h = ∅ if and only if h ≤ β .

Theorem 3.16. Given s ∈ R E &gt; 0 and m ∈ R E ≥ 0 . For every 0 &lt; h ≤ β , let z ∗ h be an optimal solution of the problem min z ∈ F h m z · . Then,

$$m \cdot z _ { h } ^ { * } \geq m \cdot z _ { \beta } ^ { * } \quad \forall h \leq \beta.$$

In other words, the polymatroid sparsification problem is equivalent to min z ∈ F β m z. ·

Proof. This can be proved in the same manner as in the proof of Theorem 3.9.

## 3.4 Relationship between P f and Q g

Given a polymatroid function f on E , recall that f is normalized, nondecreasing, and submodular. Let the set function g be defined as in equation (3.10). In this section, we explore several properties of P f and Q g .

Proposition 3.17. Given a polymatroid function f on E . Let P f be the associated polymatroid of f and B f be the base polytope of f , then

$$P _ { f } = ( B _ { f } - \mathbb { R } _ { \geq 0 } ^ { E } ) \cap \mathbb { R } _ { \geq 0 } ^ { E }.$$

Proof. Let x ∈ ( B f -R E ≥ 0 ) ∩ R E ≥ 0 , then

$$0 \leq x = y - r,$$

$$x \leq y.$$

for some y ∈ B f and r ∈ R E ≥ 0 . Hence,

Because y ∈ P f , we have x ∈ P f . Therefore,

$$( B _ { f } - \mathbb { R } _ { \geq 0 } ^ { E } ) \cap \mathbb { R } _ { \geq 0 } ^ { E } \subset P _ { f }.$$

Let x ∈ P f . Then, there exists x ′ ≥ 0 such that x + x ′ is maximal in P f . By Lemma 3.3, we have that

$$x + x ^ { \prime } \in B _ { f }.$$

Hence,

$$0 \leq x = ( x + x ^ { \prime } ) - x ^ { \prime } \in B _ { f } - \mathbb { R } _ { \geq 0 } ^ { E }.$$

Therefore, P f ⊂ ( B f -R E ≥ 0 ) ∩ R E ≥ 0 .

The proof is completed.

Proposition 3.18. Given a polymatroid function f on E . Let the set function g be defined as in (3.10). Let c be a real number such that c ≥ f ( E ) = g E ( ) . Let Q , C , Q g g g,c , and C g,c are defined as in (1.13), (1.14), (3.11), and (3.12), respectively. Then,

$$C _ { g, c } & = C _ { g }.$$

(ii)

Q

g,c

= (

C

g,c

+

R

E

E

≥

0

≥

0

)

∩

x

∈

R

:

c

≥

x

,

(3.15)

{

}

(iii)

$$Q _ { g } = C _ { g } + \mathbb { R } _ { \geq 0 } ^ { E },$$

Proof. For (i), denote J := { x ∈ R E ≥ 0 : x E ( ) = g E ( ) } and K c := { x ∈ R E ≥ 0 : x ≤ c } . Then, we obtain that J ⊂ K c . Hence

$$C _ { g, c } = Q _ { g, c } \cap J = Q _ { g } \cap K _ { c } \cap J = Q _ { g } \cap J = C _ { g }.$$

By the proof of Theorem 3.10 and Proposition 3.17, we obtain (ii). Finally, for (iii),

$$\text{10 and Proposition 3.17, we obtain (ii).                                                                                                                                                                                                        
                                                                                                                                                                                                        }                                                                                                                                                                                                        Q _ { g } = \bigcup _ { c > f ( E ) } Q _ { g, c } \\ = \bigcup _ { c > f ( E ) } \left ( ( C _ { g, c } + \mathbb { R } _ { \geq 0 } ^ { E } ) \cap K _ { c } \right ) \\ = \bigcup _ { c > f ( E ) } ( C _ { g } + \mathbb { R } _ { \geq 0 } ^ { E } ) \cap \left ( \bigcup _ { c > f ( E ) } K _ { c } \right ) \\ = C _ { g } + \mathbb { R } _ { \geq 0 } ^ { E }.$$

Theorem 3.19. Given a polymatroid function f on E . Let the set function g be defined as in (3.10). Given s ∈ R E &gt; 0 , let α and β be defined as in (1.11) and (1.17). Let P , B , Q f f g , and C g be defined as in (1.7), (1.8), (1.13), and (1.14). Then, for h &gt; 0 ,

- (i) s ∈ hP f if and only if h ≥ α .
- (ii) s ∈ hQ g if and only if h ≤ β .
- (iii) α ≥ β , and s ∈ hB f if and only if h = α = β .

Proof. By definition of α and β , we have (i) and (ii). For (iii), we have that s ∈ αP f and s ∈ βB g , then αf E ( ) ≥ s E ( ) ≥ βg E ( ). Since f ( E ) = g E ( ), we have that α ≥ β . It is well-known that B f = C g , this is because given that x E ( ) = f ( E ), for any subset A ⊆ E ,

$$x ( A ) \leq f ( A ) \Leftrightarrow x ( E ) - x ( E - A ) \leq f ( A )$$

$$\Leftrightarrow f ( E ) - x ( E - A ) \leq f ( A )$$

$$\Leftrightarrow x ( E - A ) \geq f ( E ) - f ( A ).$$

Assume that h = α = β . Then, αf E ( ) = s E ( ) = g E ( ) and s ∈ hB f = hC g .

Assume that s ∈ hB f = hC g . By definition of α and β , we have β ≥ h ≥ α . Note that hf E ( ) = s E ( ) = hg E ( ), we obtain α ≥ h ≥ β . Therefore, h = α = β .

## 4 Matroid reinforcement and sparsification

## 4.1 Some properties of strength and fractional arboricity

In this section, we give some properties for strength and fractional arboricity of matroids. Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let f be the rank function of M . Let the set function g be defined as in (3.10). Let P , B f f , Q g , and C g be defined as in (1.7), (1.8), (1.13), and (1.14).

Lemma 4.1. Given a matroid M E, ( I ) with weights σ ∈ R E ≥ 0 . Let B be the base family of M . Let S σ ( M ) be the strength of M . Let D σ ( G ) be the fractional arboricity of M . If σ e ( ) = 0 for some e ∈ E , we have

$$S _ { \sigma } ( M ) = S _ { \sigma } ( M \, \sum \{ e \} ),$$

and

Proof. For X ⊂ E , we have and

Then,

$$\frac { \sigma ( X ) } { r ( X ) } \leq \frac { \sigma ( X - \{ e \} ) } { r ( X - \{ e \} ) } = \frac { \sigma ( X - \{ e \} ) } { r _ { ( M \overline { \{ } e \} ) } ( X - \{ e \} ) }$$

Based on the definitions of D σ ( M ), we have (4.2). Similarly, we obtain (4.1).

$$D _ { \sigma } ( M ) = D _ { \sigma } ( M \, \smallsetminus \{ e \} ).$$

$$\sigma ( X ) = \sigma ( X - \{ e \} ),$$

$$r ( X ) \geq r ( X - \{ e \} ) = r _ { ( M \overline { \{ e \} } ) } ( X - \{ e \} ).$$

↦

Proposition 4.2. Given a matroid M E, ( I ) with weights σ ∈ R E ≥ 0 . Let B be the base family of M . Let S σ ( M ) be the strength of M . Let D σ ( G ) be the fractional arboricity of M . Then, the functions σ → S σ ( M ) and σ → D σ ( M ) are Lipschitz continuous and monotonically increasing.

↦

Proof. Let σ , σ 1 2 ∈ R E &gt; 0 , and let X 1 and X 2 be optimal for S σ 1 ( M ) and S σ 2 ( M ) respectively. Then, without loss of generality, we assume that S σ 1 ( M ) ≤ S σ 2 ( M ). So,

$$\text{oss or generality, we assume that $\varrho_{\sigma_{1}(\nu) \geq \varkappa_{\sigma_{2}(\nu)$} }. \, \varkappa \circ, \\ \\ S _ { \sigma _ { 2 } } ( M ) - S _ { \sigma _ { 1 } } ( M ) & \leq \frac { \sigma _ { 2 } ( X _ { 1 } ) } { r ( E ) - r ( E - X _ { 1 } ) } - \frac { \sigma _ { 1 } ( X _ { 1 } ) } { r ( E ) - r ( E - X _ { 1 } ) } \\ & = \frac { 1 } { r ( E ) - r ( E - X _ { 1 } ) } \sum _ { e \in X _ { 1 } } ( \sigma _ { 2 } ( e ) - \sigma _ { 1 } ( e ) ) \\ & \leq \frac { 1 } { r ( E ) - r ( E - X _ { 1 } ) } \sum _ { e \in X _ { 1 } } | \sigma _ { 2 } ( e ) - \sigma _ { 1 } ( e ) | \\ & \leq \sum _ { e \in X _ { 1 } } | \sigma _ { 2 } ( e ) - \sigma _ { 1 } ( e ) | \leq \sum _ { e \in E } | \sigma _ { 2 } ( e ) - \sigma _ { 1 } ( e ) | \\ & \leq | E | \| \sigma _ { 2 } - \sigma _ { 1 } \| _ { \infty }. \\ \cdot \| _ { \infty } \text{ is the maximum norm on $\mathbb{R}^{E}$. $ So, the function $\sigma \mapsto S_{\sigma}(G)$ is Lipschitz con}.$$

↦

where ‖ · ‖ ∞ is the maximum norm on R E . So, the function σ → S σ ( G ) is Lipschitz continuous. We have a similar argument for D σ ( G . )

For the monotonicity, assume that σ ≤ σ ′ , then σ A ( ) ≤ σ ′ ( A ) for all A ⊂ E. Therefore S σ ( G ) ≤ S σ ′ ( G ) and D σ ( G ) ≤ D σ ′ ( G ).

## 4.2 Matroid reinforcement

Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 . Let f be the rank function of M . Let α be defined as in (1.11). By Theorem 3.9, the problem (1.9) is equivalent to (1.10). By Remark 3.7, this is equivalent to

$$\min \left \{ m \cdot z \colon z \text{ is maximal in } ( \alpha P _ { f } ) ^ { \sigma } \right \}.$$

Since ( αP f ) σ is a polymatroid, we can use the greedy algorithm to solve this problem. To implement the greedy algorithm, we have that the oracle is equivalent to

$$\ v e \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \text{law} \, \end{cases}$$

/BD

Note that the oracle (4.5) is equivalent to

$$\max \left \{ \epsilon \colon \sigma + z + \epsilon \mathbb { 1 } _ { \{ j \} } \in \alpha P _ { f } \right \}. \\ 4. 5 ) \text{ is equivalent to}$$

/BD

$$\min \left \{ \alpha f ( A ) - ( \sigma + z ) ( A ) \colon j \in A \subset E \right \}.$$

Assume that we have a method to implement the oracle (4.6). Suppose m j 1 ≤ m j 2 ≤ · · · ≤ m j k where k = | E | . We introduce Algorithm 1 for the matroid reinforcement problem (1.5).

Theorem 4.3. Let m ∈ R E ≥ 0 be the cost of increasing elements per unit. Let D σ ( M ) be the fractional arboricity and α = D σ ( M ) . Then, after each iteration of step (3) in Algorithm 1, the matroid M with the new weights σ + z has the fractional arboricity remaining unchanged. When the algorithm terminates and outputs the optimal z , the matroid M = ( E, I ) with weights ( σ + ) z is homogeneous.

## Algorithm 1

```
\frac { \text{Algorithm 1 Algorithm for the matroid reinforcement problem} } { \text{ Input: $M=(E,\mathcal{I}),\sigma,\alpha$} } \text{ Output: Optimal $z$} } \, \frac { 1 } { 2 } \, \colon \, z \leftarrow 0 \, \real \, i \in \{ 1, 2, \dots, k \} \, \text{ do} \, \real \, z ( j _ { i } ) \leftarrow z ( j _ { i } ) + \min \{ \alpha f ( A ) - ( \sigma + z ) ( A ) \colon j _ { i } \in A \subset E \} \, \real \, \real \, \real } \, \real \, \real \, \real } \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \null \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \colon \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \quad \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \real \, \end{cases}
```

```
\overline { \text{ithm 1 Algorithm for the matroid reinforcement problem} } \text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text	$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text#\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{	$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\test{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\test$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text
$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text<$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text}$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text.$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text'$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text`$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text1$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text $\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$
$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text
```

Proof. After each iteration of step (3) of Algorithm 1, the weights are increasing. Then, by Proposition 4.2, the fractional arboricity is increasing as well. In contrast, since the new weights are always in αP f , the fractional arboricity never exceeds α during the process by Theorem 3.19. Therefore, the fractional arboricity remains unchanged during the entire algorithm. When the algorithm terminates, σ + z is maximal in αP f , this means that σ + z ∈ αB f = α co( B ). Therefore, the matroid M = ( E, I ) with weights ( σ + ), with the optimal z z , is homogeneous.

## 4.3 Matroid sparsification

Given a matroid M E, ( I ) with weights σ ∈ R E &gt; 0 and the rank function f . Let β be defined as in (1.17). Follow the same method as in Section 4.2, we obtain Algorithm 2 for the matroid sparsification problem (1.6).

## Algorithm 2 Algorithm for the matroid sparsification problem

```
\frac { \text{Algorithm 2 Algorithm for the matroid sparsification problem} } { \text{ Input: $M=(E,\mathcal{I}),\sigma,\beta$} } }
```

Theorem 4.4. Let m ∈ R E ≥ 0 be the cost of decreasing elements per unit. Let S σ ( M ) be the strength and β = S σ ( M ) . Then, after each iteration of step (3) in Algorithm 2, the matroid with the new weights σ -z has the strength remaining unchanged. When the algorithm terminates and outputs the optimal z , the matroid M = ( E, I ) with weights ( σ -z ) is homogeneous.

Proof. After each iteration of step (3) of Algorithm 2, the weights are decreasing. Then, by Proposition 4.2, the strength is decreasing as well. In contrast, since the new weights are always in βQ g , the strength never go below β during the process by Theorem 3.19. Therefore, the strength remains unchanged during the entire algorithm. When the algorithm terminates, σ -z is maximal in βQ g , this means that σ -z ∈ βC g = β co( B ). Therefore, the matroid M = ( E, I ) with weights ( σ -z ), with the optimal z , is homogeneous.

## 5 Application for graphs

In this section, we consider the matroid reinforcement and matroid sparsification problems for graphic matroids.

## 5.1 An algorithm for computing fractional arboricity

We consider an undirected, connected, and weighted graph G = ( V, E, σ ) with edge weights σ ∈ R E &gt; 0 . Let f be the rank function of the graphic matroid associated with G . Let α be defined as in (1.11), we recall that α = D σ ( G ) where the fractional arboricity of G is defined as:

$$\Phi _ { \sigma } ^ { \quad - \nu \, \Phi ^ { \prime } } \cdots \Phi _ { \sigma } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \sigma } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \nu } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sphi } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \salpha } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sbeta } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \selta } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \seta } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \spha } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sga } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sgo } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \smega } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \svarphi } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \nu } } \cdots \Phi _ { \nu} ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu} ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sphi } } \cdots \Phi _ { \nu \quad \Phi _ { \nu } } \cdots \Phi _ { \nu } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \nu } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _{ \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } } \cdots \Phi _ { \nu } ^ { \quad \Phi _ { \sigma } } \cdots \Phi _ { \nu } ^ { \quad \Phi$$

Theorem 5.1. Let G = ( V, E, σ ) be a weighted connected graph. Let D σ ( G ) be the fractional arboricity of G . Let H be the set of all vertex-induced connected subgraphs of G that contain at least one edge. Let E B denote the set of edges that have both endpoints in each set B ⊆ V . Then

$$\mathbb { m } { 3 } \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon = \cdots \cdots \cdots \cdots \cdots \\ D _ { \sigma } ( G ) = \max \left \{ \frac { \sigma ( E _ { B } ) } { | B | - 1 } \, \colon B \subseteq V, | B | \geq 2 \right \} = \max _ { H \in \mathcal { H } } \frac { \sigma ( E _ { H } ) } { | V _ { H } | - 1 }.$$

Proof. We have three definitions for fractional arboricity:

$$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdot \\ D _ { 1 } \coloneqq D _ { \sigma } ( G ), \quad \ \ D _ { 2 } \coloneqq \max \left \{ \frac { \sigma ( E _ { B } ) } { | B | - 1 } \colon B \subseteq V, | B | \geq 2 \right \}, \quad \ \ D _ { 3 } \coloneqq \max _ { H \in \mathcal { H } } \frac { \sigma ( E _ { H } ) } { | V _ { H } | - 1 }.$$

Let H ′ = ( V H ′ , E H ′ ) be a subgraph which optimizes D 3 . Choose X = E H ′ , then f ( X ) = | V H ′ |-1. Thus, we obtain D 3 ≤ D 1 . Choose B = V H ′ , then D 3 ≤ D 2 .

Let X be an optimizer for D 1 . Then H = ( V X , X ) be the edge-induced subgraph generated by X . Suppose H has m connected components H , H , . . . , H 1 2 m . We want to show that

$$\frac { \sigma ( X ) } { f ( X ) } \leq \max _ { i = 1, \dots, m } \frac { \sigma ( E _ { H _ { i } } ) } { | V _ { H _ { i } } | - 1 }.$$

Notice that for a , . . . , a 1 n &gt; 0 and b , . . . , b 1 n &gt; 0, we have

$$& \quad \begin{array} { c } \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cd. \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cd. \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdots \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cd� \quad \end{array}$$

Therefore,

In particular,

$$\frac { a _ { 1 } + a _ { 2 } + \dots + a _ { n } } { b _ { 1 } + b _ { 2 } + \dots + b _ { n } } \leq \max _ { i = 1, \dots, n } \frac { a _ { i } } { b _ { i } }.$$

$$\frac { \sigma ( X ) } { f ( X ) } & \leq \frac { \sigma ( E _ { H _ { 1 } } ) + \dots + \sigma ( E _ { H _ { m } } ) } { ( | V _ { H _ { 1 } } | - 1 ) + \dots + ( | V _ { H _ { m } } | - 1 ) } \\ & \leq \max _ { i = 1, \dots, m } \frac { \sigma ( E _ { H _ { i } } ) } { | V _ { H _ { i } } | - 1 }.$$

Thus, D 1 ≤ D 3 .

Let B be an optimizer for D 2 . Then K = ( B,E B ) be the vertex-induced subgraph generated by B . Suppose K has m connected components K , K , . . . , K 1 2 m where each component has at least one edge. We want to show that

$$\frac { \sigma ( E _ { B } ) } { | B | - 1 } \leq \max _ { i = 1, \dots, m } \frac { \sigma ( E _ { K _ { i } } ) } { | V _ { K _ { i } } | - 1 }.$$

We have,

$$\frac { \sigma ( E _ { B } ) } { | B | - 1 } & \leq \frac { \sigma ( E _ { K _ { 1 } } ) + \cdots + \sigma ( E _ { K _ { m } } ) } { | V _ { K _ { 1 } } | + \cdots + | V _ { K _ { m } } | - 1 } \\ & \leq \frac { \sigma ( E _ { K _ { 1 } } ) + \cdots + \sigma ( E _ { K _ { m } } ) } { | V _ { H _ { 1 } } | + \cdots + | V _ { K _ { m } } | - m } \\ & \leq \max _ { i = 1, \dots, m } \frac { \sigma ( E _ { K _ { i } } ) } { | V _ { K _ { i } } | - 1 }.$$

Thus, D 2 ≤ D 3 .

It is well-known that the polytope P f defined as in (1.7) can be described as follows:

$$\begin{array} { c } x ( E _ { B } ) \leq | B | - 1 \quad \forall B \text{ such that } \emptyset \neq B \subseteq V ; \\ x \geq 0. \end{array}$$

where E B denotes the set of edges that have both endpoints in B . This fact gives rise to a second proof for the first equality in (5.2).

Next, we give an algorithm for computing the fractional arboricity D σ ( G ). There is a well-known method for dealing with quotients like D σ ( G ). It is described as follows. Recall that α = D σ ( G ) and let b &gt; 0. By (5.2), we have

$$\mu \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ \alpha < b & \Leftrightarrow \max \left \{ \frac { \sigma ( E _ { B } ) } { | B | - 1 } \, \colon B \subseteq V, | B | \geq 2 \right \} < b \\ & \Leftrightarrow \frac { \sigma ( E _ { B } ) } { | B | - 1 } < b \quad \forall B \text{ such that } B \subseteq V, | B | \geq 2 \\ & \Leftrightarrow b ( | B | - 1 ) - \sigma ( E _ { B } ) > 0 \quad \forall B \text{ such that } B \subseteq V, | B | \geq 2 \\ & \Leftrightarrow g ( b ) \coloneqq \min \left \{ b ( | B | - 1 ) - \sigma ( E _ { B } ) \, \colon B \subseteq V, | B | \geq 2 \right \} > 0. \\ \mu \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots.$$

Note that we also have similar statements:

$$\alpha = b \Leftrightarrow g ( b ) = 0,$$

$$\alpha > b \Leftrightarrow g ( b ) < 0.$$

Next, we assume that we have a lower bound b of α , in other words, α ≥ b . Then, we have g b ( ) ≤ 0, let's consider two cases:

- · If g b ( ) = 0, then α = . b

- · If g b ( ) &lt; 0. Let B ∗ be a minimizer of g b ( ), then

$$& b ( | B ^ { * } | - 1 ) - \sigma ( E _ { B ^ { * } } ) < 0 \\ & \Leftrightarrow b ^ { \prime } \coloneqq \frac { \sigma ( E _ { B ^ { * } } ) } { | B ^ { * } | - 1 } > b.$$

Then, b ′ is a better lower bound of α . Based on this argument, we obtain an algorithm for computing α :

## Algorithm 3 Algorithm for computing α Input: G = ( V, E, σ ) Output: α 1: B ← V 2: b ← σ E / ( ) ( | V | -1) 3: while g b ( ) &lt; 0 do 4: B ← a minimizer of g b ( ) 5: b ← σ E ( B ) / ( | B | -1) 6: end while 7: return b, B

The following lemma shows that Algorithm 3 takes at most n = | V | steps.

Lemma 5.2. Assume that g b ( 0 ) &lt; 0 and B 0 is a minimizer of g b ( 0 ) . Denote

$$b _ { 1 } \coloneqq \frac { \sigma ( E _ { B _ { 0 } } ) } { | B _ { 0 } | - 1 }.$$

Let B 1 be a minimizer of g b ( 1 ) . If g b ( 1 ) &lt; 0 , then | B 1 | &lt; B | 0 | .

Proof. Because g b ( 0 ) &lt; 0 and g b ( 1 ) &lt; 0, we have

$$\frac { \sigma ( E _ { B _ { 1 } } ) } { | B _ { 1 } | - 1 } > b _ { 1 } = \frac { \sigma ( E _ { B _ { 0 } } ) } { | B _ { 0 } | - 1 } > b _ { 0 }.$$

Then,

$$0 & < \sigma ( E _ { B _ { 1 } } ) - b _ { 1 } ( | B _ { 1 } | - 1 ) \\ & = \sigma ( E _ { B _ { 1 } } ) - b _ { 0 } ( | B _ { 1 } | - 1 ) + b _ { 0 } ( | B _ { 1 } | - 1 ) - b _ { 1 } ( | B _ { 1 } | - 1 ) \\ & \leq \sigma ( E _ { B _ { 0 } } ) - b _ { 0 } ( | B _ { 0 } | - 1 ) + b _ { 0 } ( | B _ { 1 } | - 1 ) - b _ { 1 } ( | B _ { 1 } | - 1 ) \quad \text{(because $B_{0}$ is a minimizer of $g(b_{0})$)} \\ & = b _ { 1 } ( | B _ { 0 } | - 1 ) - b _ { 0 } ( | B _ { 0 } | - 1 ) + b _ { 0 } ( | B _ { 1 } | - 1 ) - b _ { 1 } ( | B _ { 1 } | - 1 ) \\ & = ( b _ { 0 } - b _ { 1 } ) ( | B _ { 1 } | - | B _ { 0 } | ). \\ - \quad. \quad. \quad. \quad. - \. \quad. - \.$$

Since b 0 -b 1 &lt; 0, we obtain | B 1 | &lt; B | 0 | .

By Lemma 5.2, we conclude that Algorithm 3 will compute D σ ( G ) within at most | V | iterations. The remaining work is to find a way to compute g b ( ) given that g b ( ) ≤ 0. Denote x := σ/b , then finding g b ( ) is equivalent to finding

$$\min \left \{ ( | B | - 1 ) - x ( E _ { B } ) \colon B \subseteq V, | B | \geq 2 \right \}.$$

Let's recall the problem of finding a most-violated inequality for the description (5.3) of P f :

$$\min \left \{ ( | B | - 1 ) - x ( E _ { B } ) \colon \emptyset \neq B \subseteq V \right \}.$$

In general, the problem (5.7) and the problem (5.8) are not equivalent. But note that we have g b ( ) ≤ 0, and when | B | = 1 we have | B | -1 -x E ( B ) = 0. Therefore, in our case, these two problems are equivalent. A network flow algorithm for this problem is known [8].

## A Cunningham's minimum cut formulation.

In [8], Cunnningham gives an algorithm for finding a most-violated inequality for the description (5.3). We recall the algorithm for completeness.

Given x ∈ R E &gt; 0 . As described in [8], we construct a capacitated undirected graph G ′ from G = ( V, E ) as follows.

- · The vertex set of G ′ is V ∪ { r, s } .
- · Every edge e of G is an edge of G ′ with the same endpoints and it has capacity 1 2 x e ( ).
- · For every v ∈ V , there is an edge connecting v and s and it has capacity 1.
- · For every v ∈ V , let δ v ( ) := { e ∈ E : e is incident with v } , there is an edge connecting v and r and it has capacity 1 2 x δ v ( ( )).

Denote the capacity of edges in G ′ by w and B = V \ A . Consider a cut separating r and s in G ′ determined by

$$A \cup \{ r \} \text{ for any } A \subset V.$$

Then, the value of this cut is:

$$\mathfrak { e } \, \text{of this cut is:} \\ \mathfrak { e } = \{ a, b \} \colon a \in A, b \in B } \, w ( e ) + \sum _ { e = \{ r, b \} \colon b \in B } w ( e ) + \sum _ { e = \{ a, s \} \colon a \in A } w ( e ) \\ = \sum _ { e = \{ a, b \} \colon a \in A, b \in B } \frac { 1 } { 2 } x ( e ) + \sum _ { b \in B } \frac { 1 } { 2 } x ( \delta ( b ) ) + | A | \\ = \, x ( E ) - x ( E _ { A } ) + | A |. \\ \text{the set of edges that have both endoints in } A \quad \text{Therefore the nrc}$$

/negationslash

/negationslash

/negationslash where E A is the set of edges that have both endpoints in A . Therefore, the problem (5.8) is equivalent to find a minimum cut A ∪ { r } satisfying A = ∅ . To overcome the condition A = ∅ , we just need to solve | V | minimum cut problems, each one determined by changing the capacity of an edge connecting v and r to ∞ . This is because any cut A ∪ { r } with A = ∅ will not use at least one of these edges.

Run-time complexity for Algorithm 3: | V | 2 minimum-cut calculations. This is because the problem of finding a most-violated inequality for the description (5.3) of P f takes | V | minimum-cut calculations and the number of iterations is at most | V | .

## 5.2 Matroid reinforcement for graphs

In this section, we give a detailed method to implement Algorithm 1.

## Cunningham's minimum cut formulation modification

In [9], Cunningham gives a network-flow algorithm that solves (4.6). Given x ∈ P f and j ∈ E , we want to solve

$$\min \left \{ f ( A ) - x ( A ) \colon j \in A \subset E \right \}.$$

Because we have that x ∈ P f , then a set A that minimizes f ( A ) -x A ( ) over j ∈ A ⊆ E can be required to be of the form E B . Hence, Cunningham modified his minimum cut formulation as follows.

We construct an undirected capacitated graph G ′ from G = ( V, E ) as follows.

- · The vertex set for G ′ is V ∩{ r, s } , where r and s are new vertices that will be the source and sink respectively.
- · Every edge e of G is an edge of G ′ with the same endpoints and it has capacity 1 2 x e ( ).
- · For every v ∈ V , there is an edge connecting v and s and it has capacity 1.
- · For every v ∈ V , let δ v ( ) := { e ∈ E : e is incident with v } , there is an edge connecting v and r . It has capacity 1 2 x δ v ( ( )) if v is not an endpoint of j and has capacity ∞ if v is an endpoint of j .

As shown in [9], (5.9) can be recovered from the value of a minimum cut seperating r and s in G ′ and the edges of a minimum cut (after removing any edges incident with r or s ) form a minimizer for (5.9).

Run-time complexity for Algorithm 1: | V | 2 + | E | minimum-cut calculations. This is due to finding D σ ( G ) and the number of iterations is | E | where each iteration takes 1 minimum-cut calculation.

## 5.3 Matroid sparsification for graphs

In this section, we provide a detailed method to implement Algorithm 2. Given x ∈ Q g and j ∈ E , we want to solve

$$\min \left \{ x ( A ) - g ( A ) \colon j \in A \subset E \right \}.$$

This is equivalent to

$$\min \left \{ x ( A ) + f ( E - A ) \, \colon j \in A \subset E \right \}.$$

By a change of variable B := E -A , the problem (5.10) is equivalent to

$$\min \left \{ f ( B ) - x ( B ) \colon j \notin$$

We can deal with this problem by deleting the edge j from G . Let G ′ = ( V G ′ , E G ′ ) := G -{ } j , then (5.11) is equivalent to

$$\min \left \{ f _ { G ^ { \prime } } ( B ) - x ($$

In fact, this is known as the attack problem, see [9]. Cunningham gives an algorithm for it in [9]. The algorithm requires | E | minimum-cut calculations.

Run-time complexity for Algorithm 2: | V || E | + | E | 2 minimum-cut calculations. This is due to finding S σ ( G ) (we use the algorithm in [9], it requires | V || E | minimum-cut calculations) and the number of iterations is | E | where each iteration takes | E | minimum-cut calculations.

## 5.4 An algorithm for computing spanning tree modulus

Let G = ( V, E, σ ) be a weighted graph with edge weights σ ∈ R E &gt; 0 . Let B be the family of spanning trees of G . In [4], they propose an algorithm for computing spanning tree modulus based on E max (defined as in (2.15)) using Cunningham's algorithm for computing the strength of a graph.

Applying results in [21], we suggest an algorithm for computing spanning tree modulus using Algorithm 3 based on E min (defined as in (2.17)).

Any subgraph which is optimal for the fraction arboricity problem (5.2) is said to be a D-optimal subgraph. First, we find a D-optimal subgraph H of G using Algorithm 3. Then, Theorem 2.7 show that σ -1 η ∗ takes the value ( | V H | -1) /σ E ( H ) on all edges in H . Now, shrink H to a vertex, this results in a shrunk graph G 1 = G/H . Next, find a D-optimal subgraph H 1 of G 1 and σ -1 η ∗ (for the spanning tree modulus of G ) takes the value ( | V H 1 | -1) /σ E ( H 1 ) on the edges of H 1 . Repeat this procedure, each time computes σ -1 η ∗ for at least one edge. Thus, after finite iterations, σ -1 η ∗ will be computed for all edges. A more detailed description of this algorithm is described in Algorithm 4.

```
\begin{array} {
```

Run-time complexity for Algorithm 4: | V | 3 minimum-cut calculations. This is because solving D σ ( G ) takes | V | 2 minimum-cut calculations and the number of iterations is at most | V | .

## References

- [1] Albin, N., Brunner, M., Perez, R., Poggi-Corradini, P., and Wiens, N. Modulus on graphs as a generalization of standard graph theoretic quantities. Conform. Geom. Dyn. 19 (2015), 298-317.
- [2] Albin, N., Clemens, J., Fernando, N., and Poggi-Corradini, P. Blocking duality for p -modulus on networks and applications. Ann. Mat. Pura Appl. (4) 198 , 3 (2019), 973-999.
- [3] Albin, N., Clemens, J., Hoare, D., Poggi-Corradini, P., Sit, B., and Tymochko, S. Fairest edge usage and minimum expected overlap for random spanning trees. Discrete Math. 344 , 5 (2021), Paper No. 112282, 24.
- [4] Albin, N., Kottegoda, K., and Poggi-Corradini, P. An exact-arithmetic algorithm for spanning tree modulus. Preprint .
- [5] Albin, N., Kottegoda, K., and Poggi-Corradini, P. Spanning tree modulus for secure broadcast games. Networks 76 , 3 (2020), 350-365.
- [6] Albin, N., and Poggi-Corradini, P. Minimal subfamilies and the probabilistic interpretation for modulus on graphs. J. Anal. 24 , 2 (2016), 183-208.
- [7] Catlin, P. A., Grossman, J. W., Hobbs, A. M., and Lai, H.-J. Fractional arboricity, strength, and principal partitions in graphs and matroids. Discrete Applied Mathematics 40 , 3 (1992), 285-302.
- [8] Cunningham, W. H. Minimum cuts, modular functions, and matroid polyhedra. Networks 15 , 2 (1985), 205-215.
- [9] Cunningham, W. H. Optimal attack and reinforcement of a network. J. Assoc. Comput. Mach. 32 , 3 (1985), 549-561.
- [10] Edmonds, J. Matroids and the greedy algorithm. Math. Programming 1 (1971), 127-136.
- [11] Edmonds, J. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimization-Eureka, You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5-9, 2001 Revised Papers (2003), Springer, pp. 11-26.
- [12] Fujishige, S. Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of Operations Research 5 , 2 (1980), 186-196.
- [13] Fujishige, S. Theory of principal partitions revisited. Research Trends in Combinatorial Optimization: Bonn 2008 (2009), 127-162.
- [14] Fulkerson, D. R. Blocking polyhedra. In Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969) (1970), Academic Press, New York, pp. 93-112.
- [15] Fulkerson, D. R. Blocking and anti-blocking pairs of polyhedra. Math. Programming 1 (1971), 168-194.

- [16] Nash-Williams, C. S. J. Decomposition of finite graphs into forests. Journal of the London Mathematical Society 1 , 1 (1964), 12-12.
- [17] Nash-Williams, C. S. J. A. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc. 36 (1961), 445-450.
- [18] Pitsoulis, L. S. Topics in matroid theory . SpringerBriefs in Optimization. Springer, New York, 2014.
- [19] Ruci´ski, A., and Vince, A. n Strongly balanced graphs and random graphs. Journal of graph theory 10 , 2 (1986), 251-264.
- [20] Schrijver, A. Combinatorial optimization. Polyhedra and efficiency. Vol. B , vol. 24,B of Algorithms and Combinatorics . Springer-Verlag, Berlin, 2003. Matroids, trees, stable sets, Chapters 39-69.
- [21] Truong, H., and Poggi-Corradini, P. Fulkerson duality for modulus of spanning trees and partitions. arXiv preprint arXiv:2306.15984 (2023).
- [22] Truong, H., and Poggi-Corradini, P. Modulus for bases of matroids. arXiv preprint arXiv:2404.05650 (2024).
- [23] Tutte, W. T. On the problem of decomposing a graph into n connected factors. J. London Math. Soc. 36 (1961), 221-230.
Huy Truong Pietro Poggi-Corradini
Matroid reinforcement and sparsification
Homogeneous matroids are characterized by the property that strength equals
fractional arboricity, and arise in the study of base modulus [22]. For graphic
matroids, Cunningham [9] provided efficient algorithms for calculating graph
strength, and also for determining minimum cost reinforcement to achieve a
desired strength. This paper extends this latter problem by focusing on two
optimal strategies for transforming a matroid into a homogeneous one, by either
increasing or decreasing element weights. As an application to graphs, we give
algorithms to solve this problem in the context of spanning trees.