Efficient processing of hierarchical graphs
Is Version Of
The standard representation of a graph is a list of its vertices and edges. However, graphs encountered in some areas have structural regularities that allow them to be represented using considerably less space. Typically, such a succinct encoding consists of a list of basic parts and a set of instructions for assembling the graph from the parts. Several models for succinctly representing graphs and other structures have been studied in the past. These models are capable of representing a graph using space polynomial in the logarithm of the size of the graph. Because of the potentially large difference in size between a graph and its description, it is natural to ask whether there are any problems that can be solved in time polynomial in the size of the succinct description, rather than in the size of the graph. It is known that even simple graph problems become NP-hard or worse under most models for succinct representation. Two exceptions are dynamic graphs and, the model we study, hierarchical graphs;A hierarchical graph [gamma] is a list of graphs and a set of rules describing how to attach the graphs together to form X([gamma]), the graph [gamma] represents. A hierarchical algorithm is an algorithm that, given [gamma], solves some problem defined on X([gamma]). Not every polynomially-solvable graph problem has a polynomial-time hierarchical algorithm. However, polynomial-time hierarchical algorithms for many problems have been developed using a framework called the bottom-up method;We develop a generalization of the bottom-up method that we use to construct and analyze hierarchical algorithms. Our method provides a uniform setting in which to present our algorithms, as well as many developed by other researchers. The problems we study belong to three classes: connectivity augmentation, subgraph homeomorphism, and matroid optimization. The P-connectivity augmentation problem, where P is a connectivity property, is to determine the number of edges that must be added to a graph to satisfy P. We present polynomial-time hierarchical algorithms for bridge-connectivity, biconnectivity, and strong-connectivity augmentation. Series-parallel and outer-planar graphs can be characterized by sets of forbidden graphs closed under homeomorphism. We present linear-time hierarchical algorithms that determine if X([gamma]) is series-parallel or outer-planar, and a polynomial-space hierarchical algorithm that generates a forbidden subgraph of X([gamma]) when one exists. The matroid optimization problem we consider is that of computing costs of optimum bases of matroids defined on graphs. We identify two infinite families of matroids for which polynomial-time hierarchical algorithms for this problem exist. We also develop polynomial-space hierarchical algorithms that generate optimum bases.