CAG Schedule of Talks: Summer

Schedule of Talks: Summer 2008

If you would like to give a talk in our seminar series, please contact Wendy Myrvold ( To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at

Schedule for Talks:

Date Place Time Speaker Abbreviated Title
May 2 _ _ No CAG WCCCE 2008 Conference (May 2, ECS 108 and ECS 125)
May 9 _ _ No CAG IWPEC 2008 (May 14-16, ECS 660)
May 16 _ _ No CAG STOC 2008 (May 17-20, Victoria)
May 23 2:30 ECS 660 Wendy Myrvold Embedding Graphs on Surfaces-Algorithmic Aspects and Obstructions
May 30 _ _ No CAG Prairie Discrete Math Meeting
June 20 _ _ No CAG SIAM Discrete Math conference
July 18 2:30 ECS 660 Ganesh Ramesh Disclosure Risk Analysis and the Dilemma of Disclosing Anonymized Data
Aug. 7 2:30 ECS 660 Ryuhei Vehara Enumeration of Perfect Sequences of a Chordal Graph
Aug. 8 2:30 DSB C 113 Gary MacGillivray Injective Homomorphisms of Directed Graphs

Previous Talks

We did not have CAG seminars in early May because these three conferences were in Victoria:

  1. WCCCE 2008: Thirteenth Annual Western Canadian Conference on Computing Education, Victoria, B.C., May 2, 2008.
  2. International Workshop on Exact and Parameterized Computation (IWPEC 2008) Victoria, B.C., May 14-16, 2008.
  3. 40th ACM Symposium on Theory of Computing (STOC 2008), Victoria, B.C., May 17-20, 2008.

Embedding Graphs on Surfaces-Algorithmic Aspects and Obstructions
Wendy Myrvold
Friday May 23, 2:30pm, ECS 660

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 K5 and K3,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.

Disclosure Risk Analysis and the Dilemma of Disclosing Anonymized Data
Ganesh Ramesh, Microsoft
Friday July 18, 2:30pm, ECS 660

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).

Enumeration of Perfect Sequences of a Chordal Graph
Ryuhei Uehara
School of Information Science, JAIST
Thursday August 7, 2:30pm, ECS 660

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.

Injective Homomorphisms of Directed Graphs
Gary MacGillivray
Friday August 8, 2:30pm, DSB C 113

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.

CAG Schedule of Talks: Summer 2008 / maintained by Wendy Myrvold / / revised Sept. 5, 2008