THEMATIC PROGRAMS

Special Year on Graph Theory and Combinatorial Optimization Program

Seminar Series at the Fields Institute

Thanks are due to André Kündgen, who is organizing the series.

---

Thursday, May 25, 3:30 - 4:30 p.m.

Daniel Kobler , The Fields Institute
(Joint work with M.Gerber)

Partitioning a graph to satisfy all vertices: theoretical results and algorithmic approach

Abstract:
In a given graph, we want to partition the set of its vertices into two subsets, such that each vertex is satisfied in that it has at least as many neighbours in its own subset as in the other. By introducing weights for the vertices and the edges, we generalize the problem. These more general problems are strongly NP-complete. For the unweighted version, we present some sufficient conditions for the existence of a solution, and propose an exact and a heuristic solution method.

---

Total Ramsey colorings (a.k.a. split colorings) of graphs and hypergraphs

Abstract:
Ramsey colorings can be interpreted as total colorings (colorings of the edges and vertices) using a two round game played with an adversary.

Given integers n,m and r, we want to color the vertices and edges of the complete graph on n vertices with r colors in two rounds. We lose if, at the end of two rounds, there is a totally monochromatic m-clique, that is a clique in which all vertices and edges have the same color.

In the first round, we color all the edges. We then challenge the devil to color the vertices from the same r colors. The threshold below which we always win (assuming intelligent play) is exactly the Ramsey number R_r(m).

We investigate the threshold when the players roles are reversed - i.e. the devil does Round 1 and we do Round 2. This parameter was introduced by Erdos and Gyarfas as a generalization of split graphs. We present improved upper and lower bounds and generalize the problem to hypergraphs.

---

Andreas Jakoby , Department of Computer Science, University of Toronto
(Joint work with M.Liskiewicz and R.Reischuk)

Scheduling Dynamic Graphs

Abstract:

In parallel and distributed computing scheduling low level tasks on the available hardware is a fundamental problem. Traditionally, one has assumed that the set of tasks to be executed is known beforehand. Then the scheduling constraints are given by a precedence graph. Nodes represent the elementary tasks and edges the dependencies among tasks. This static approach is not appropriate in situations where the set of tasks is not known exactly in advance, for example, when different options how to continue a program may be granted.

In this talk a new model for parallel and distributed programs, the dynamic process graph, will be introduced, which represents all possible executions of a program in a compact way. The size of this representation is small -- in many cases only logarithmically with respect to the size of any execution. An important feature of our model is that the encoded executions are directed acyclic graphs having a "regular" structure that is typical of programs.

Dynamic process graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. With respect to such a compact representation we investigate the complexity of different aspects of the scheduling problem: the question whether a legal schedule exists at all and how to find an optimal schedule. Our analysis takes into account communication delays between processors exchanging data.

Precise characterizations of the computational complexity of various variants of this compact scheduling problem will be given. The results range from easy, that is NL-complete, to very hard, namely NEXPTIME-complete.

---

May 1

Graphs and Their Polynomials I: Complexes and Generating Polynomials

Abstract:

A number of polynomials have arisen in the study of graphs, most notably chromatic polynomials and reliability polynomials. Each has associated results and open problems. Yet underlying many graph polynomials is a common setting. We describe here such groundwork based on underlying abstract simplicial complexes and their face polynomials. The approach taken gives way to a broader mode of investigation of many graph parameters, and we shall provide another example in the guise of independence polynomials.

May 2

Graphs and Their Polynomials II: Roots of Graph Polynomials

Abstract:
Associating a polynomial to a graph begs the question as to the nature and location of the related roots of the polynomial in the complex plane. In this talk we shall explain why the nature of the roots are of interest, and shall provide some examples of how classical theorems on zeros of polynomials (including those of Gauss & Lucas, Sturm and Enestrom and Kakeya) can be applied to furnish new results on the nature and location of roots of chromatic, reliability and independence polynomials.

May 3,

Graphs and Their Polynomials III: The Connection to Commutative Algebra

Abstract:
The fact that many graph polynomials are face polynomials for various classes of simplicial complexes can often be used to formulate a deep connection between the combinatorics and commutative algebra by way of Hilbert Series of graded k-algebras. The upshot of this relation is that one can derive properties of expansions of graph polynomials that are virtually impossible to derive without dipping into commutative algebra. As an application, we shall show how this connection can drastically improve previously known bounds for the modulus of chromatic roots.

Note: Work discussed includes joint work with Carl Hickman, Richard Nowakowski, Karl Dilcher, Alan Sokal and David Wagner.

---

Derek Corneil , Department of Computer Science, University of Toronto

Abstract:
In preparation for the workshop on Structured Families of Graphs to be held at the Fields Institute May 8 - 13, this talk will provide an overview of the various families of graphs that will be discussed at the workshop.

---

Mike Molloy , Department of Computer Science, University of Toronto

(joint work with Bruce Reed)

Abstract:

We consider graphs whose maximum degree is some constant $\Delta$. We are interested in the complexity of $k$-colourability of such graphs. These graphs are trivially $k$-colourable if $k=\Delta+1$, and Brooks' Theorem makes it easy to test for $k$-colourability when $k=\Delta$. Maffray and Preissman showed that when $\Delta=4$ and $k=3$, the problem is NP-complete. This raises the question for which values of $k$ is $k$-colourability tractible.

A few years ago, Embden-Weinert, Hougardy and Kreuter proved that this problem is NP-complete when $k\leq K(\Delta)\approx \Delta+1-\sqrt{\Delta}$. We then proved that the problem can be solved in polynomial time if $k\geq \Delta+1-\epsilon\sqrt{\Delta}$ for a small positive constant $\epsilon$. In this lecture we present our more recent proof that the problem can be solved in polynomial time for every $k>K(\Delta)$, as long as $\Delta$ is sufficiently large.

A consequence of our work is a characterization of graphs with chromatic number close to $\Delta$, which is very similiar to Brooks' Theorem.

---

Algorithms for AT-free Graphs

Ekkehard Koehler , Department of Mathematics, Technische Universitaet Berlin

Abstract:
I n recent years a class of graphs gained a lot of attention in the field of Algorithmic Graph Theory: The Asteroidal Triple-free graphs. Although their creation dates back into the early sixties when they were used for characterizing interval graphs, AT-free graphs were not properly studied until the beginning of the nineties.

What is an Asteroidal Triple and why is it of any interest to us? Those and similiar questions will be tackled in the first part of the talk. We will survey some structural and algorithmic results for this graph class and consider different characterizations.

In the second part of the talk we will look at the recognition of AT-free graphs. We will examine several algorithms for this problem. One of them uses an interesting auxiliary graph, the knotting graph, which is helpful not only for AT-free graphs and enables us to recognize AT-free graphs in an elegant way.

---

Tom Fowler , Department of Mathematics, Universite du Quebec a Montreal

Abstract:
The Barnette Conjecture states that every 3-connected cubic planar bipartite graph has a hamilton cycle. The dual of this conjecture states that every triangulation of the plane having all vertices of even degree and having no parallel edges contains a circuit passing through all of its faces.

Define a configuration (which should roughly be thought of as a plane subgraph in a triangulation) to be reducible if it cannot appear in a minimum counterexample to the Barnett conjecture.

We present partial progress toward the Barnette Conjecture by exhibiting some reducible configurations

---

Oliver Kullman , Department of Computer Science, University of Toronto

Abstract:
Traditionally, the propositional satisfiability problem (SAT) belongs to the areas of logic and complexity theory, while combinatorial optimization focuses on graph theory and linear programming. In this talk we present some ideas for a fruitful connection between SAT and combinatorial optimization.

The broader perspective is to understand the complexity problems in NP (better algorithms, better upper bounds, better lower bounds). In order to make even small progress, it seems necessary to seriously examine NP-completeness and to attack problems in NP by using many reformulations and relaxations in terms of graph theory, linear programming and propositional logic.

In this 2-part lecture (aimed at a general audience from computer science and combinatorial optimization) we present (new) notions and results related to the concept of "autarky". A partial assignment of truth values to variables is called an "autarky" for a conjunctive normal form (a set of clauses), if every clause "touched" by the partial assignment is in fact satisfied by it.

We show interesting connections of this notion to the field of resolution refutations ("lean" clause sets not having non-trivial autarkies), linear programming ("linear autarkies"), matching theory ("matching autarkies") and matroid theory ("matching-lean" clause sets as cyclic transversal matroids). Speakers slides

---

Complexity of recognition of intersection graphs

Jan Kratochvil
Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

Abstract:
We will describe several classes of intersection graphs and discuss the complexity of their recognition. We will give a general technique for showing that recognition of an intersection class is NP-hard and address upper bounds.

This talk is a part of the mini-symposium on "Geometric Representations of Graphs" (April 11-14, 2000 at The Fields Institute). There will be two other lectures by Prof. Kratochvil, and three lectures by Prof. Sue Whiteside.

For more information visit the Symposium web page: Geometric Representations of Graphs

---

April 4,

The Power of Lexicographic Breadth First Search (LBFS)

Derek Corneil , Department of Computer Science, University of Toronto

Abstract:
The concept ot systematically searching a graph was first developed over a century ago. In the late 60s or 70s, considerable attention was given to the algorithmic importance of the two most obvious search strategies, namely Depth First Search and Breadth First Search. In 1976 Rose, Tarjan and Leuker developed a variation of Breadth First Search called Lexicographic Breadth First Search (LBFS). They showed that LBFS yields a very simple linear time algorithm for recognizing chordal graphs (graphs without induced cycles of size greater than 3). Although little work was done on LBFS for the following 15 years, recently it has received a great deal of attention.

In particular it has been shown that LBFS can be used both alone and in multiple sweeps to recognize various restricted families of graphs as well as to determine specific properties on such graphs.

In this talk we survey these results and indicate open problems in the area.

---

Discharging Techniques in Practice

Petr Hlineny , The Fields Institute

Abstract:
The discharging method is a powerful tool for dealing with graphs embedded on some surface (often just planar graphs). Probably the best known application of this technique is the "unavoidability" part in the proof of the Four Colour Theorem (Appel, Haken / Robertson, Sanders, Seymour, Thomas).

We will give an overview of this technique in the three talks of this miniseries:

In the first talk we will formulate the basic principles of the discharging method and give some simple examples. The second talk will be a "discharging method tutorial", focusing on how to apply this technique in practice. In the third talk we present a more involved application of discharging: we give a proof that there is no finite planar cover of the graph $K_{4,4}-e$.

---

Natasa Przulj , Department of Computer Science, University of Toronto

Abstract:
A \emph{dominating pair (DP)} in a connected graph is a pair of vertices such that every path between them is dominating. A graph $G$ is \emph{hereditary dominating pair (HDP)} if every connected induced subgraph of $G$ has a DP. The class of HDP graphs includes all asteroidal triple-free (AT-free) graphs --- already extensively studied --- and some graphs containing asteroidal triples (ATs). A \emph{minimal} HDP graph $H$ contains an AT $\{x,y,z\}$, and satisfies the following: if $\mathcal{P}^{c}_{a,b}$ is the set of all induced paths between vertices $a$ and $b$ that avoid the neighborhood of a vertex $c$, then every vertex of $H$ belongs to a path in $\mathcal{P}^{z}_{x,y} \cup \mathcal{P}^{y}_{x,z} \cup \mathcal{P}^{x}_{y,z}$. We describe some general structural properties of HDP and minimal HDP graphs. Also, the position of DP vertices in minimal HDP graphs is determined, as well as some structural properties dictated by the position of DP vertices.

---

Colin McDiarmid ,Department of Statistics, University of Oxford
(joint work with Stefanie Gerk)

Abstract:
Given a graph $G$ and a non-negative integer weight $x_v$ for each node $v$, a {\em weighted colouring} of the pair $(G,x)$ is an assignment to each node $v$ of a set of $x_v$ colours such that adjacent vertices receive disjoint sets of colours. We are interested in such colourings when the maximum weight $x_v$ is large, and in particular in the ratio of the ratio of the number of colours needed to the clique-based lower bound. An application where this problem arises is in the design of cellular communication systems, where we need to assign sets of radio frequency channels (colours) to transmitters (nodes), using few channels but avoiding excessive interference. We shall introduce a relevant graph invariant, the `imperfection ratio' $imp(G)$, and present some investigations concerning it. This invariant satisfies for example $\: imp(G) \geq 1$, $imp(G)=1$ if and only if $G$ is perfect, $imp(G)=imp(\bar{G})$, and if $G$ is an imperfect line graph then $imp(G) = \frac{g}{g-1}$ where $g$ is the minimum length of an odd hole. It is also related for example to the graph entropy of $G$ and $\bar{G}$.

---

March 14, 3:30 - 4:30

On frequent sets of Boolean matrices

Zoltán Füredi , University of Illinois, Urbana-Champaign and Renyi Institute, Budapest
(joint work with R.H. Sloan, Ken Takata and Gy. Turan)

Abstract:

Given a Boolean matrix and a threshold t, a subset of columns is {\it frequent} if there are at least t rows having an entry of1 in each corresponding position. This concept is used in the algorithmic, combinatorial approach to knowledge discovery and data mining. Examples are given of families that can be represented by a small matrix with threshold t, but that require a significantly larger matrix if the threshold is less than t. We also discuss connections to circuit complexity. The results presented here are purely combinatorial and we apply extremal hypergraph theory. We slightly improve Jukna's (1995) exponential lower bound to t 2^{n/t}.

This lecture is a part of the mini-symposium on "Extremal Graph Theory" (Monday March 13 - Thursday March 16). There will be several other lectures by Professor Furedi and Professor Simonovits in the mini-symposium.

---

Mohammad Reza Salavatipour , Department of Computer Science, University of Toronto

Abstract:
The sum coloring problem asks to find a vertex coloring of a given graph $G$, using natural numbers, such that the total sum of the colors is minimized amongst all proper vertex colorings of $G$. A coloring which achieves this total sum is called an optimum coloring and the minimum number of colors needed in any optimum coloring of a graph is called the strength of the graph, denoted by $s(G)$.

We prove the NP-hardness of finding the vertex strength for graphs with $\Delta=6$ and also give some logarithmic upper bounds for the vertex strength of graphs with small chromatic number. A linear time algorithm is presented for the sum coloring of chain bipartite graphs.

The edge sum coloring problem and the edge strength of a graph are defined similarly. We prove that the edge sum coloring and the edge strength problems are both NP-complete for cubic graphs. Also we give a polynomial time algorithm to solve the edge sum coloring problem on trees.

---

Laszlo Liptak , The Fields Institute

Abstract:
Lovász and Schrijver introduced several lifting-projecting methods to generate new valid inequalities for the convex hull of $0$-$1$ vectors of a polyhedron. Each of these operators have the property that in $n$ steps ($n$ is the dimension of the space) we obtain the convex hull itself. Hence applying these operators to the fractional stable set polytope of a graph $G$ (which is the linear programming relaxation of the stable set polytope, defined by the trivial $x_v\geq 0$ and the edge inequalities: $x_v+x_w\leq 1$ for all edges $vw$), the stable set polytope is obtained in at most $V(G)$ steps. In one step exactly the odd cycle inequalities can be derived, but little is known about inequalities obtained in two or more steps.

We summarize the properties of these operators, and examine the special case when the graph is $\alpha$-critical with stability number $\alpha(G)$, and the facet $\sum_{v\in V(G)} x_v\leq \alpha(G)$ can be derived in two steps.

---

Prof. Curt Lindner

Abstract:
This talk gives a survey of results on embedding partial Steiner triple systems with respect to the size of the containing system. The "beyond" is a brief description of results for embedding partial (2m+1)-cycle systems, 2m+1 >= 5, with respect to the size of the containing system.

This lecture is a part of the mini-symposium on "Triple Systems and their Generalizations". There will be a second lecture by Prof. Lindner in the mini-symposium on March 1 from 10:00-10:50.

---

March 1,

(joint work with Jack Edmonds)

Kathie Cameron, Wilfrid Laurier University

Abstract:
Given a spanning tree T of a graph G, can you find another spanning tree T' with the same degrees at each node as T? Corollaries of theorems of Ken Berman say that if G-E(T) is connected or has all node-degrees odd, then such a T' exists. These are "existentially polytime theorems", a generalization of "NP-coNP theorems" (i.e. "good characterizations"). We have nice pivot algorithms to find what they say exists. We do not know if our algorithms are polytime.

---

Dimitris Achlioptas , Microsoft Research

Abstract:(can also be found here.)

Let $X$ be a set of $n$ Boolean variables and denote by $C(X)$ the set of all 3-clauses over $X$, i.e.\ the set of all $8 {n \choose 3}$ possible disjunctions of three distinct, non-complementary literals of variables in $X$. Let $F(n,m)$ be a random 3-SAT formula formed by selecting, with replacement, $m$ clauses uniformly at random from $C(X)$ and taking their conjunction. Finally, let us say that a sequence of events ${\cal E}_n$ occurs with high probability (w.h.p.) if $\lim_{n \rightarrow \infty} \Pr[{\cal E}_n]=1$. The {\em satisfiability threshold conjecture\/} asserts that there exists a constant $r_3$ such that $F(n,rn)$ is \as satisfiable for $r <r_3$ and \as unsatisfiable for $r > r_3$. Experiments suggest $r_3 \approx 4.2$.

We prove $r_3 > 3.145$ improving over the previous best lower bound $r_3 > 3.003$ due to Frieze and Suen. For this, we introduce a new satisfiability heuristic and analyze its performance. The framework we develop for the analysis of our heuristic also allows us to recover most of the previous lower bounds in a uniform manner and with very little effort.

---

(joint work with various people)

Daniel Kobler , The Fields Institute

Abstract:
The directed de Bruijn graph $B(a,k)$ is a directed graph on words of length $k$ over an alphabet of $a$ letters, with specific arcs. Classes of directed de Bruijn graphs appear often as models in computer science, because of the useful properties these graphs have. Similarly, the induced subgraphs of these graphs have applications related to the sequencing of DNA chains. One of the problems considered in molecular biology is that of recognition of DNA primary structure. It is known that some methods for solving this problem may be reduced (in their computational part) to graph theoretic problems involving labeled graphs. In this talk, we will consider various classes of induced subgraphs of de Bruijn graphs. We will present properties of those classes, and we will also consider the related recognition problems.

---

(joint work with Aviad Mintz)

Martin Charles Golumbic , Bar-Ilan University, Ramat-Gan, Israel

Abstract:
Algorithmic logic synthesis is usually carried out in two stages, the independent stage where logic minimization is performed on the Boolean equations with no regard to physical properties and the dependent stage where mapping to a physical cell library is done. The independent stage includes logic operations like Decomposition, Extraction, Factoring, Substitution and Elimination. These operations are done with some kind of division (boolean, algebraic), with the goal being to obtain a logically equivalent factored form which minimizes the number of literals.

In this paper, we present an algorithm for factoring that uses graph partitioning rather than division. Central to our approach is to combine this with the use of special classes of boolean functions, such as read-once functions, to devise new combinatorial algorithms for logic minimization. Our method has been implemented in the SIS environment, and an empirical evaluation indicates that we usually get significantly better results than algebraic factoring and are quite competitive with boolean factoring but with lower computation costs.

---

On centroid branches of trees from certain families
(joint work with J.W. Moon)

Amram Meir , York University

Abstract:
For any node v of a tree T, the branches of T joined to v are the maximal subtrees of T not containing v. Let k(v) denote the size of the largest branch of T joined to v. If T has n nodes, then there exist either a unique node v such that k(v)<n/2 or two adjacent nodes v_1 and v_2 such that k(v_1)=k(v_2)=n/2 and n is even. This node(s) is the centroid of T.

We obtain various results concerning the sizes etc of the centroid branches in large random trees from certain families.

---

Colouring of Mixed Hypergraphs

Vitaly Voloshin , The Moldovan Academy of Sciences

Abstract:
The colouring theory of combinatorial structures has existed for about 150 years and in its usual setting is concerned with the minimum number of colours. We investigate structures called mixed hypergraphs where problems on both, the minimum and the maximum number of colours occur.

A mixed hypergraph is a triple H=(X,C,D) where X is the vertex set, C is the family of C-edges and D is the family of D-edges. A proper colouring of H is a mapping from X onto a set of colours such that:

1. every C-edge has at least two vertices with a Common colour;

2. every D-edge has at least two vertices with Different colours.

It may very well be that a mixed hypergraph has no colourings; then it is called uncolourable. In a colourable mixed hypergraph, the minimum (maximum) number of colours for which there exists a colouring using all the colours is called the lower (upper) chromatic number.

A feasible partition is a partition of X such that the colouring constraints 1) and 2) hold for the partition classes. The numbers of all feasible partitions form a vector called the chromatic spectrum.

In mixed hypergraphs, many old problems admit natural generalizations; many new problems arise; many properties have no analogue.

Basic paper : V.Voloshin. On the upper chromatic number of a hypergraph. Australasian J. of Comb. 11, 1995, p. 25-45.

In the 3 lectures we will discuss the following questions:

• Introduction: main definitions, ideas and examples.

• A splitting-contraction algorithm and chromatic polynomials.

• Algorithmic aspects related to the upper chromatic number.

• Perfection of mixed hypergraphs with respect to the upper chromatic number.

• The colourability problem and uncolourable mixed hypergraphs.

• Gaps in the chromatic spectrum.

• Applications of mixed hypergraph colourings.

---

John Mighton , University of Toronto

Abstract
We will show that Knot Theory may (up to a local move on knots called "mutation") be reduced to the study of labelled bipartite graphs.

The graphs appear to offer a new approach to a number of open problems in Knot Theory.

We will also discuss how the graphs may be used (via the Jones polynomial) to give upper bounds in Complexity Theory.