Welcome to the University of Toronto combinatorics seminar web site. This seminar series, held jointly by the Department of Computer Science and the Department of Mathematics, discusses recent developments in applied discrete mathematics, including, but not limited to, problems in combinatorial theory, graph theory, and their algorithms. We invite researchers from around the University, around the province, and around the world to present their latest work.
The combinatorics seminar is traditionally held weekly on Friday afternoons, from 1pm to 2pm, in room 266 of the D.L. Pratt building (6 King's College Road, Toronto) on the University of Toronto downtown campus. You may find this campus map useful; the Pratt building is labelled PT near the bottom. Occasionally we depart from this tradition, but any differences will be distinguished.
If you would like to be added to the combinatorics announcement and discussion mailing list, or to schedule a talk by yourself or one of your visitors, please contact the coordinators. For the 2003-2004 year, the coordinator is Mike Molloy who can be contacted at molloy in cs.toronto.edu.
Jan Kratochvil
Charles University, Prague
Abstract: Graph homomorphism is an edge preserving vertex mapping between two graphs. This algebraically motivated notion is also a natural generalization of the graph coloring concept - a k-coloring of a graph G is a homomorphism from G into the complete graph on k vertices. From the complexity point of view, the H-homomorphism problem is well understood. This problem, parametrized by a (fixed) graph H, asks when an input graph G allows a homomorphism into H. It is also referred to as the H-coloring problem. As Hell and Nesetril proved, this problem is polynomially solvable when H is bipartite and NP-complete otherwise.
A similar question will be discussed for locally constrained homomorphisms, i.e., homomorphisms for which the neighborhood of every vertex needs to be mapped bijectively/injectively/surjectively into/onto the neighborhood of its image. Interesting relations to topological graph theory and to the generalized frequency assignment problem will be presented. The latter is also referred to as the distance-constrained graph labeling problem, since it asks for a labeling of the vertices of the input graph by nonnegative integers such that the labels assigned to vertices which are close to each other differ by at least a certain specified amount. Several complexity results on this problem, including the complexity of L(2,1)-labeling regular graphs and L(p,q)-labeling prelabeled trees will be surveyed.
Dimitrios M. Thilikos
Departament de Llenguatges i Systemes Informatics
Universitat Politecnica de Catalunya,
Barcelona, Spain
Abstract: In this talk we present the games of conquest and searching in graphs. The goal in these games is to systematically maneuver several searches in order to capture an omniscient fugitive who flees around the graph. Such games have several applications in network security where we need to clean a computer network that is ``contaminated'' by mobile viruses or eavesdroppers. We describe the computational complexity of these games, and their connections to graph-theoretic parameters. In particular, we consider the "recontamination question":
Is it possible to search/conquest a graph using fewer searchers if we allow retreat, i.e., if the fugitive can visit an already searched location?
We present a structural theorem providing conditions for a negative answer to this question and describe its consequences and applications. The basic idea of the proof is to determine the structures defining strategies of "efficient resistance" that can be applied no matter whether the search/conquest strategy includes retreat or not. Finally, we present an example of a search game in which the answer to the recontamination question is positive and we evaluate the benefits of retreat in trees and in general graphs for this type of search game.
Lap Chi Lau
Dept of Computer Science
University of Toronto
Abstract: Given an undirected multigraph G and a subset of vertices S, the Steiner Tree Packing problem is to find a largest collection of edge-disjoint trees that each connects S. This problem and its generalization have attracted considerable attention from researchers in different areas because of their wide applicability. This problem was shown to be APX-hard (no polytime approximation scheme unless P=NP). In fact, prior to this work, not even an approximation algorithm with asymptotic ratio better than O(n) was known.
In this talk, we present the first polynomial time constant factor approximation algorithm for the Steiner Tree Packing problem. The main theorem is an approximate min-max relation between the minimum size of an edge-cut that disconnects some vertices in S (i.e. S-cut) and the maximum number of edge-disjoint trees that each connects S (i.e. S-trees). Specifically, we prove that if the minimum S-cut in G has k edges, then G has at least k/26 edge-disjoint S-trees; this answers Kriesell's conjecture affirmatively up to a constant multiple. The techniques that we use are purely combinatorial, where matroid theory is the underlying ground work.
Apostolos Dimitromanolakis
Dept of Computer Science
University of Toronto
Abstract: Golomb rulers are sets of positive integers having a unique difference between any two numbers in the set. The goal is to find an optimal Golomb ruler which has the smallest possible largest element for a specified numer of marks (elements of the set). It is not only a very interesting combinatorial problem but also has many applications in engineering as well. The same problem with a different notation can also be found under the Sidon set or B_2 sequence name which is more common among the mathematicians. Finding an optimal Golomb ruler is a very difficult combinatorial problem and although it has not been proven to be NP-hard, no polynomial algorithms exists for finding an optimal ruler. Optimal rulers are known today for up to 24 marks and are all of sub-quadratic length. Indeed, a conjecture by Erdös and Atkinson (independently) states that sub-quadratic length rulers exist for any number of marks. Previous works were able to verify this for up to 150 marks. In this talk we will present how we were able to verify the conjecture for Golomb rulers having up to 65000 marks and at the same time produce a vast amount of near-optimal rulers useful in applications.
|
|