The arboricity of a graph is the minimum number of forests it can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they only approximated the arboricity as a value without computing a corresponding forest partition, as they operate on the related pseudoforest partitions or the dual problem. We propose an algorithm for converting a partition of @math pseudoforests into a partition of @math forests in @math time, where @math is the inverse Ackermann function, when @math expected time is allowed for pre-computation of a perfect hash function. Without perfect hashing, we obtain @math with a data structure by Brodal and Fagerberg that stores graphs of arboricity @math . For every fixed @math , the latter result implies a constructive @math -approximation algorithm with runtime @math by using Kowalik's approximation scheme for pseudoforest partitions. Our algorithm might help in designing a faster exact arboricity algorithm. We also make several remarks on approximation algorithms for the pseudoarboricity and the equivalent graph orientations with smallest maximum indegree, and correct some mistakes made in the literature.
In this paper, we develop some algorithmic aspects of the fractional arboricity of a graph in order to study some new approaches for graph clustering. For a given undirected graph G ( V , E ) with m edges and n vertices, the fractional arboricity γ ( G ) measures the maximum edge density of the subgraphs of G ( V , E ) . It is the fractional covering number of the corresponding graphic matroid. The fractional arboricity, for applications in networks reliability or the approximation of the chromatic number of the graphs, has been studied for many years. There are some algorithms in polynomial time to compute the fractional arboricity and its integer part. But, for large graphs such as the graph of the Web or graphs of social networks, the exact algorithms are not fast enough for practical use. That is why we describe a new FPTAS to compute an e -approximation of the fractional arboricity (with e 0 as small as desired). Our algorithm uses the principle of the multiplicative weights update method, needs a memory of size O ( m ) and has a complexity of O ( m log 2 ( m ) log ( m n ) e 2 ) . We also give a 2-approximation of γ ( G ) with computation time O ( m ) , which is a quick preprocessing for the main algorithm. Finally, we present a fast algorithm to extract a subgraph which achieves the value of the approximation of the fractional arboricity.