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.
Kowalik's approximation scheme @cite_15 works by terminating Dinitz's algorithm early. It computes an @math -orientation in time @math . The aforementioned greedy algorithm computes an acyclic @math -orientation @cite_3 @cite_36 and a subgraph of density at least @math @cite_4 @cite_22 @cite_27 @cite_31 in linear time. It repeatedly removes the vertex of minimum degree and orients its unassigned edges towards it. Georgakopoulos and Politopoulos @cite_31 give a generalization to hypergraphs. Charikar @cite_27 and Khuller and Saha @cite_22 address directed graphs. The fractional orientation problem is dual to the densest subgraph problem @cite_27 .
@cite_31 @cite_4 @cite_22 @cite_36 @cite_3 @cite_27 @cite_15
2104146203 2165621523 1500512125 1044639830 2079535727 1535144194 1703925482
A data structure for representing a set of n items from a umverse of m items, which uses space n + o(n) and accommodates membership queries m constant time is described. Both the data structure and the query algorithm are easy to mplement. Given an undirected graph G = (V ,E ), the density of a subgraph on vertex set S is defined as @math , where E (S ) is the set of edges in the subgraph induced by nodes in S . Finding subgraphs of maximum density is a very well studied problem. One can also generalize this notion to directed graphs. For a directed graph one notion of density given by Kannan and Vinay [12] is as follows: given subsets S and T of vertices, the density of the subgraph is @math , where E (S ,T ) is the set of edges going from S to T . Without any size constraints, a subgraph of maximum density can be found in polynomial time. When we require the subgraph to have a specified size, the problem of finding a maximum density subgraph becomes NP -hard. In this paper we focus on developing fast polynomial time algorithms for several variations of dense subgraph problems for both directed and undirected graphs. When there is no size bound, we extend the flow based technique for obtaining a densest subgraph in directed graphs and also give a linear time 2-approximation algorithm for it. When a size lower bound is specified for both directed and undirected cases, we show that the problem is NP-complete and give fast algorithms to find subgraphs within a factor 2 of the optimum density. We also show that solving the densest subgraph problem with an upper bound on size is as hard as solving the problem with an exact size constraint, within a constant factor. A succint representation of a graph is a widely studied problem. A number of criteria can be used to determine the succinctness of the representation. We examined the representation of a graph in these two aspects: 1. The space complexity of the representation. In graphs of bounded arboricity, the total complexity of all maximal complete bipartite subgraphs is O(n). We described a linear time algorithm to list such subgraphs. The arboricity bound is necessary: for any constant k and any n there exists an n-vertex graph with O(n) edges and (nlog n)k maximal complete bipartite subgraphs Kk,l. We study the problem of finding highly connected subgraphs of undirected and directed graphs. For undirected graphs, the notion of density of a subgraph we use is the average degree of the subgraph. For directed graphs, a corresponding notion of density was introduced recently by Kannan and Vinay. This is designed to quantify highly connectedness of substructures in a sparse directed graph such as the web graph. We study the optimization problems of finding subgraphs maximizing these notions of density for undirected and directed graphs. This paper gives simple greedy approximation algorithms for these optimization problems. We also answer an open question about the complexity of the optimization problem for directed graphs.