Transforming a graph into a 1-balanced graph

Let GG be a non-trivial, loopless graph and for each non-trivial subgraph HH of GG, let g(H)=|E(H)||V(H)|−ω(H). The graph GG is 1-balanced if γ(G)γ(G), the maximum among g(H)g(H), taken over all non-trivial subgraphs HH of GG, is attained when H=GH=G. This quantity γ(G)γ(G) is called the fractional arboricity   of the graph GG. The value γ(G)γ(G) appears in a paper by Picard and Queyranne and has been studied extensively by Catlin, Grossman, Hobbs and Lai. The quantity γ(G)−g(G)γ(G)−g(G) measures how much a given graph GG differs from being 1-balanced. In this paper, we describe a systematic method of modifying a given graph to obtain a 1-balanced graph on the same number of vertices and edges. We obtain this by a sequence of iterations; each iteration re-defining one end-vertex of an edge in the given graph. After each iteration, either the value γγ of the new graph formed is less than that of the graph from the previous iteration or the size of the maximal γγ-achieving subgraph of the new graph is smaller than that of the graph in the previous iteration. We show that our algorithm is polynomial in time complexity. Further ways to decrease the number of iterations are also discussed.