Algorithms, Structure, Randomness

# Berlin-Poznan Seminar / ASZ Workshop 2008

## Schedule:

### Friday, 20 June 2008

14:00 Opening and greetings
14:15 Jeong Han Kim Optimal Query Complexity Bounds for Finding Graphs
15:00 Florian Pfender A Turan type theorem for multipartite graphs
15:30 Oleg Pikhurko Game chromatic index of graphs with given restrictions on degrees
16:00 Break / PhD defence Stefan Kirchner Untere Schranken für Steinerbaumalgorithmen und die Konstruktion von Bicliquen in dichten Graphen

### Saturday, 21 June 2008

8:45 Coffee
9:00 Anand Srivastav Low-Discrepancy Colorings for Arithmetic Progressions
9:30 Bernd Kreuter Patterns and Structures in real markets
10:00 Miroslawa Janczak On a problem of Hilliker and Straus
10:30 Coffee
11:00 Manuel Bodirsky The Product Ramsey Theorem in Constraint Satisfaction Complexity
11:30 Julia Böttcher (Not) separating between sublinear and linear bandwidth and treewidth
12:00 Wojciech Wawrzyniak Distributed packing in planar graphs
12:30 Lunch
14:15 Coffee
14:30 Krzysztof Krzywdzinski Distributed constant time algorithm for finding PTAS-approximation of Minimum Spanning Tree in Unit Disc Graphs
15:00 Mariano Zelke Weighted Matching in Streaming Graphs
15:30 Taral Seierstad The differential equations method
16:00 Coffee
16:15 Vojtech Rödl Folkman and Ramsey Numbers
16:45 Anusch Taraz / Mihyun Kang Mathematical history of the Berlin-Poznan seminar
17:45 Closeing

All lectures will be held in

Erwin Schrödinger-Zentrum, HU Berlin
Rudower Chaussee 26,
12489 Berlin
in room 1.306

## Abstracts

### The Product Ramsey Theorem in Constraint Satisfaction Complexity

In this talk, I show how the product Ramsey theorem can be used jointly with tools from universal algebra to classify the complexity of a large class of computational problems in temporal reasoning. I will also discuss open problems both in constraint satisfaction and Ramsey theory.

### (Not) separating between sublinear and linear bandwidth and treewidth

Bandwidth and treewidth are well studied graph parameters. While lots of research is dedicated to determining these parameters rather precisely for certain graphs or to graph classes where they are constants, in this talk we will be mainly interested in distinguishing between graph classes where the bandwidth/treewidth is sublinear in the number of vertices and such where these parameters are linear.
The star shows that in general even trees (i.e. graphs of treewidth 1) can have linear bandwidth. Chung proved that trees with bounded maximum degree however have sublinear bandwidth. This raises the question wether such a result remains true for bounded-degree graphs of bigger treewidth. We answer this question in the affirmative. More generally, we prove that for any hereditary class of bounded-degree graphs the concepts of sublinear bandwidth, sublinear treewidth, the absence of big expanders as subgraphs, and the existence of small separators are equivalent.
This result implies that planar graphs with bounded maximum degree have sublinear bandwidth. As a consequence we can infer the following embedding result. For each gamma>0 every n-vertex graph (for n sufficiently large) with minimum degree (gamma+3/4)n contains a copy of every bounded-degree planar graph on n vertices.
Joint work with Klaas Pruessmann, Anusch Taraz, Andreas Würfl.

### On a problem of Hilliker and Straus

For a prime $p$ and a vector $\ha=(\alpha_1,\dots,\alpha_k)\in \Z_p^k$ let $f\left(\ha,p\right)$ be the largest $n$ such that in each set $A\subseteq\Z_{p}$ of $n$ elements one can find $x$ which has a unique representation in the form $x=\a_{1}a_1+\dots +\a_{k}a_k,~a_i\in A$. Hilliker and Straus~\cite{hs} bounded $f\left(\ha,p\right)$ from below by an expression which contained the $L_1$-norm of $\ha$ and asked if there exists a positive constant $c\left(k\right)$ so that $f\left(\ha,p\right)>c\left(k\right)\log p$. In this note we answer their question in the affirmative and show that, for large $k$, one can take $c(k)=O(1/k\log (2k))$. We also give a lower bound for the size of a set $A\subseteq \Z_{p}$ such that every element of $A+A$ has at least $K$ representations in the form $a+a'$, $a, a'\in A$.

### Optimal Query Complexity Bounds for Finding Graphs

We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask sum of weights for the weighted graphs. These types of queries were partially motivated in DNA shotgun sequencing and linkage discovery problem of artificial intelligence.
For a given unknown weighted graph $G$ with $n$ vertices, $m$ edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of $G$ using $O\left(\frac{m\log{n}}{\log{m}}\right)$ queries of both types provided that $m \geq n^{\epsilon}$ for any constant $\epsilon> 0$. For a graph, it is shown that the same bound holds for all range of $m$.
This settles a conjecture of Grebinski for finding an unweighte graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions. A similar coin weighing problem is also considered.

### PhD thesis

My PhD thesis consists of two parts. The first part is concerned with lower bounds for approximating Steiner trees. The Steiner tree problem is to find a shortest subgraph that spans a given set of vertices in a graph and is a classical NP-hard problem. Several approximation algorithms exist, but for most algorithms only lower and upper bounds for the approximation ratio are known. For some of these algorithms we present instances which improve the lower bounds. When the problem is restricted to the class of graphs with k terminals, we also present a method which can be used to determine the approximation ratio of the Relative Greedy Algorithm with arbitrary precision.
The second part is about balanced bicliques, i.e. complete bipartite subgraphs with equal partition sizes. It has been known for a long time that every dense bipartite graph contains a balanced biclique of size O(log(n)), but whether and how such a biclique can be constructed in polynomial time is still unknown. Our contribution to this problem is a polynomial time algorithm which constructs a balanced biclique of size O(sqrt(log(n))) in sufficiently large and dense bipartite graphs.

### Patterns and Structures in real markets

Patterns and Structures in real markets -- on data mining, multi agent set-ups, the failure of classical probability theory, trading strategies, and many unsolved problems

### Distributed constant time algorithm for finding PTAS-approximation of Minimum Spanning Tree in Unit Disc Graphs

The Unit Disc Graphs (UDG) is the most natural class of graphs to model wireless ad hoc networks (for example cell phon es networks, wireless sensor networks etc.). The set of vertices of UDG is a set of points on the plane and two vertice s of UDG, $v$ and $w$, are connected by an edge in UDG if and only if they are at the distance at most one in Euklidi an norm ($\left\|v,w\right\| \leq 1$). From application point of view it means that the vertices (cell phones, sensors etc.) are in their communication range. By the weight of an edge $(v,w)$ in UDG we mean the distance between $v$ and $w$ on the plane. Moreover as the weight of a graph (of a subgraph of UDG as well) we define a sum of weights of its edge s.
One of the most fundamental problems concerning Unit Disc Graphs is finding a Minimum (in terms of its weight) Spannin g Tree of the arbitrarily given Unit Disc Graph G ($MST(G)$). In my presentation I will introduce a new distributed alg orithm, which finds in $O(poly(D))$ synchronous rounds a subgraph $H$ of $G$, which is a good approximation of $MST(G)$ .
Namely I will prove, that given as an input parameter $D$ and a Unit Disc Graph $G$, the presented algorithm finds in $O(poly(D))$ synchronous rounds, a subgraph $H$ of $G$ with four following properties:
$H$ contains one of the $MST(G)$;
weight of $H$ is $(1+O(1/D))$ approximation of the weight of $MST(G)$;
$H$ is planar;
if a shortest path between $v$ and $w$ in $G$ have weight $K$, then the shortest path between $v$ and $w$ in $H$ have weight $O(D)K$.

### A Turan type theorem for multipartite graphs

Turan's Theorem states that every graph of a certain edge density contains a complete graph K^k and describes the unique extremal graphs. We give a similar Theorem for l-partite graphs. For large l, we find the minimal edge density d_k , such that every l-partite graph whose parts have pairwise edge density greater than d_k contains a K^k . It turns out that d-k = (k-2)/(k-1) for large enough l, refuting a conjecture by Bondy, Shen, Thomasse and Thomassen. We also describe the structure of the extremal graphs.

### Game chromatic index of graphs with given restrictions on degrees

Given a graph $G$ and an integer $k$, two players alternatively color the edges of $G$ using $k$ colors so that adjacent edges get different colors. The \emph{game chromatic index} $\chi'_g(G)$ is the minimum $k$ for which the first player has a strategy that ensures that all edges of $G$ get colored.
Lam, Shiu, and Xu and, independently, Bartnicki and Grytczuk asked whether there is a constant $C$ such that $\chi_g'(G)\le \Delta(G)+C$ for every graph $G$. We show that the answer is in the negative. Also, general upper bounds on $\chi'(G)$ in terms of $\Delta(G)$ and $v(G)$ will be discussed.
This is a joint work with Andrew Beveridge, Tom Bohman, and Alan Frieze.

### The differential equations method

Wormald's differential equation method is often used to show that parameters defined on random graph processes converge in probability to the solutions of certain differential equations. We show that this method, in many cases, can be extended to show that the parameters converge to a multivariate normal distribution.

### Low-Discrepancy Colorings for Arithmetic Progressions

One of the celebrated theorems in discrepancy theory says that the 2-color discrepancy of the hypergraph of arithmetic progressions in the first $n$ integers is $\Theta(n^{1/4})$ (lower bound by Roth (1964), upper bound Matou\v{s}ek, Spencer (1994)). In this talk we give an overview on the discrepancy problem for different kind of arithmetic progressions, among them sums and products, both in the natural numbers as well as in $\mathbb{Z}_{p}$. In particular, we will prove tight bounds for the $c$-color discrepancy function for centered arithmetic progressions in $\mathbb{Z}_{p}$. Here, due to the lack of translation-invariance of the hypergraph Fourier analysis alone does not work, and has to be combined with a new decomposition of such progressions.

### Distributed packing in planar graphs

I'll give an efficient distributed algorithm that finds an almost optimal packing of a graph H in a planar graph G. The algorithm is deterministic and its running time is poly-logarithmic in the order of G.

### Weighted Matching in Streaming Graphs

The Semi-Streaming Model forbids random access to the input and uses a working memory of restricted size. It was proposed by Muthukrishnan in 2003 and is appropriate when tackling massive graphs. For the problem of finding the maximum weighted matching, which is intractable in the Semi-Streaming Model, we will present the best known approximation algorithm.

## Contact:

Dr. Mihyun Kang
Postal address
Johann von Neumann-Haus
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin

Tel.   : (+49 30) 2093 3830
Fax    : (+49 30) 2093 3191
e-mail : kang@informatik.hu-berlin.de