18th ARCO 2014 MTH

Program

Abstracts

Detecting and counting small pattern graphs

We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs.
We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for non-identity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs.
Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size $s$ and a subgraph of host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.
Joint work with Miroslaw Kowaluk, Andrzej Lingas and Eva-Martta Lundell, presented at ISAAC 2013.

Compressed Subsequence Matching and Packed Tree Coloring

We present a new algorithm for subsequence matching in grammar compressed strings. Given a grammar of size $n$ compressing a string of size $N$ and a pattern string of size $m$ over an alphabet of size $\sigma$, our algorithm uses $O(n+\frac{n\sigma}{w})$ space and $O(n+\frac{n\sigma}{w}+m\log N\log w\cdot occ)$ or $O(n+\frac{n\sigma}{w}\log w+m\log N\cdot occ)$ time. Here $w$ is the word size and $occ$ is the number of occurrences of the pattern. Our algorithm uses less space than previous algorithms and is also faster for $occ=o(\frac{n}{\log N})$ occurrences. The algorithm uses a new data structure that allows us to efficiently find the next occurrence of a given character after a given position in a compressed string. This data structure in turn is based on a new data structure for the tree color problem, where the node colors are packed in bit strings.

On-Line Edge Coloring on Paths and Trees

We revisit the problem of On-Line edge coloring a graph with a fixed number of colors. In this problem, the edges of some unknown graph are revealed one by one to the algorithm. Immediately upon receiving an edge, the algorithm must either color the edge with one of the k colors or reject the edge. The goal is to color as many edges as possible. We consider the problem when the input graph is restricted to being a path or a tree. For paths, we give a randomized algorithm with a competitive ratio of $\frac45$ and show that this is optimal (for k=2). For trees, we show that the natural greedy algorithm First-Fit is optimal among deterministic algorithms and that no randomized algorithm can do significantly better than First-Fit. Joint work with Lene Monrad Favrholdt.

Adjacency labeling schemes

I will present two new and simple results regarding adjacency labeling schemes. The first is an improved scheme for dense graphs, and the other is the extension to dynamic labeling schemes for various families.

Optimal Geometric Flows via Dual Programs

Considering potentials in the dual of a planar network has proved to be a powerful tool for computing planar maximum flows. In this paper we explore the use of potentials for giving algorithmic and combinatorial results on continuous flows in geometric domains - a (far going) generalization of discrete flows in unit-capacity planar networks. Joint work with Sylvester Eriksson-Bique and Mikko Sysikaski to be presented at SoCG'14

Shortest Two Disjoint Paths in Polynomial Time

Given an undirected graph and two pairs of vertices $(s_i,t_i)$ for $i\in\{1,2\}$ we show that there is a polynomial time Monte Carlo algorithm that finds vertex disjoint paths of smallest total length joining $s_i$ and $t_i$ for $i\in\{1,2\}$ respectively, or concludes that there most likely are no such paths at all. This answers an open problem, noticed by Eilam--Tzoreff in 1998 and by Kobayachi and Sommer in 2010.
Our algorithm is algebraic and uses permanents over the quotient ring $\mathbf{Z}_{4}[X]/(X^m)$ in combination with Mulmuley, Vazirani and Vazirani's isolation lemma to detect a solution. We develop a fast algorithm for permanents over said ring by modifying Valiant's 1979 algorithm for the permanent over $\mathbf{Z}_{2^l}$. Joint work with Thore Husfeldt.

A General Technique for Non-blocking Trees

A library of concurrent data structures can make the task of developing concurrent software much easier. Although sequential data structures can be transformed into concurrent data structures in straightforward ways using locks or transactional memory, the results are generally inefficient. I'll describe a general method for obtaining efficient non-blocking implementations of a large class of trees, including a chromatic tree, which is a relaxed version of a red-black tree, using only standard machine instructions. This is joint work with Trevor Brown and Eric Ruppert.

The Input/Output Complexity of Triangle Enumeration

In this talk, we consider the well-known problem of enumerating all triangles of an undirected graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let E be the number of edges, M<E the size of internal memory, and B the block size. The best previous results are sort(E^(3/2)) I/Os (Dementiev, PhD thesis, 2006) and O(E^2/(MB)) I/Os (Hu et al., SIGMOD 2013), where sort(n) denotes the number of I/Os for sorting n items. We improve the I/O complexity to O(E^(3/2)/(sqrt(M) B)) expected I/Os, which improves the previous bounds by a factor min(sqrt(E/M),sqrt(M)). Our algorithm is cache-oblivious and also I/O optimal: We show that any algorithm enumerating t distinct triangles must always use Ω(t/(sqrt(M) B)) I/Os, and there are graphs for which t=Ω(E^(3/2)). Finally, we give a deterministic cache-aware algorithm using O(E^(3/2)/(sqrt(M) B)) I/Os assuming M≥E^(Ω(1)). Our results are based on a new color coding technique, which may be of independent interest. Joint work with Francesco Silvestri, to appear at PODS 2014.