COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2008

It has been suggested that the parameterized complexity class AW[*] is the natural home of k-move games, but to date the number of games known to be complete for this class has remained small. We investigate the complexity of Short Generalized Chess (the problem of deciding whether a chess player can force checkmate in the next k moves) and show that this problem is complete for AW[*].

This is joint work with Ulrike Stege.

Previous Talks

A perfect path double cover of a graph G on n vertices is a family P of n paths of G such that each edge of G belongs to exactly two members of P and each vertex of G occurs exactly twice as an end of a path of P. The perfect path double cover conjecture states that that every simple graph has a perfect path double cover. Hajos' conjecture is that for any simple eulerian graph on n vertices, one can partition the edges into at most n/2 cycles.

In this talk, I will discuss how a recent result for matroids leads to some interesting known and unknown theorems/problems for graphs, in particular the perfect path double cover conjecture and Hajos' conjecture.

How do you know what-or even if- your students are truly learning? Educational assessment means more than just tests; assessment should be an integrated and ongoing process that informs both teaching and learning. This session will offer a vocabulary for building an understanding of the importance of assessment, and introduce an online assessment toolkit being developed at the University of Washington that will focus on CS-related disciplines. Finally, some simple Classroom Assessment Techniques that work well in CS courses will be presented.

Jamie Cromack is a member of the Education Research Programs group at Microsoft Research. Her focus is the assessment of learning in postsecondary courses in which computational science plays a key role. A specialist in higher education studies, Dr. Cromack taught at the college level for over 15 years and was a new media producer in the educational arena for close to 20 years. Dr. Cromack integrated her technology experience and educational background while working with the National Science Foundation grant, math*ed*ology, and the U.S. Department of Education grant, Preparing Tomorrow's Teachers to Use Technology (PT3).

This talk presents an attempt to connect qualitative matrix theory with linear programming and linear complementarity problems. A linear program max{cx | Ax=b, x >= 0} is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. Checking the sign-solvability of a given linear program turns out to be co-NP-complete. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c.

Similarly, we introduce sign-solvability for linear complementarity problems(LCPs). We show that a totally sign-nonsingular matrix characterizes a sign-solvable LCP whose coefficient matrix is nonzero diagonal. This characterization leads to an efficient algorithm to obtain the sign pattern of a solution for these LCPs.

The first part of this talk is a joint work with Satoru Iwata.

A symmetric matrix A is said to be sign-nonsingular if every symmetric matrix with the same sign pattern as A is nonsingular. Hall, Li and Wang (2001) showed that the inertia of a sign-nonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of this paper is to present an efficient algorithm for computing the inertia of such symmetric matrices. Our algorithm is based on the matching structure of symmetric bipartite graphs. The running time bound is O(sqrt(n) m log n) for a symmetric matrix of order n with m nonzero entries. In addition, it is shown to be co-NP-complete to decide whether the inertia of a given symmetric matrix is determined by its sign pattern.

This is joint work with Satoru Iwata.

Reference: N. Kakimura and S. Iwata, Computing the Inertia from Sign Patterns. Mathematical Programming, 110, pp. 229-244, 2007.

Gutman motivated by applications in chemistry introduced the energy of a graph to be the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of a matrix is defined to be the sum of its singular values. It turns out that only strongly regular graphs attain the maximum possible energy amongst all graphs with a given number of vertices and edges. A similar result holds for (0,1)-matrices achieving a maximum possible energy.

No special background is needed for this survey talk.

Genetic algorithms have been evolving since the early 70's, achieving immense success and fame in the process. Multi-objective Evolutionary Algorithms (MOEAs) take this natural paradigm to the next level - an essential jump because few real problems of interest have only a single objective. The last decade has seen a deluge of research in this field, producing such delights as the Non-dominated Sorting Genetic Algorithm II (NSGA-II). Most MOEAs employ the concept of Pareto-based fitness, inspired by the objective of finding an approximation of the Pareto-optimal solution set in objective function space. This talk shall present the basic concepts of MOEAs as formulated for discrete combinatorial optimization, including fitness assignment, genetic operations, diversity preservation, elitism, constraint handling and auto-adaptation of parameters in a multi-objective environment.

Circular colouring of a graph is a variation of the ordinary vertex colouring of graphs, which provides a better model for many periodic scheduling problems. Analogous to the list colouring of graphs, circular choosability of graphs was introduced independently by Mohar and myself. In this talk, I shall survey results in the study of circular colouring of graphs. In particular, I shall explain the application of the combinatorial nullstellensatz to the study of circular choosability of graphs.

A colouring game on planar graphs was invented by Steves in 1981 (published by Scientific America by M. Gardner) as a recreational game. The game remained unnoticed by the graph theoretic community until it was re-invented by Bodlaender in 1991 for general graphs and for the purpose of studying computational complexity. Since then it has attracted much attention. Many interesting problems are studied and interesting results are obtained. In this talk, I shall explain some strategies used in the games that achieve the best known upper bounds for many classes of graphs.

This is a Lansdowne Public Lecture sponsored by the Department of Mathematics and Statistics.