2 citations · 4 across the 7 of their papers we have counts for
9 papers
The Gallai Vertex Problem is -Complete
Amir Nikabadi, Eva Rotenberg, Lasse Wulf
When a graph admits a vertex that is contained in all its longest paths, we call a Gallai vertex. These are named after Gallai, who in 1966 asked the question if it is…
Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
Christoph Grüne, Berit Johannes, James B. Orlin +1
Many natural optimization problems derived from admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objec…
The Presort Hierarchy for Geometric Problems
Ivor van der Hoog, Eva Rotenberg, Jack Spalding-Jamieson +1
Many fundamental problems in computational geometry admit no algorithm running in time for planar input points, via classical reductions from sorting. Prominent e…
The Complexity of Stackelberg Pricing Games
Christoph Grüne, Dorothee Henke, Eva Rotenberg +1
We consider Stackelberg pricing games, which are also known as bilevel pricing problems, or combinatorial price-setting problems. This family of problems consists of games between…
The Complexity of Blocking All Solutions
Christoph Grüne, Lasse Wulf
We consider the general problem of blocking all solutions of some given combinatorial problem with only few elements. For example, the problem of destroying all maximum cliques of…
On the Complexity of the Bilevel Shortest Path Problem
Dorothee Henke, Lasse Wulf
We introduce a new bilevel version of the classic shortest path problem and completely characterize its computational complexity with respect to several problem variants. In our pr…
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
Christoph Grüne, Lasse Wulf
Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consid…
Recognition of Unit Segment and Polyline Graphs is -Complete
Michael Hoffmann, Tillmann Miltzow, Simon Weber +1
Given a set of objects in the plane, the corresponding intersection graph is defined as follows. Each object defines a vertex and an edge joins two vertices whenever the corres…
Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
Christoph Grüne, Lasse Wulf
In bilevel and robust optimization we are concerned with combinatorial min-max problems, for example from the areas of min-max regret robust optimization, network interdiction, mos…