84th Workshop on Algorithms and Complexity ("GI Theorietag")
Date: 6 March 2023, directly followed by STACS 2023
Location: Hamburg University of Technology, Schwarzenberg campus (see here for directions), lecture hall A0.13 in the main building A which has barrier-free entrance access.
Invited Plenary Speaker: Prof. Sebastian Siebertz, Bremen University
Participation is free of charge.
The workshop is aimed at all those interested in research in the field of theoretical computer science. The focus is mainly on complexity, algorithms and data structures, as well as parallel and distributed algorithms. We welcome presentations by junior researchers (PhD students) and senior researchers on recent topics in algorithms and complexity. There are no formal proceedings, so both published and unpublished work can be presented, without interfering with any past or future publication. A declared goal of the workshop is to enable contact between young and senior scientists.
The 84th Theorietag of Gesellschaft für Informatik will take place at Hamburg University of Technology (TUHH). This workshop is organized by the Institute for Algorithms and Complexity and the Research Group for Theoretical Computer Science at TUHH.
09.30 - 09.40 Opening address 🌅
Session #1: Graph Algorithms
09.40 - 10.10 Felix Hommelsheim (Universität Bremen)
"Matching Augmentation via Simultaneous Contractions"
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.
10.10 - 10.35 Abhiruk Lahiri
"Maximum edge colouring problem on graphs that exclude a fixed minor"
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.
10.35 - 11.05 Jaroslav Garvardt (Philipps-Universität Marburg)
"Modularity Clustering parameterized by Max Leaf Number"
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.
11.05 - 11.20 coffee/tea break, time for exchange and discussion ☕🍵
Session #2: Exploration
11.20 - 11.50 Petra Wolf (Universitetet i Bergen)
"Kernelizing Temporal Exploration Problems"
We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs G=(G1, G2, ..., GL) 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) = ΣLi=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.
11.50 - 12.20 Jens Schlöter (Universität Bremen)
"Set Selection under Explorable Stochastic Uncertainty via Covering Techniques"
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.
12.20 - 13.15 Lunch break, self-catered lunch in the TUHH mensa 🥘
Session #3: Invited talk
13.15 - 14.15 Prof. Dr. Sebastian Siebertz (Universität Bremen)
"Advances in algorithmic meta-theorems"
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.
14.15 - 14.45 Coffee/tea break, time for exchange and discussion ☕🍵
Session #4: Scheduling
14.45 - 15.15 Ilya Chernykh (Sobolev Institute of Mathematics)
"The Golden Ratio and Normality in the Two-Machine Routing Open Shop"
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.
15.15 - 15.45 Tobias Stamm (TU Hamburg)
"New results for intractable scheduling problems"
We present an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a 1+ε-approximation for Q||Cmax on N jobs in time 2O(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 2O(1/ε log^4(1/ε))+ NO(1). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation which greatly benefits from new support bounds.
15.45 - 16.00 Short break
Session #5: Logic and Formulae
16.00 - 16.30 Volker Diekert (University of Stuttgart)
"Properties of Graphs Specified by a Regular Language"
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 ∈ cGF with a Hamiltonian cycle?
Is there some G ∈ cGF with a perfect matching?
Is there some G ∈ cGF with a dominating set of size at most log2 |VG|?
Is there some G ∈ cGF with a defensive alliance of size at most log2 |VG|?
16.30 - 17.00 Benjamin Böhm (FSU Jena)
"CDCL vs resolution: the picture in QBF"
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).
17.00 - 17.30 Lennart Bittel (Heinrich-Heine Universität Düsseldorf)
"The optimal depth of variational quantum algorithms is QCMA-hard to approximate"
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.
17.30 Time for exchange and discussion
18.30 Closing 🌇
18.30 Joint walk to nearby restaurant for self-paid dinner
There are many more food choices available in the area around the university, as well as the city center of Hamburg!
Contact & Registration
Email: Ms Julia Ehrenbrecht at algo[at]tuhh.de
If you would like to attend: Please register by sending an e-mail to the above address until 22 February 2023.
If you plan to give a talk: Please include in your email (until 22 February 2023) the title and abstract of your talk (preferably send the latex source code). If there is a corresponding manuscript available online, please include a link to the manuscript. Each talk should be in English and about 20 minutes long (followed by a 5-minute discussion round).
The Theorietag on Algorithms and Complexity is a recurring event featured by the Fachgruppe Algorithmen and Fachgruppe Komplexität of the Gesellschaft für Informatik. A list of previous iterations of this event can be found here.