ARCO > ARCO Events > 18th ARCO 2014 MTH
18th ARCO 2014 MTH
Program
9.3010.00  Coffee and sandwich  
10.0010.30  Peter Floderus Detecting and counting small pattern graphs 

10.3011.00  Patrick Hagge Cording Compressed Subsequence Matching and Packed Tree Coloring 

11.0011.15  Break  
11.1511.45  Jesper With Mikkelsen OnLine Edge Coloring on Paths and Trees 

11.4512.15  Noy Rotbart Adjacency labeling schemes 

12.1513.30  Lunch at the Orkanen cantine  
13.3014.00  Valentin Polischuck Optimal Geometric Flows via Dual Programs 

14.0014.30  Andreas Björklund Shortest Two Disjoint Paths in Polynomial Time 

14.3015.00  Coffee break  
15.0015.30  Faith Ellen A General Technique for Nonblocking Trees 

15.3016.00  Rasmus Pagh The Input/Output Complexity of Triangle Enumeration 

16.0016.30  Business meeting 
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 nonidentity 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 EvaMartta 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.
OnLine Edge Coloring on Paths and Trees
We revisit the problem of OnLine 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 FirstFit is optimal among deterministic algorithms and that no randomized algorithm can do significantly better than FirstFit. 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 unitcapacity planar networks. Joint work with Sylvester ErikssonBique 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 EilamTzoreff 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 Nonblocking 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 nonblocking implementations of a large class of trees, including a chromatic tree, which is a relaxed version of a redblack 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 wellknown 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 cacheoblivious 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 cacheaware 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.