Approximation Algorithms For Graph Problems
Open Access
- Author:
- Kasiviswanathan, Shiva Prasad
- Graduate Program:
- Computer Science
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- July 25, 2008
- Committee Members:
- Martin Furer, Committee Chair/Co-Chair
Piotr Berman, Committee Member
Woodrow Dale Brownawell, Committee Member
Sofya Raskhodnikova, Committee Member
Adam Davison Smith, Committee Member - Keywords:
- Geometric Disk Graph
Perfect Matching
Subgraph Isomorphism
Approximation Algorithm
Graph theory
Graph Spanner - Abstract:
- This thesis studies approximation algorithms for two fundamental problems arising in graph theory: counting copies of one graph in another graph and estimating distances in geometric graphs. In the first part of this thesis, we look at the problem of counting the number of copies of one (template) graph in another (base) graph. This is the counting version of the subgraph isomorphism problem and is #P-complete. We present the first general subcase of this problem which is almost always efficiently approximable. The template families for which we almost always obtain an efficient approximation algorithm (formally captured by the notion of a fully polynomial randomized approximation scheme) include graphs of degree at most two, bounded-degree forests, bounded-width grid graphs, subdivisions of bounded-degree graphs, and major subclasses of outerplanar graphs, series-parallel and planar graphs. As a simple consequence, we also obtain a fully polynomial randomized approximation scheme for counting all cycles in a random graph (solving an open problem of Frieze and McDiarmid). We also provide a general technique which can easily be applied to proving many more similar results. We then investigate the famous #P-complete problem of counting perfect matchings in a graph. For this problem, we present a simple randomized algorithm. The algorithm runs in time almost linear in the size of the input adjacency matrix and is a randomized approximation scheme for almost all graphs. This algorithm is faster than the previous best algorithm of Chien by a factor on n (number of vertices in the graph). In the second part of this thesis, we present algorithms for constructing approximate sparse representations of geometric intersection graphs. Given a collection of geometric objects, their intersection graph is an undirected graph that has one vertex per object, and connects two objects by an edge whenever the intersection of the two objects is nonempty. A disk graph is an intersection graph of a set of disks with arbitrary radii in the plane (the generalization to higher dimensions is known as a ball graph). We present the first algorithm for constructing sparse (1+epsilon)-spanners for ball graphs. The algorithm takes sub-quadratic time. For the special case where all the balls have the same radius, we show that the spanner construction has complexity almost equivalent to the construction of a Euclidean minimum spanning tree. We also present efficient algorithms for answering approximate distance queries in ball graphs. Disk graphs have been widely used to model wireless ad hoc networks. Spanners and distance queries are used for topology control and routing in these networks.