COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring/Summer 2013

We consider the problem of deciding whether a given network with integer capacities has two feasible flows x and y with prescribed balance vectors such that the arcs that carry flow in x are arc-disjoint from the arcs that carry flow in y. This generalizes a number of well-studied problems such as the existence of arc-disjoint out-branchings B⁺_s, B⁺_t where the roots s, t may be the same vertex, existence of arc-disjoint spanning subdigraphs D₁, D₂ with prescribed degree sequences in a digraph (e.g. arc-disjoint cycle factors), the weak-2-linkage problem, the number partitioning problem etc. Hence, the problem is NP-complete in general. We show that the problem remains hard even for very restricted cases such as two arc-disjoint (s, t)-flows each of value 2 in a network with capacities 1 and 2 on the arcs.

On the positive side, we prove that the above problem is polynomially solvable if the network is acyclic and the arc capacities as well as the desired flow values are bounded. Our algorithm for this case generalizes the algorithm (by Perl and Shiloach for k=2 and by and Fortune, Hopcroft and Wyllie for k >= 3) for the k-linkage problem in acyclic digraphs. Besides, the problem is polynomial in general digraphs if all capacities are one and the two flows have the same balance for all vertices in N, but remains NP-complete if the network contains at least one arc with capacity 2 (and the others have capacity 1). Finally, we have also shown that the following properties are NP-complete to decide on digraphs: the existence of a spanning connected eulerian subdigraph, the existence of a cycle factor in which all cycles have even length and finally, the existence of a cycle factor in which all cycles have odd length.

This is joint work with Stephane Bessy, LIRMM, Universite Montpellier 2, France.

The prism over a graph G is the Cartesian product of G with K₂. My interest in prisms began in 1973 when I tried to tackle Dave Barnette's conjecture that all simple 4-polytopes are Hamiltonian (still open). Subsequently, we merged the study of Hamiltonian cycles in prisms with other refinements of Hamiltonian cycles. We observed that if G has a Hamiltonian prism then G has a spanning closed 2-walk but the opposite is not true, that is having a Hamiltonian prism is "closer" to being Hamiltonian than having a spanning, closed 2-walk. This observation created many opportunities to study various classical problems on Hamiltonicity of graphs. In this talk I will discuss some results on prism Hamiltonicity, related complexity problems and other "classical" open problems.

Previous Talks

We consider various characterizations of discrete-time pursuit games, a collection of combinatorial games that includes Cops and Robbers and all of its variants. There are two players, Left and Right, who may move via prescribed rules. If Left can ensure that Right enters into a fixed set of final positions, then Left wins; otherwise, Right wins. In a wide variety of cases a relational characterization of such games is provided for when Left wins. In the case that the set of positions is finite, a precise formula is given for the length of the game, along with an algorithm for computing if Left has a winning strategy whose complexity is a function of the parameters of the game.

Everyone is welcome to join in for refreshments at the Grad Center after this talk.

In Bobbin Lace, a pattern is divided into regions by shape, each region filled with a texture. Since Bobbin Lace is generally made with a single colour of thread (black, white or ecru), the textures take on the role of colour to provide interest and shading. Using a combinatorial approach, I will look at one aspect of Bobbin Lace and examine how many unique textures are possible for a specified number of grid points. I will compare the results to textures currently known and used in Bobbin Lace. In the process, I hope to rediscover some of the more complicated textures that have been lost over time as well as identify some new textures which may be of use to modern Bobbin Lace artists. Bobbin Lace provides a very high level of control over the position of threads in a material. It is hoped that by increasing the palette of possible textures, the results may also prove useful to electronic textile manufacturing or fabric designed for a specific purpose such as medical prostheses.

We are interested in how systems (such as peer-to-peer systems or research groups) can form in a distributed manner - with agents interacting among with the aim of benefiting themselves yet forming high 'quality' groups. Using game theory, we have analysed particular games (especially their Price of Anarchy) in which a granting agency (here, the EU commission) gives grants to groups of researchers connected by a collaboration graph, based on their average quality assessed in a certain manner. At one level, this research directly suggests ways to address and improve science budget allocations. At another more conceptual level, it addresses game theoretic questions of collaboration formation in face of monetary (or other) incentives.

This paper (Composition Games for Distributed Systems: the EU Grant games) was presented at AAAI 2013, Bellevue, USA. Joint work with Shay Kutten and Ron Lavi.
Amitabh Trehan is currently a postdoctoral fellow at Hebrew University, after serving as a postdoctoral fellow at UVic and the Technion. He will soon be an assistant prof at Queen's University in Belfast. He works in distributed computing and is known for his work on "self-healing" network algorithms."