We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a 2-edge-connected spanning subgraph by adding the minimum number of edges to it. We present a polynomial-time algorithm with an approximation ratio of 13/8 = 1.625 improving upon an earlier 5/3-approximation. The improvement builds on a new ⍺-approximation preserving reduction for any ⍺ ≥ 3/2 from arbitrary MAP instances to well-structured instances that do not contain certain forbidden structures like parallel edges, small separators, and contractible subgraphs. We further introduce, as key ingredients, the technique of repeated simultaneous contractions and provide improved lower bounds for instances that cannot be contracted.

The maximum edge colouring problem considers the maximum colour assignment to edges of a graph under the condition that every vertex has at most a fixed number of distinct coloured edges incident on it. If that fixed number is q we call the colouring a maximum edge q-colouring. The problem models a non-overlapping frequency channel assignment question on wireless networks. The problem has also been studied from a purely combinatorial aspect in the graph theory literature. We studied the question when the input graph is sparse.

In this talk, we will show that the problem remains NP-hard on 1-apex graphs. We will also show that there exists PTAS for the problem on minor free graphs. The PTAS is based on a recently developed Baker game technique for proper minor-closed classes, thus avoiding the need to use any involved structural results. This further pushes the Baker game technique beyond the problems expressible in the first-order logic.

The modularity of a graph is an important measure for clustering and community detection in networks. However, computing the maximum modularity of a graph is known to be NP-hard, so in practice heuristic approaches with no guarantee on the quality of the solution are deployed. Recently Meeks and Skerman initiated the study of the corresponding decision problem Modularity in the context of parameterized complexity. They showed that Modularity is in XP when parameterized by treewidth or max leaf number. For the parameter max leaf number they conjectured that the problem is even in FPT. In this work we present an FPT-algorithm for Modularity with respect to max leaf number, thus confirming the conjecture.

We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs G=(G₁, G₂, ..., G_L) that share a common vertex set but might have different edge sets.  The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner, asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph with infinite speed. The exploration must at the latest be completed in the last snapshot graph. The optimization variant of this problem is the k-arb NS-TEXP problem, whether the agent's task is to visit at least k vertices of the temporal graph.
We show that under standard computational complexity assumptions, neither of the problems NS-TEXP nor k-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices n, lifetime L, number of vertices to visit k, and maximal number of connected components per time step γ; as well as in the combined parameters L+k, L + γ, and k+γ. On the way to establishing these lower bounds, we answer a couple of questions left open by  Erlebach and Spooner.

We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph
 p(G) = Σ^L_i=1(|E(G_i)|) - |V(G)| +1. Informally, this parameter measures how dynamic the temporal graph is. Our main algorithmic result is the construction of a polynomial (in p(G)) kernel for the more general Weighted k-arb NS-TEXP problem, where weights are assigned to the vertices and the task is to find a temporal walk of weight at least k.

Given subsets of uncertain values, we study the problem of identifying the subset of minimum total value (sum of the uncertain values) by querying as few values as possible.
This set selection problem falls into the field of explorable uncertainty and is of intrinsic importance therein as it implies strong adversarial lower bounds for a wide range of interesting combinatorial problems such as knapsack and matchings.
We consider a stochastic problem variant and give algorithms that, in expectation, improve upon these adversarial lower bounds.
The key to our results is to prove a strong structural connection to a seemingly unrelated covering problem with uncertainty in the constraints via a linear programming formulation.
We exploit this connection to derive an algorithmic framework that can be used to solve both problems under uncertainty, obtaining nearly tight bounds on the competitive ratio. This is the first non-trivial stochastic result in explorable uncertainty concerning the sum of unknown values without further structure known for the set. With our novel methods, we lay the foundations for solving more general problems in the area of explorable uncertainty.

Algorithmic meta-theorems provide general explanations when and why certain algorithmic problems can be solved efficiently. They are typically formulated in terms of logic (defining the descriptive complexity of the problems) and structural properties of their inputs. A prototypical algorithmic meta-theorem is Courcelle’s Theorem, stating that every graph property definable in monadic second-order logic (MSO) can be decided in linear time on every graph class of bounded treewidth. Similarly, every graph property definable in first-order logic (FO) can be tested efficiently on every nowhere dense graph class. 

In this talk I will present recent progress on algorithmic meta-theorems for FO on dense graph classes as well as for logics whose expressive power lies between MSO and FO. The presented results reveal beautiful connections between structural graph theory, classical model theory and algorithmics. 

We consider the routing open shop, being a generalization of two well-known discrete optimization problems, namely open shop and metric traveling salesman problem. Immovable jobs are located at the nodes of the transportation network, and mobile machines have to tra- verse the network, sequentially performing operations on the jobs. Each job has to be processed by each machine in arbitrary order, processing times are known in advance. The machines are initially located at the predefined depot and have to return there after processing the jobs. The goal is to construct a feasible schedule with minimal makespan. The problem is known to be NP-hard even for the simplest case with two machines and two nodes. Moreover, it remains NP-hard in the special proportionate case, when processing times do not depend on machine. We propose a new special case for scheduling problems with proportional processing times or rank P = 1, where P is the matrix of processing times. We investigate the two-machine routing open shop with at most three nodes of transportation network in terms of proportionality factor k of rows of P and present the following results:

1. the problem instance is normal (i.e. its optimal makespan coincides with the standard lower bound ¯R) if and only if k ≥ Φ, where Φ is the golden ratio;

2. for any k ∈ [1, Φ] the optimal makespan does not exceed f(k) = (4k^2+3k)/(5k^2+2k−1) ¯R;

3. an optimal schedule in case k ≥ Φ and a feasible schedule with makespan at most f(k) ¯R can be constructed in linear time.

Therefore, we describe a new polynomially solvable case (k ≥ Φ) and a linear approximation algorithm for which the worst performance ratio guarantee is as small as theoretically possible in terms of the standard lower bound.

We present an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||C_max).
Our EPTAS yields a 1+ε-approximation for Q||C_max on N jobs in time 2^{O(1/ε log^3(1/ε)log(log(1/ε)))}+ O(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2^{O(1/ε log^4(1/ε))}+ N^O(1).
Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||C_max, as we reduce the problem to a novel MILP formulation which greatly benefits from new support bounds.

The talk is based on a joint work with Henning Fernau (Trier) and Petra Wolf (Bergen, Norway).
It reports on some research which was initiated in the Master Thesis of Petra Wolf at the University Tübingen under direction of Klaus-Jörn Lange. Petra reported about her earlier results at the 77th Workshop about Algorithms and Complexity in Marburg 2019. 

The starting point is the question whether there is a graph satisfying a graph property Φ in a family of graphs given by a set of words under the assumption each word represents a finite graph? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided for regular languages by studying the syntactic monoid of the specification language.
More specifically, we use a natural binary encoding of finite graphs over a binary alphabet Σ, and we define a regular set G ⊆ Σ^* such that every nonempty word w ∈ G defines a finite  and nonempty graph.
Also, graph properties can then be syntactically defined as languages over Σ.
Then, we ask whether the automaton A specifies some graph satisfying a certain property Φ.
Our structural results show that we can answer this question for all ``typical'' graph properties. For example, the following problems are decidable. 

• Is there some G ∈ cG_F with a Hamiltonian cycle?
• Is there some G ∈ cG_F  with a perfect matching?
• Is there some G ∈ cG_F  with a dominating set of size at most log₂ |V_G|?
• Is there some G ∈ cG_F  with a defensive alliance of size at most log₂ |V_G|?

This talk will cover the relations between QBF resolution and QCDCL solving algorithms. Modelling QCDCL as proof systems we show that QCDCL and Q- Resolution are incomparable. We also introduce new versions of QCDCL that turn out to be stronger than the classic models. This talk is based on a couple of recent papers (joint with Olaf Beyersdor and Tomas Peitl, which appeared in ITCS’21, SAT’21, SAT’22 and IJCAI’22).

Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the depth of the variational “ansatz” used — the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant ε > 0, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor N , where N denotes the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists in the even “simpler” QAOA-type settings. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems.

Uni Grillhouse - Döner Kebap

Croque Master - French style croque

Kaiserlich - traditional German food

VietNo1 - Vietnamese food

Panthera Rodizio - Brazilian buffet style

There are many more food choices available in the area around the university, as well as the city center of Hamburg!