Abstracts

1. Mathias Bæk Tejs Knudsen, DIKU, Finding Even Cycles Via Capped k-Walks

Abstract: Finding cycles in graphs is a fundamental problem in algorithmic graph theory. In this paper, we consider the problem of finding and reporting a cycle of length 2k in a graph G with n nodes and m edges for constant k >= 2. A classic result by Bondy and Simonovits [J. Combinatorial Theory, 1974] implies that if m > 100 k n^{1+1/k}, then G contains a 2k-cycle, further implying that one needs to consider only graphs with m = O(n^{1+1/k}).

Previously the best known algorithms were an O(n^2) algorithm by Yuster and Zwick [J. Discrete Math 1997] and a O(m^{2-(1+1 / ceil(k/2))/(k+1)}) algorithm by Alon et. al. [Algorithmica 1997]. We present an algorithm that uses O(m^{2k/(k+1)}) time and finds a 2k-cycle if one exists. This bound is O(n^2) exactly when m = Theta(n^{1+1/k}). When finding 4-cycles our new bound coincides with Alon et. al., while for every k>2 our new bound yields a polynomial improvement in m.

We also observe new conditional lower bounds for this problem. In particular, when k=3 we show that no combinatorial algorithm can decide whether G contains a 2k-cycle in time m^{3/2-eps} for any eps > 0 unless boolean matrix multiplication can be solved combinatorially in time n^{3-eps'} for some eps' > 0, which is widely believed to be false. Coupled with our main result, this gives tight bounds for finding 6-cycles combinatorially. Our conditional lower bounds also provide a separation in the complexity of finding 4- and 6-cycles combinatorially giving evidence that in the time complexity, the exponent of m should increase with k.

Yuster and Zwick noted that it is "plausible to conjecture that O(n^2) is the best possible bound in terms of n". We show "conditional optimality": if this hypothesis holds then our O(m^{2k/(k+1)}) algorithm is tight as well.

Our new algorithm is conceptually simple, and is in fact a slight modification of an O(mn) time algorithm by Monien [Ann. Discrete Math., 1985]. The time analysis, however, is significantly more involved. Here we introduce the notion of capped k-walks, which are walks of length k that visit only nodes according to a fixed ordering. Our technical contribution is several properties of such walks which may be of independent interest.
Joint work with Søren Dahlgaard and Morten Stöckel

2. Anders Roy Christiansen, DTU, Parallel Lookups in String Indexes

In this talk I'll look at the pattern matching problem in the PRAM model. First I'll give a short introduction to the PRAM model followed by a short summary of known solutions for pattern matching in suffix trees in the PRAM model. I'll then show our new results that achieve optimal worst-case matching time O(log m), work O(m) and space O(n) for patterns of length m in a text of length n. The preprocessing part is non-deterministic. Our solution uses simple techniques based on hashing and Karp-Rabin fingerprints. The main challenge is to deal with colliding fingerprints. Finally, I'll shortly present the lower bound that shows the algorithm is time optimal.

3. Søren Dahlgaard, DIKU, Near-Optimal Light Spanners in Near-Linear Time

Abstract: Given an edge-weighted undirected graph G=(V,E,w) with n vertices and m edges and t>=1, a subgraph H of G is called a t-spanner of G if for all u,v in V(G), the shortest path distance between u and v in H is at most a factor of t longer than in G. The two main measures of the sparseness of a spanner are the size (number of edges) and the lightness, defined as w(H)/w(MST(G)) where w(H) resp. w(MST(G)) is the total weight of edges in H resp. in an MST of G. It is known that O(n^(1+1/k)) size and O(n^(1/k)) lightness is optimal assuming the Erdös Girth Conjecture.

In this talk I will present a recent result obtaining fast construction of light spanners. Specifically, we present an algorithm that constructs a O(k)-spanner of size O(n^(1+1/k)) and lightness O(n^(1/k)) in time O(m + kn^(1+1/k+eps)) for any constant eps>0. As an important corollary we obtain an asymptotically optimal O(log n)-spanner of size O(n) and lightness O(1) in almost linear time O(m+n^(1+eps)). Joint work with: Stephen Alstrup, Morten Stöckel, and Christian Wulff-Nilsen

4. Valentin Polishchuk, LIU, On Minimizing Crossings in Storyline Visualizations.

Abstract. In a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by x-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with n characters, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with O(n log n) crossings. Furthermore, we show that there exist storylines in this restricted case that require Ω(n log n) crossings. Lastly, we show that, in the general case, minimizing the number of crossings in a storyline visualization is fixed-parameter tractable, when parameterized on the number of characters k. Joint with with I. Kostitsyna, M. Nöllenburg, A. Schulz, D. Strash, presented at Graph Drawing 2015

5. Tilde My Christiansen, SDU, Degree Constrained 2-Partitions of Tournaments

Abstract. DTUA 2-partition (V_1,V_2) of a digraph D=(V,A) is a partition of V into disjoint sets V_1,V_2 such that V=V_1\cup V_2. We will consider problems of deciding whether a given digraph has a 2-partition (V_1,V_2) such that V_i induces a digraph with some specified property. In \cite{BJCH15} and \cite{BJH15} Bang-Jensen, Cohen and Havet determined the complexity of 120 such problems. In this paper we consider tournaments and semicomplete digraphs and the complexity of the problems with graph properties minimum in-degree, minimum out-degree and minimum semidegree. While we can prove the existence of a polynomial algorithm for the (\delta^+\geq k, \delta^+\geq k)-partition problem for every k \in \mathbb{Z}, we can only prove similar for the (\delta^+\geq k, \delta^-\geq k)-partition and the (\delta^0 \geq k, \delta^0 \geq k)-partition problem in the case where k=1.

6. Nikolai Nøjgaard, SDU,  DNA Origami and Enumerating Non-Equivalent Embeddings

Abstract: In [Nat. Chem. Biol., 9(6):362--363, 2013] polypeptide sequences were designed such that the three-dimensional embedding of these sequences fold into a predefined polyhedron, the success was verified with atomic force microscopy. The biochemical design question is basically answered by finding a ``strong trace'', which essentially is identical to an embedding of a graph in a higher surface. This allows to directly connect topological graph theory and the application of methods for efficient enumeration of all possible solutions. In this presentation we will introduce the problem and discuss methods for efficient enumeration of all possible one-face embeddings.