The P vs. NP-complete dichotomy of some challenging problems in graph theory

The Clay Mathematics Institute has selected seven Millennium Problems to motivate research on important classic questions that have resisted solution over the years. Among them is the central problem in theoretical computer science: the P vs. NP problem, which aims to classify the possible existence of efficient solutions to combinatorial and optimization problems. The main goal is to determine whether there are questions whose answer can be quickly checked, but which require an impossible long time to solve by any direct procedure. In this context, it is important to determine precisely what facet of a problem makes it NP-complete. We shall discuss our contribution to the P vs. NP-complete dichotomy through the classification of some long-standing problems in important areas of graph theory: perfect graphs, intersection graphs, and structural characterization of graph classes. More precisely, we have shown that Chvatal's SKEW PARTITION is polynomial and that Roberts-Spencer's CLIQUE GRAPH is NP-complete. We have also solved the dichotomy for Golumbic-Kaplan-Shamir's SANDWICH problem. We shall describe two examples where we can determine the full dichotomy: The edge-coloring problem for graphs with no cycle with a unique chord, and the three nonempty part sandwich problem. Open problems are discussed: the stubborn problem for list partition; the chromatic index of chordal graphs; the recognition of split clique graphs.

Generalizations of interval graphs motivated by constraint satisfaction

Recently, interval graphs have naturally arisen in the context of constraint satisfaction problems. Progress in understanding what structures make CSP's tractable suggests generalizations and analogues of interval graphs. I will discuss obstruction characterizations and recognition algorithms for these generalizations. Applications to the CSP dichotomy problem will also be mentioned. This is joint work with Tomas Feder, Jing Huang, and Arash Rafiey.

Conflict and Tolerance in the Representation of Graphs Canceled

There are a large number of graph classes which can be described using roughly the following paradigm: each vertex is assigned something measuring its size and something measuring its tolerance. If the combined sizes exceed the combined tolerances, then there is a conflict and the corresponding vertices are adjacent in a conflict graphM. A representation of a graph of this type will be called a conflict-tolerance representation.

So far the size of a vertex has been measured in two primary ways: by a set and by a number. In the set model, the combined size of two vertices is usually mea- sured in terms of the intersection of the sets representing those vertices. In both models, tolerances have ordinarily been given as pure numbers which must be combined by means of a suitable coupling function. Recently, however, some new types of intersection graphs have been introduced which can be regarded as having non-numeric tolerances.

After briefly outlining the history of the subject, this survey will focus on recent developments and open problems.

Edge intersection graphs of paths on trees and grids

Let P be a collection of nontrivial simple paths on a host graph H. The edge intersection graph of P, denoted by EP_H(P), has vertex set that corresponds to the members of P, where two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in H. An undirected graph Γ is called an edge intersection graph of paths in a tree (EPT) if Γ = EP_T(P) for some P and tree T. Similarly, Γ is called an edge intersection graph of paths in a grid (EPG) if Γ = EP_G(P) for some P and grid G. The EPT and EPG graphs can be useful in network and circuit applications, where scheduling and layout problems are often equivalent to coloring an EPT or EPG graph.

In this invited lecture, we will survey the mathematical and algorithmic results on various types of EPT and EPG graphs and some of their generalizations, together with several restrictions on the representations. The class of EPT graphs was first investigated by Golumbic and Jamison in two papers appearing in 1985, and subsequently, further research has been carried out by a number of algorithmic graph theorists. In a series of papers during the past 5 years, Golumbic, Lipshteyn and Stern studied the hierarchy of related EPT graph classes giving some structure theorems.

Very recently, Golumbic, Lipshteyn and Stern introduced EPG graphs, proving that every graph is an EPG graph, and then turning their attention to the subclass of graphs that admit an EPG representation in which every path has at most a single bend, called B₁-EPG graphs. They proved that any tree is a B₁-EPG graph and gave a structural property that enables generating non B₁-EPG graphs. A characterization of the representation of cliques and chordless 4-cycles in B₁-EPG graphs was given, and also prove that single bend paths on a grid have Strong Helly number 3. This year, Andrei Asinowski and Andrew Suk and Bernard Ries have given further results on edge intersection graphs of systems of paths on a grid with a bounded number of bends.

We conclude with some open problems and future work.

Analytic Combinatorics of Balanced Search Trees

Balanced search trees, invented nearly 50 years ago, play a critical role in our modern computational infrastructure because they provide guaranteed performance for a range of the most heavily-used operations at the heart of many systems. This talk will address a natural mathematical question about such trees that has remained open since their invention: what is the expected cost of a search in a random balanced search tree? Many types of balanced search trees have been proposed and are in use, but none of them have been successfully analyzed. The talk begins with an discussion of the distinction between a random binary tree and a random binary search tree that is at the heart of the problem and continues with a description of the Guibas-Sedgewick framework that provides a unified view of the relationships among the many variants of balanced search trees that have been proposed, including Sedgewick's recently discovered implementation of 2-3 trees (left-leaning red-black trees), which can be developed from elementary binary search trees by adding just a few lines of code. Examined next is Odylyzko's 1982 analysis of path length in random 2-3 trees, which demonstrates the effectiveness of modern analytic combinatorics in the study of recursively-defined structures. But balanced search trees have a dynamic component that presents a significant challenge in determining even how to begin the analysis, let alone extend Odlyzko's results. The talk concludes with a study of experiments that disclose a fascinating dynamic process underlying a remarkably stable end result that validates the widespread use of these structures in practice and presents a number of conjectures that might aid in the analysis. Still, the central mathematical question remains open.

The Rank Aggregation Problem

The rank aggregation problem was introduced by Dwork, Kumar, Naor, and Sivakumar (WWW 2001) in the context of finding good rankings of web pages by drawing on multiple input rankings from various search engines. The work draws on earlier work in the social choice literature on combining voter preferences specified by ranked alternatives. Dwork et al. propose finding a ranking that minimizes the sum of its Kendall distance to the input rankings; this can be viewed as a weighted feedback arc set problem. I will give an overview of the rank aggregation problem and some of its applications, including an application to intranet search (WWW 2003). I will also cover recent work done on finding good approximation algorithms for the problem. In particular, Ailon, Charikar, and Newman (STOC 2005) introduce a randomized ``pivoting'' algorithm for rank aggregation and related problems; recent work has extended this to deterministic pivoting algorithms for constrained versions of the problem (van Zuylen, Hegde, Jain and Williamson, SODA 2007, van Zuylen and Williamson 2007) and has yielded a polynomial-time approximation scheme for the problem (Kenyon-Mathieu and Schudy, STOC 2007). Recent experimental work of Schalekamp and van Zuylen has given us a good sense of the tradeoffs of these various algorithms in practice. If time permits, I will discuss some extensions of this work to finding good clusterings and hierarchical clusterings.