Monday, May 4, 2009
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
It is shown that, for any $\epsilon > 0$, every graph of
maximum degree $\Delta$ permits a {\em conflict-free
coloring} with at most $\log^{2+\epsilon}\Delta$ colors,
that is, a coloring with the property that the neighborhood
$N(v)$ of any vertex $v$, contains an element whose color
differs from the color of any other element of $N(v)$. We
give an efficient deterministic algorithm to find such a
coloring, based on an algorithmic version of the Lov\'asz
Local Lemma suggested by Beck, Molloy and Reed. We need to
correct a small error in the Molloy-Reed approach, restate
it in a deterministic form, and re-prove it
The problem can be extended to arbitrary hypergraphs $H$: a
coloring of the vertices of $H$ is called
{\em conflict-free} if each hyperedge $E$ of $H$ contains a
vertex whose color does not get repeated in $E$. Every
hypergraph with fewer than ${s \choose 2}$ edges permits a
conflict-free coloring with fewer than $s$ colors, and this
bound cannot be improved. Moreover, there is a linear time
deterministic algorithm for finding such a coloring.
The concept of conflict-free colorings was first raised in a
geometric setting in connection with frequency assignment
problems for cellular networks.
Joint work with G\'abor Tardos.
Colloquium - 16:00
Abstract:
In addition to approximation algorithms, parameterized complexity theory is a well-known approach when dealing with NP-hard (optimization) problems. The central definition of fixed parameter tractability expresses that the corresponding decision problem can be solved in time O(f(k)n^c), where k is the parameter, e.g., the size of the solution, c is a constant independent of k, and f is an arbitrary computable function. Only recently, one has begun to apply this theory to a geometric context.
In this talk, we will analyze several variants of geometric stabbing problems from a parameterized complexity point of view. In particular, we will show that the problem of stabbing unit-squares with lines does not allow an fpt algorithm when parameterized with the size of the solution (under standard complexity-theoretic assumptions). Still, we will consider some restrictions of the general problem for which such algorithms can be found. Finally, several open problems that arise from geometric settings are presented.
Abstract:
For a graph $G$ and $d\in \mathbb N,$ the $d$-girth $g_d(G)$ of $G$ is the minimum order of an induced subgraph of $G$ of minimum degree at least $d$ (or $\infty,$ if no such subgraph exists). The $2$-girth of a graph is the same as its usual girth (the length of a shortest cycle), so the $d$-girth is a generalization of the girth. In particular, we examine the $(d+k)$-girth of $C_n^d,$ the $d$-th power of a cycle of length $n.$ This is motivated by a conjecture of K{\'e}zdy and Markert, that $C_n^d$ are the $2d$-regular graphs with largest $(d+1)$-girth. In 1989 Bermond and Peyrat proved $g_{d+k}(C_n^d)\geq \frac{d+k}{2d}$
for $1\leq k\leq d$ which is best-possible for even $d+k,$ but not for odd $d+k.$ In order to improve these results, we reduced the problem of computing $g(d,k):=\inf \left\{ g_{d+k}(C_n^d)/n ~|~n\geq 3 \right\}$ to a minimum mean cycle problem. From the obtained data, we could conclude a general conjecture concerning the $(d+k)$-girth of $C_n^d$ for odd values of $d+k.$ We proved this conjecture for $k=d-3.$