MDS Statusworkshop 2008/09
January 27 and February 3, 2009
Technische Universität Berlin
New Room:
MA 313 (Math Building, Third Floor)
Program
Abstracts
Marc Thurley - Extended Complexity Classifications of Partition Functions
Partition functions are weighted generalizations of graph-homomorphism counting problems. Every partition function is a graph invariant defined by some quadratic matrix A. Recently the complexity of computing these functions has been classified for all cases where the matrix A is a real-valued and symmetric. I will mainly focus on discussing how these results can be generalized to Hermitian matrices.
Christina Puhl - More about Recoverable Robust Shortest Path Problems
The shortest path problem with nonnegative arc lengths can be solved easily. Yet, in many real-world applications the arc lengths underlie significant uncertainties. To deal with these, the classical strict notion of robustness yields a solution, which is feasible for any scenario, but has unacceptably high costs. To avoid this drawback, the recoverable robust approach allows a solution to be recovered to a certain extent after a change of data. In my last talk (MDS Monday Colloquium 24.11.08), I introduced the k-Arc-RRSP problem. In this setting the costs of the arcs are subject to uncertainty. In a first stage a path is chosen, which can be altered by at most k arcs in the recovery. In this talk I will define a generalization of the problem, in which a subgraph instead of a path can be chosen in the first stage. For this general setting we discuss again its complexity status depending on the three classes of scenario sets.
Hiêp Hàn - Degree conditions for spanning subhypergraphs
A fundamental question in extremal graph theory asks for sufficient minimum degree conditions $\delta(G)$ which ensure the existence of a given graph in $G$ as spanning subgraph. A theorem of this flavour is for example Dirac's Theorem on the existence of Hamilton cycles. In this talk we study similar questions for hypergraphs.
Bruno Benedetti - Counting footballs
A famous open problem in combinatorics is the asymptotic enumeration of simplicial spheres, either with respect to the number n of vertices, or with respect to the number N of simplices. The problem is interesting because the correctness of a recent theory in Physics, called "discrete quantum gravity", depends on the answer. In 25 minutes, we sketch successful and not-so-successful approaches that have been tried over the last 100 years.
Felix Breuer - Counting hexagonal patches in polynomial time
A hexagonal patch is a plane graph with boundary vertices of degree 2 or 3, interior vertices of degree 3, and interior faces of degree 6. When is a sequence of 2s and 3s the boundary sequence of a hexagonal patch? How many such hexagonal patches are there? We present a polynomial time algorithm for these problems and explain how they are related to the following curve problem: When can a "nice" map c:S^1->R^2 be extended to a local homeomorphism d:D^2->R^2?
Paul Bonsma - Finding fullerene patches in polynomial time: reducing 5-faces
Fullerene molecules can be modelled as 3-regular planar graphs with only 5-faces and 6-faces. For studying how these molecules are formed, the following subgraphs are important: a fullerene patch is a 2-connected plane graph where inner faces have length 5 or 6, internal vertices have degree 3, and boundary vertices have degree 2 or 3. The boundary code of a fullerene patch is the degree sequence along the outer face. Although different patches can have the same boundary code, the number of 5-faces of a fullerene patch is uniquely determined by the boundary code. We consider the following well-studied decision problem from computational chemistry: given a sequence of twos and threes, does there exist a fullerene patch with this boundary code? We give the first polynomial time algorithm for this problem, for boundary codes with at most five 5-faces. An essential ingredient is the algorithm for patches without 5-faces that will be presented by Felix Breuer. The talk with end with open questions on the complexity of (variants of) the problem. This is joint work with Felix Breuer.
Sarah Li - Dimension of the Incidence Poset of Graphs Embeddable on Surfaces of Higher Genus
With a finite graph $G$, associate an incidence poset P=($X$, $P$) defined by setting $X$ = $V \cup E$ and $x<e$ in P if and only if $x$ is an end point of $e$ in $G$. By using the classical combinatorial structure for planar graphs called Schnyder Woods, W. Schnyder established the following well-known result: A graph $G$ is planar if and only if the dimension of its incidence poset is at most 3. In line with this, we are interested in finding an upper bound for the dimension of the incidence poset of graphs embeddable on surfaces of higher genus. I will give an exploratory talk of my research on this problem.
Ronald Wotzlaw - Skeleta of Polytopes
I will talk about two topics related to combinatorial and structural properties of polytope skeleta: incidence graphs and unneighborly polytopes. Incidence graphs are defined by incidence relations among the faces of a polytope. I will talk about basic properties of these graphs (mainly connectivity with Balinski's theorem on $d$-connectedness of $d$-polytope graphs as a special case) and mention open problems. An unneighborly polytope is a polytope in which every vertex lies on a "missing edge." I will talk about their generalization to higher skeleta, about the very basic question on the minimum number of vertices these polytopes can have (which we cannot answer), and related topics (Perles' Skeleton Theorem, illuminated polytopes).
Siamak Tazari - Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
Hans Raj Tiwary - Covering space with Cones
Given a set of polyhedral cones in $R^d$ we want to decide whether a set $D$ is covered by these cones. We consider the cases when $D$ is either the whole space of a linear subspace. The complexity of the problem depends on the representation of the cones and also on how they intersect with each other. In this talk I will discuss the motivation for this problem and the complexity of various cases. This is a joint work with Khaled Elbassioni.
Mareike Massow - More on Diametral Pairs of Linear Extensions
Given a finite poset P, we consider pairs of linear extensions of P with maximal distance. The distance of two linear extensions L_1, L_2 is the number of pairs of elements of P appearing in different orders in L_1 and L_2. A diametral pair maximizes the distance among all pairs of linear extensions of P. We show that deciding if P has two linear extensions of distance at least k is NP-complete for general P, and can be solved in polynomial time for posets of width 3. Felsner and Reuter conjectured that in every diametral pair at least one of the two linear extensions reverses a critical pair of P. In my last MDS talk, I presented a positive answer for several subclasses of posets. Now we will see a counterexample disproving the general conjecture. On the other hand, we show that the conjecture holds for almost all posets. These results are joint work with Graham Brightwell. I will also report about the progress on diametral pairs of linear extensions of the Boolean lattice.
Holger Dell - Subexponential Time Complexity
The counting exponential time complexity (#ETH) is that no algorithm can compute the number of satisfying assignments of a 3-CNF formula in subexponential time. Is this hypothesis much stronger than the corresponding hypothesis for decision problems? There is an interesting connection between the concept of kernelization from parameterized complexity and subexponential time complexity. Recently, conditional superpolynomial lower bounds for kernels of several NP-complete problems have been established. Can these lower bounds shed more light into the area of subexponential time complexity? Conversely, can the techniques developed for subexponential time complexity be used to get better problem kernels? In the talk, I will present some barriers and rays of hope around these and other central open questions in the area.
Kolja Knauer - From chip-firing to partial cubes
Bjoerner/Lovasz/Shor's chip-firing games (aka sandpile models) yield upper locally distributive lattices. We show that not every such lattice can be represented as a chip-firing game, but as a vector-addition-language - a slight generalization of chip-firing games. We will see how some concepts related to chip-firing games translate to the lattices and vice-versa. Finally we describe these lattices as partial cubes (isometrical subgraphs of hypercubes) and point out some open questions.
Bastian Laubner - Properties and expressiveness of rank logics
I consider fixed-point logic (FP) and first-order logic (FO) in conjunction with operators that can calculate the rank of FO or FP-definable matrices. These logics are more expressive than the respective logics with counting operators, which makes them, albeit unlikely, candidates for capturing PTIME (on general structures). I investigate the basic properties of these rank operators in relation to the different logics. One result of my work is that FO with rank operators over the finite field of characteristic p captures the complexity class MOD-p-L; in particular Parity-L is captured by FO with rank over GF(2).
Yury Person - Applications of weak hypergraph regularity lemma
We will give a short overview of recent applications of the weak hypergraph regularity lemma.
Kord Eickmeyer - Derandomisation of few random bits
Complexity theory explores the capabilities of computers with restricted ressources, such as a polynomial amount of time or a logarithmic amount of space relative to the size of the input. For many problems we know efficient algorithms which, in addition to classical computation steps, make random choices. The question of whether this can lead to a significant saving in other ressources (in particular time) has become a central topic in theoretical computer science. We are particularly interested in the case where the amount of random choices is limited as well.
Jens Schmidt - Construction sequences of 3-connected graphs
Let H be a subdivision of a 3-connected subgraph in G of constant size and let O be a set of operations on graphs. Then a construction sequence from H to G is a sequence of operations in O that are performed iteratively to H, yielding G, and in which all intermediate graphs are 3-connected. We discuss some existence results about construction sequences that typically start with a K_4 subdivision (some results are well-known, some are related to the MDS talk a week before).
