Midwest Theory Day F A L L   2 0 0 1

Abstracts

New Themes in the All-Pairs Shortest Path (APSP) Problem: A Survey
Chandra N. Sekharan, Loyola University of Chicago (chandra@cs.luc.edu)

The problem of computing the shortest distances between all pairs of vertices and of obtaining the shortest paths in an unweighted, undirected graph is well-known and thoroughly researched in the area of applied algorithms. The APSP problem is closely tied to computing the diameter of a graph. Variants of the APSP problem include approximating the shortest distances, and query versions. This talk will survey results in this area with a focus on special classes of graphs such as chordal graphs, and graphs with forbidden subgraph characterizations. Open problems will be identified.

Co-author: John Del Greco.

Select References:
1. R. Seidel. On all-pairs shortest-path problem, in Proc. 25th ACM STOC, Canada 1992, 745-749.
2. R. Sridhar, K.Han, Chandra N. Sekharan, Efficient Algorithms for Shortest distance Queries on Special classes of Polygons, Theoretical Computer Science, vol. 140, 1995, pp.291-300.
3.Corneil D.G., Dragan F.F., Habib M. and Paul C."Diameter Determination on Restricted Graph Families" Discrete Appl. Math. 113 (2001), 143-166.
4. A. Brandstädt, Chepoi V.D. and Dragan F.F. "Distance approximating trees for chordal and dually chordal graphs", Journal of Algorithms. 30 (1999), 166-184.
5. K. Han, Chandra N. Sekharan, R. Sridhar. "Unified All-Pairs Path Algorithms in the Chordal Hierarchy", Discrete Applied Mathematics, vol. 77, (1997), pp. 59-71.
6. J. Del Greco, Chandra N. Sekharan, R. Sridhar. "Fast Parallel Reordering and Isomorphism testing of k-trees", Algorithmica, 2001.
7. Dragan F.F. "Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach", (extended abstract)
Proc. 27th International Workshop ''Graph-Theoretic Concepts in Computer Science''(WG'01), June 2001, Springer, Lecture Notes in Computer Science 2204, pp. 103-116.

Multichannel Communication and Vertex Labeling of Graph Products
Tanya Berger-Wolf, UIUC (tanyabw.uiuc.edu)

We consider the problem of communication over multiple channels in which channels can fail and the information sent over those channels is lost. The goal is to create an encoding that minimizes the absolute difference between the received and the original information while having as little redundancy as possible. Depending on the type of data, error measure, and type of channel failure, the problem is equivalent to different classical problems in graph theory: bandwidth and wirelength (also known as linear arrangement, edgesum, and, in the matrix domain, envelope) of product graphs. We give sharp lower and upper bounds for the bandwidth of clique products (joint work with L. H. Harper and Mitch Harris) and an optimal solution for grid graph wirelength.

Load Balancing Multiweight Geometric Problems
Andy Poe, Northern Michigan U. (apoe@nmu.edu)

A new load balancing algorithm is proposed for biweighted graphs with a geometric basis. The load balancing is based upon an iterated use of the ham sandwich theorem. A basic algorithm is presented, along with a variant that drastically improves the running time while only slightly degrading the load balance. These algorithms are compared to previous approaches for general purpose load balancing for biweighted graphs. It is shown that utilizing the geometric basis of the graphs yields superior load balancing, and that this can be achieved with less processing time.

Generalization Bounds for Linear Learning Algorithms
Ashutosh Garg, UIUC (ashutosh@uiuc.edu)

We study generalization properties of linear learning algorithms and develop a data dependent approach that is used to derive generalization bounds that depend on the margin distribution. Our method makes use of random projection techniques to allow the use of existing VC dimension bounds in the effective, lower, dimension of the data. Comparisons with existing generalization bound show that our bounds are tighter and meaningful in cases existing bounds are not. Our methods is also shown to be useful as an analysis tool, alternative to learning curves.

Phase Space Properties of Synchronous and Sequential Dynamical Systems
Predrag Tosic, UIUC (p-tosic@cs.uiuc.edu)

A class of graph automata, viewed as discrete dynamical systems, has been proposed as an abstract model for computer simulation of large-scale, complex infrastructures, from traffic systems to mobile communication networks. Depending on whether the states of the nodes in these automata are updated sequentially or in parallel, two main subclasses are considered: sequential dynamical systems (SDS) and synchronous dynamical systems (SyDS). The dynamics of SDSs and SyDSs is explored by studying their phase space properties. We summarize some recent results on algorithmic aspects and computational complexity of determining some of these phase space properties for several SDS and SyDS classes of interest, and outline some of the directions for current and future investigations.

Some Karp-Lipton-Type theorems based on S₂
Venkatesan Chakaravarthy, U. Wisconsin, Madison (venkat@cs.wisc.edu)

We prove a lowness theorem for the symmetric alternation class (S_2). Using the theorem, we obtain some Karp-Lipton-Type theorems for various complexity classes. Under assumptions about containment of various complexity classes in P/poly and (NP\cap coNP)/poly, we obtain collapses to S_2 and to S_2[NP\cap coNP], respectively. For example, we show that if NP is contained in (NP\cap coNP)/poly, then the polynomial hierarchy collapses to S_2[NP\cap coNP]. Previously, under either kind of assumptions, the strongest known such collapses were to ZPP^NP. Thus it seemed both assumptions yield same results. As S_2[NP\cap coNP] is not known to be contained in S_2, our results show that the collapse consequences from the two kinds of hypothesis currently differ. As it was shown recently that S_2[NP\cap coNP] is contained in ZPP^NP, our results also strengthen the collapse results for a wide variety of classes.

Joint work with J. Cai, L. Hemaspaandra, and M. Ogihara.

The distribution of Squarefree Smooth integers in Short Intervals
Denis Charles, U. Wisconsin, Madison (cdx@cs.wisc.edu)

We show that for every e > 1/2, d > 0 and large enough X, the intervals [X ... X + X^e] contains integers that are divisible only by primes <= X^d and are not divisible by any perfect square. Results such as this play an important role in the rigorous analysis of the running time of several factoring algorithms, most notably the Elliptic Curve Method of Lenstra.

Separating the Multiparty Communication Hierarchy
Thomas P. Hayes, U. Chicago (hayest@math.uchicago.edu)

In the multiparty communication complexity model due to Chandra, Furst, and Lipton (1983), each of k players has an input stuck on his forehead, so that each player can see k-1 of the k inputs. The players then try to collaboratively evaluate a function f, which depends on all k inputs. The players can only communicate by taking turns writing bits on a blackboard; the communication complexity of f is the total number of bits required in the worst case.

In this context, we prove that "k+1 heads are better than k." More precisely, for every fixed k, there is an explicit family of functions on n bits which requires \Omega(n) bits of communication for k players, but only O(1) bits of communication for k+1 players. This improves an earlier result by V. Grolmusz (1995). Expander-like graphs play a key role in the construction.

Recognizing String Graphs in NP
Daniel Stefankovic, U. Chicago (stefanko@cs.uchicago.edu) and Marcus Schaefer, DePaul (MSchaefer@cti.depaul.edu)

A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices reflects that the corresponding curves intersect. We show that string graphs can be recognized in NP. The recognition problem was not known to be decidable until very recently, when two independent papers established exponential upper bounds on the number of intersections needed to realize a string graph (Pach, Toth, and Schaefer, Stefankovic, 2001). These results implied that the recognition problem lies in NEXP. In the present paper we improve this by showing that the recognition problem for string graphs is in NP, and therefore NP-complete, since Kratochvil showed in 1991 that the recognition problem is NP-hard. The result has consequences for the computational complexity of problems in graph drawing, and topological inference.

The paper is available online. Authors: Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic.

On the complexity of listing minimal hitting sets
Ken Takata, U. Illinois, Chicago (takata@math.uic.edu)

The problem of listing the minimal hitting sets of a simple hypergraph in polynomial time in the size of the input and the output is a longstanding open problem in the area of enumeration algorithms. We show that the well-known sequential approach studied since the 1960's is not a polynomial algorithm in the above sense, even if we allow a optimal ordering of the edges. The proof uses hypergraphs based on read-once formulas.

A Polynomial Time Algorithm for Bistable Roommates Problem
Teo Chung-Piaw, Northwestern University and National University of Singapore (fbateocp@nus.edu.sg)

In a recent paper, Weems (1999, JCSS) introduced the concept of bistable matchings, which are matchings that are stable with respect to both the original and reversed preference lists. For the bistable marriage problem, Weems described an elegant way of adapting the original Gale-Shapley algorithm to find a bistable matching, if one exists, and showed that several structural results known for the stable marriage problem hold for the bistable version as well. However, Weems left open analogous questions for the bistable roommates problem. We show that the existence of bistable roommates solution can be resolved in polynomial time using linear programming. In addition, we show that several bistability results for the bistable marriages and roommates problem become transparent using the polyhedral approach. This technique has been used recently by the authors to address the classical stable marriage problem.

Joint work with Jay Sethuraman, Columbia University.