COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2009

In the relay placement problem, the input is a set of sensors (given by a set of points in the plane) and a number r>=1, the communication range of a relay. In the one-tier version of the problem the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays, such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance one otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors. We present a 3.11-approximation algorithm for the one-tier version and a PTAS for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P!=NP.

This is joint work with Alon Efrat, Poornananda Gaddehosur, Joe Mitchell, Valentin Polishchuk, and Jukka Suomela.

Previous Talks

Theoretical models of ultrawideband (UWB) radio channels indicate that pairs of UWB radio transceivers measure their common radio channel with a high degree of agreement. In addition, third parties are not able to accurately estimate the state of this common channel. These properties allow generation of secret keys to support secure communications from UWB channel measurements. In this talk, the results of UWB propagation studies are shown that validate the required properties to support secret key generation in a typical indoor environment. Furthermore, key generation algorithms that are employed on the measured data will be introduced. It is shown that key lengths in the order of thousands of bits are obtained which are capable of supporting most popular cryptographic systems. The presentation is also going to report measurements of the spatial and temporal correlation of the UWB channel from which the relative privacy of the secret keys and the rate of secret key generation may be determined.

Byzantine Agreement is a fundamental problem in distributed computing, that is- design a protocol to bring processors to agreement on a bit despite a fraction of bad processors behaving to disrupt the outcome. First proposed in 1980, it was proved impossible to solve deterministically in the full information asychronous model which launched some of the early work on randomized algorithms. As the only (randomized) solutions required exponential time, or assumptions of private channels, this spurred the field of cryptography to develop concepts like multiparty secure computation.

Previously, I described a polylog time distributed protocol for the synchronous model to choose a small robust group of processors which can then run Byzantine agreement, leader election, or compile info from processors in a fast, reliable way. The adversary can be assumed to know the messages sent even before it sends its messages in the same round and can be unbounded in computational power. However we do not allow the adversary to dynamically determine which processes to corrupt as the protocol proceeds.

Now through an interesting application of averaging samplers, we extend our results to the much more difficult asynchronous model, bringing the time bounds down from exponential to polylog.

This is joint work with Bruce Kapron, David Kempe, Jared Saia, and Vishal Sanwalani.

Fullerenes are all-carbon molecules with a polyhedral structure in which each carbon atom is bonded with three other carbon atoms and each face of the polyhedron is a hexagon or pentagon. Nanotubes are included in this theoretically infinite group of molecules that were discovered in 1985, and since then fullerenes have received much study.

Finding a maximum independent set of fullerene molecular graphs is of interest from mathematical, computational, and chemical points of view. Such a set can be used to model the bond locations of bulky addends under the assumption that they are too large to bond to adjacent carbon atoms. The problem of determining the maximum independent set order is NP-hard for the class of cubic planar graphs and the complexity for the fullerene subclass was previously unknown. This talk sketches a linear-time algorithm for solving the maximum independent set problem for fullerenes.

Analysis showed that the resulting molecule under the vertex independence model is not always stable. A new model, the closed-shell independent set, adds some restrictions to the rule of non-adjacency to ensure stability of the resulting molecule after the addition of bulky addends. A backtracking algorithm for finding a maximum closed-shell independent set of a fullerene molecule will be presented along with several enhancements that improve the running time.

This is joint work with Wendy Myrvold and Patrick Fowler and extends the work of Jack Graver.

Friday May 15 at 2:30pm in ECS 660
CanaDAM Practice Talks

We consider here some isoperimetric problems on the infinite binary tree T, whose leaves are all at the same level. The main quantity of interest is d(n), the minimum number of edges in a cut that has n vertices of T on one side and the rest of T on the other. A simple recurrence relation for d(n) is derived, giving rise to an algorithm that uses O(n) arithmetic operations to evaluate d(n). We also show that d(n) is equal to the least number of parts in any partition of n into parts that are of the form +P or -P where P is one less than a power of 2. (This is joint research with Anita Das and Sunil Chandran.)

PolyVenn diagrams are drawn using polyominoes on the integer lattice, where the curves are perimeters and the intersections are smaller polyominoes. Minimum-area Venn diagrams occur when each region in the full diagram is exactly one unit square. We show such diagrams exist in bounding boxes of dimension 2^r X 2^c whenever 0 < c < 2r + 2. We also show that we can expand an existing minimum-area Venn diagram to produce another that fits into a 2^(r+1) X 2^(c+2) bounding box.

Tuesday May 19 at 2:30pm in ECS 660
CanaDAM Practice Talks

A graph G is gamma-vertex-critical if gamma(G-v) < gamma(G) for every vertex v in V(G)(where gamma(G) denotes the domination number of G). Fulman, Hanson and MacGillivray showed that the diameter, d, of a gamma-vertex-critical graph G satisfies d <= 2(gamma(G)-1) and provided graphs which show that this bound is sharp. We employ their technique to find an upper bound on the diameter of independent domination vertex-critical, total domination vertex-critical, and paired domination vertex-critical graphs. We also present graphs which attain equality in the bounds.

A dichotomy theorem for the complexity of homomorphisms to fixed local tournaments is described. The local tournaments for which the problem is polynomial are those which have the X-underbar property or are instances of the graft extension. The problem is NP-complete for all other fixed local tournaments. (This is joint work with Joergen Bang- Jensen and Jacobus Swarts.)

De Bruijn cycles are circular binary strings of length 2ⁿ that contain every binary string of length n exactly once as a substring. This talk describes the first construction for fixed-density de Bruijn cycles, which are circular strings of length (n choose k) where each binary string of length n containing k ones is contained exactly once as a shorthand substring.

Friday May 22 at 2:30pm in ECS 660
CanaDAM Practice Talks

Let H be a subgraph of G. A rational H-decomposition of G is a nonnegative rational weighting of the copies of H in G such that every edge of G has total inherited weight equal to 1.

Motivated by applications in design theory and statistics, we discuss the existence problem for rational H-decompositions of graphs G which have high minimum degree. Estimates on eigenvalues in the Johnson scheme play a central role.

A torus is a surface shaped like a doughnut. A topological obstruction for the torus is a graph G with minimum degree three that is not embeddable on the torus but for all edges e, G-e is torus embeddable. A minor order obstruction has the additional property that for all edges e, G contract e is also torus embeddable. The long-term goal of our research is to find all the obstructions to the torus, thereby formulating a Kuratowski-type theorem for non-toroidal graphs. In this talk, we will provide an overview of the research to date and discuss recent progress, including exhaustive searches, corrections to previous results, and structural characterizations that will likely guide our focus for finding and proving complete the set of all torus obstructions.

Fullerenes are cubic planar graphs having twelve pentagonal faces and all remaining faces hexagonal. These graphs model fullerene molecules and finding a maximum independent set is of interest from mathematical, computational, and chemical points of view. The problem of determining the maximum independent set order is NP-hard for general cubic planar graphs and the complexity for the fullerene subclass was previously unknown. This talk sketches a linear time algorithm for solving the maximum independent set problem for fullerenes.

A (k+2)-net of order n is equivalent to k mutually orthogonal Latin squares (MOLS) of order n. This talk will begin with some background on MOLS of order (4m+2). In 1989 Lam, Thiel and Swiercz ruled out the existence of a projective plane of order ten by computer search. I will include a brief discussion of their block-building technique.

The main result is a classification of eleven types of combinatorial structures, some of which must appear in any 6-net of order ten. Various block designs and pairwise balanced designs related to the structures will be exhibited. This work is motivated by the quest for a better upper bound on the maximum number of MOLS of order ten.

This talk is based on part of my Ph.D. thesis, supervised by Dr. Peter Dukes.