COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2002

A Latin square is an n by n array on n symbols where each symbol appears exactly once in each row and column. Two Latin squares are isotopic if one can be transformed to the other by permuting rows, columns, and/or symbols. Being in the same main class means that in addition, the roles of rows, columns and/or symbols can be interchanged. A third form of equivalence is isomorphism which will be defined in the talk. By using the novel technique of generating only the Latin squares having non-trivial symmetry group, we are able to count the number of isotopy, main, and isomorphism classes up to n = 9 and there is hope the results can be extended to n = 10.

An outstanding open question is whether there exists an orthogonal triple of Latin squares of order 10. The squares of order 10 which have been generated so far have been tested to see if they belong to some orthogonal triple. From these computations, we know that any square in such a triple must have isotopy group order 2^k for some integer k >= 0, as all other squares have been tested. This is joint work with Brendan McKay.

We introduce the problem Profit Cover. For a given graph G=(V,E) and an integer p > 0, the goal is to determine PC, a subset of V such that the profit, |E'| - |PC|, is at least p, where E' is the set of edges covered by PC. We show that p-Profit Cover is a parameterization of Vertex Cover. We present a fixed-parameter-tractable (fpt) algorithm for p-Profit Cover that runs in O(p |V| + 1.150964^p). We combine our algorithm for p-Profit Cover with an fpt-algorithm for k-Vertex Cover. We show that this results in a more efficient implementation to solve Minimum Vertex Cover than each of the algorithms independently. We also demonstrate the generality of our approach on the example of Planar Dominating Set.

Previous Talks:

We introduce the train tree representation of an interval graph, which is based on the clique-separator graph representation of a chordal graph. The train tree is the basis of the first dynamic algorithm to recognize interval graphs, and it may lead to fast dynamic algorithms for numerous problems on interval graphs, which have applications in areas such as computational biology, archeology, psychology, and scheduling.

Number theory is one of the oldest parts of mathematics and the theory of formal languages is one of the oldest parts of theoretical computer science, so it is not surprising there are interesting and non-trivial connections between these two areas. In this talk, I will discuss some of these connections focussing on:

• Christol's theorem and transcendence in finite characteristic,
• state complexity, and
• the primitive words problem.

We survey results on hamiltonian paths and cycles in digraphs that are structurally related to tournaments. This includes well studied classes of digraphs such as extended semicomplete digraphs, quasi-transitive digraphs and locally semicomplete digraphs (all of which contain tournaments as a subclass) and the class of bipartite tournaments (these do not contain tournaments but are related through the common superclass of multipartite tournaments.

We will discuss the complexity of the hamiltonian path and cycle problems for these classes of digraphs. It turns out that for all the classes above the problems are polynomially solvable but the range of difficulty varies very much from the easiest (almost trivial) case of tournaments to the hardest (very complicated) case of multipartite tournaments.

We will also discuss parallellization of some of the algorithms above for the classes of extended semicomplete digraphs and bipartite tournaments. It turns out that quite a number of tricks are needed in order to obtain (R)NC algorithms for these problems which are closely related to the matching problem in bipartite graphs.

Come one come all and bring your open problems with you. Gary has offered to moderate a problem seesion on May 24 to be continued on May 31 if there is a need for more time. In order to facilitate scheduling, please e-mail your open problems to Gary in advance.

Let G be a finite graph and f be a vertex of G. The following one player dynamic game played on G is considered. At time 0 a fire breaks out at vertex f. At each time t > 0, some vertex is defended and then the fire spreads from every vertex on fire to every undefended neighbour of such a vertex. Once a vertex is on fire it remains on fire for the duration of the game, and similarly for defended vertices. The game ends when the fire can no longer spread. The object of the game is to minimize the number of vertices on fire when the it ends. Perhaps unsurprisingly, the corresponding decision problem is NP complete even when restricted to bipartite graphs. Strategies and complexity results will for various classes of graphs willbe discussed.

Given n point obstacles in the plane and some "sketches'' of disjoint paths that wind amongst the points, we give an efficient algorithm to turn the sketched paths into shortest paths that still wind amongst the points in the same way -- i.e. that are homotopic to the original paths. This problem of computing shortest homotopic paths has application to graph drawing, wire routing in circuit board design, and motion planning. The talk will include background on geometric shortest path problems.
This is joint work with Alon Efrat and Stephen Kobourov.

The objective of this talk is to present a brief account of my current and past activities in research, particularly in the field of metaheuristics and memetic algorithms, as well as in other fields of computational complexity. Our most recent project was recently awarded with a Brazilean federal grant to study problems related with micro array data analysis, a revolutionary new tool that is changing the way in which scientific inference of genetic networks must be conducted. At the group of Software Engineering for Complex Systems, we are currently working in a variety of topics in Bioinformatics involving large-scale optimization problems in gene expression data analysis, clustering, optimal phylogenetic tree algorithms, etc.

The "meta-objective" of the talk is that it may serve as a starting point for a Collaboration with professors and graduate students at University of Victoria, particularly in problems related to data-mining and pattern recognition and the computational complexity of feature selection problems. The talk will also offer a very personal view and account of facts, and a proposal for a quest of a systematic approach to bridge the gap between theory and practice, with Bio informatics as a leading uniting force.

The material for this talk is based on past and current work with M.G. Norman (Dept. of CS, University of Edinburgh), L. Buriol (AT&T Research Labs), Prof. Carlos Cotta (University of Málaga, Spain), R. Berretta (USF, Brazil), F. Xhafa and M.J. Blesa (UPC, Barcelona), F. Von Zuben and L. Gomes (UNICAMP, Brazil).

A graph (digraph) is homomorphically full if it contains every homomorphic image as a subgraph (subdigraph). The homomorphically full irreflexive graphs are known to be precisely the graphs that contain neither P₄ nor 2K₂ as an induced subgraph. We show that the homomorphically full reflexive graphs are precisely threshold graphs, i.e, the graphs that contain none of P₄, 2K₂ and C₄ as an induced subgraph. We also characterize the reflexive semicomplete digraphs that are homomorphically full.

This is joint work with Jing Huang.

Suppose we are searching a building for an omniscient and fast moving intruder. We can capture the intruder if we place a guard at both ends of a corridor containing the intruder, but if we leave any avenue open the intruder will for sure slip past the guards.

What is the minimum number of guards and using what strategy can ensure the capture of the intruder?

This problem is nicely modelled by the "node search number" of a graph. In this model, the edges represent corridors and the nodes represent the confluence of corridors.

It happens that this problem is not only entertaining but significant, because this parameter is identical to other important graph parameters, among them: vertex separation, pathwidth and interval thickness. Computing the value of the the parameter is in general an NP-hard problem, but it can be computed in polynomial time on some restricted graph families, such as trees and some perfect graphs.

Here we consider the family of "solid (no internal holes) convex (no indentations in the periphery) 2-dimensional grid graphs". It turns out that computing the search number on these graphs in polynomial time is possible by a method that is intuitively simple, but the proof of optimality is not obvious.

This research is joint work with Hongbing Fan.

Preamble: I will be giving one of the two invited talks at the 10th Annual Conference on Graph Drawing on August 26 (http://www.cs.uci.edu/~gd2002/). This is a practice for that talk. It is also my first experience at preparing and giving a powerpoint presentation. The talk is not very technical and has lots of pretty pictures.

Abstract:

Venn diagrams have long been used as an aid in understanding set containment relationships and certain logical arguments. They also have interesting combinatorial properties. In this talk we survey some of what is known about Venn diagrams, with particular emphasis on the aesthetic and extremal properties of the drawings. Connections with graph drawing, of which there are many, will be emphasized.