COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2008

This talk will start with an introduction to a combinatorial perspective of topological graph theory- the study of embeddings of graphs on surfaces without crossing edges. No previous background in topological graph theory is assumed. A tour through the published embedding algorithms will include mention of some which are correct, some which are incorrect, and both polynomial time and exponential approaches.

A topological obstruction for a surface S is a graph G with minimum degree three that is not embeddable on S but for all edges e, G-e embeds on S. A minor order obstruction has the additional property that for all edges e, G contract e embeds on S. For the plane, the obstructions are K₅ and K_3,3. The projective plane has 35 minor order obstructions and 103 topological ones. More than 200,000 obstructions have been found so far for the torus (a torus is a surface shaped like a doughnut). One of the main goals of my current research is to determine the complete set of torus obstructions. This talk includes an update of the techniques used to find these obstructions and progress towards this goal.

My work on topological graph theory has been done in collaboration with many people including Angus Argyle, Stephen Barker, John Boyer, John Chambers, Ben Ellenberger, Patrick Fowler, Andrei Gagarin, Sameer Girn, Brenna Innes, Brad Jackson, Bill Kocay, Marsha Minchenko, Eugene Neufeld, Jianping Roth, Aidan Roy, Matthew Skala, Hongmei Wang, Jennifer Woodcock, and Andrew Wyeth.

Decision makers of companies often face the dilemma of whether to release data for knowledge discovery, versus the risk of disclosing proprietary or sensitive information. While there are various "sanitization" methods, in this talk we focus on anonymization, given its widespread use in practice. We give due diligence to the question of "just how safe the anonymized data is", in terms of protecting the true identities of the data objects. We consider both the scenarios when the hacker has no information, and more realistically, when the hacker may have partial information about items in the domain. We conduct our analyses in the context of frequent set mining. We propose to capture the prior knowledge of the hacker by means of a belief function, where an educated guess of the frequency of each item is assumed. For various classes of belief functions, which correspond to different degrees of prior knowledge, we derive formulas for computing the expected number of "cracks". While obtaining the exact values for the more general situations is computationally hard, we propose a heuristic called the O-estimate. It is easy to compute, and is shown to be accurate empirically with real benchmark datasets. Finally, based on the O-estimates, we propose a recipe for the decision makers to resolve their dilemma.

This talk is based on the SIGMOD 2005 paper "To Do or Not To Do: The Dilemma of Disclosing Anonymized Data" and is joint work with Dr. Raymond Ng and Dr. Laks Lakshmanan (while I was at UBC).

A graph is chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a chordal graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This talk addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithm. First, a chordal graph does not generally have a unique clique tree. Second a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward way to generate perfect sequences from each possible clique tree. We propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial time delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O(1) for each perfect sequence.

This is joint work with Yasuko Matsui and Takeaki Uno.

A homomorphism from a digraph D to a digraph H is called injective if it is injective on the in-neighbourhood of each vertex. Complexity results for injective homomorphisms of irreflexive digraphs D are considered in the case when the target digraph H is reflexive, and in the case where the target graph H is irreflexive. A dichotomy theorem is obtained in the case where H is reflexive, whereas a such a theorem in the case where H is irreflexive would imply one for all digraph homomorphism problems. The complexity of the related injective oriented chromatic number problems (the minimum n for which a digraph D admits an injective homomorphism to a digraph on n vertices- defined together with A. Raspaud) is also discussed.

This is joint work with Cobus Swarts.