Author name cluster

Peter Rossmanith

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

2 author rows

MFCS Conference 2025 Conference Paper

Solving Partial Dominating Set and Related Problems Using Twin-Width

Jakub Balabán
Daniel Mock
Peter Rossmanith

Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are W[1]-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form ϕ≡∃ x₁⋯ ∃ x_k ∑_{α ∈ I} #y ψ_α(x₁, …, x_k, y) ≥ t, where ψ_α is a quantifier-free formula for each α ∈ I, t is an arbitrary number, and #y is a counting quantifier, can be evaluated in time f(d, k)n, where n is the number of vertices and d is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.

Details

TCS Journal 2024 Journal Article

Transformations of probability distributions

Fabian Frei
Peter Rossmanith

Almost all of computer science is concerned with transformations of information in the form of strings. We initiate the study of a neglected transformation type, namely transformations between probability distributions. We begin by examining the deceivingly simple-looking case of Bernoulli distributions and procedures to transform them. A p-coin is a coin that, whenever tossed, lands heads up with probability p and tails up with probability 1 − p. A neat trick due to von Neumann allows us to simulate a 1/2-coin with any p-coin for an arbitrary unknown p ∈ ( 0, 1 ). We show how to apply this trick to simulate a q-coin for an arbitrary computable q ∈ ( 0, 1 ). In contrast, it is impossible to simulate a q-coin with a noncomputable q. More generally, we are interested in what transformations between probability distributions are feasible. Is it possible to simulate a p / 2 -coin with a p-coin for unknown p? How about 2p or p 2? We attempt to characterize the feasible transformations. For example, we show how to transform a p-coin into an f ( p ) -coin where any finite number of pairs ( p i, f ( p i ) ) of non-zero, non-one probabilities is prescribed, and that it is impossible to do the same for an infinite number of pairs. We also examine which probability distributions are feasible to approximate to arbitrary precision, showing that this is impossible for discontinuous ones but feasible for most but not all remaining ones.

Details DOI

MFCS Conference 2023 Conference Paper

The Online Simple Knapsack Problem with Reservation and Removability

Elisabet Burjons
Matthias Gehnen
Henri Lotze
Daniel Mock
Peter Rossmanith

In the online simple knapsack problem, a knapsack of unit size 1 is given and an algorithm is tasked to fill it using a set of items that are revealed one after another. Each item must be accepted or rejected at the time they are presented, and these decisions are irrevocable. No prior knowledge about the set and sequence of items is given. The goal is then to maximize the sum of the sizes of all packed items compared to an optimal packing of all items of the sequence. In this paper, we combine two existing variants of the problem that each extend the range of possible actions for a newly presented item by a new option. The first is removability, in which an item that was previously packed into the knapsack may be finally discarded at any point. The second is reservations, which allows the algorithm to delay the decision on accepting or rejecting a new item indefinitely for a proportional fee relative to the size of the given item. If both removability and reservations are permitted, we show that the competitive ratio of the online simple knapsack problem rises depending on the relative reservation costs. As soon as any nonzero fee has to be paid for a reservation, no online algorithm can be better than 1. 5-competitive. With rising reservation costs, this competitive ratio increases up to the golden ratio (ϕ ≈ 1. 618) that is reached for relative reservation costs of 1-√5/3 ≈ 0. 254. We provide a matching upper and lower bound for relative reservation costs up to this value. From this point onward, the tight bound by Iwama and Taketomi for the removable knapsack problem is the best possible competitive ratio, not using any reservations.

Details

SODA Conference 2021 Conference Paper

Approximate Evaluation of First-Order Counting Queries

Jan Dreier
Peter Rossmanith

Kuske and Schweikardt introduced the very expressive first-order counting logic FOC( P ) to model database queries with counting operations. They showed that there is an efficient model-checking algorithm on graphs with bounded degree, while Grohe and Schweikardt showed that probably no such algorithm exists for trees of bounded depth. We analyze the fragment FO({>0}) of this logic. While we remove for example subtraction and comparison between two nonatomic counting terms, this logic remains quite expressive: We allow nested counting and comparison between counting terms and arbitrarily large numbers. Our main result is an approximation scheme of the model-checking problem for FO({>0}) that runs in linear fpt time on structures with bounded expansion. This scheme either gives the correct answer or says “I do not know. ” The latter answer may only be given if small perturbations in the number-symbols of the formula could make it both satisfied and unsatisfied. This is complemented by showing that exactly solving the model-checking problem for FO({>0}) is already hard on trees of bounded depth and just slightly increasing the expressiveness of FO({>0}) makes even approximation hard on trees.

Details

MFCS Conference 2020 Conference Paper

Randomization in Non-Uniform Finite Automata

Pavol Duris
Rastislav Královic
Richard Královic
Dana Pardubská
Martin Pasen
Peter Rossmanith

The non-uniform version of Turing machines with an extra advice input tape that depends on the length of the input but not the input itself is a well-studied model in complexity theory. We investigate the same notion of non-uniformity in weaker models, namely one-way finite automata. In particular, we are interested in the power of two-sided bounded-error randomization, and how it compares to determinism and non-determinism. We show that for unlimited advice, randomization is strictly stronger than determinism, and strictly weaker than non-determinism. However, when the advice is restricted to polynomial length, the landscape changes: the expressive power of determinism and randomization does not change, but the power of non-determinism is reduced to the extent that it becomes incomparable with randomization.

Details

TCS Journal 2014 Journal Article

The online knapsack problem: Advice and randomization

Hans-Joachim Böckenhauer
Dennis Komm
Richard Královič
Peter Rossmanith

We study the advice complexity and the random bit complexity of the online knapsack problem. Given a knapsack of unit capacity, and n items that arrive in successive time steps, an online algorithm has to decide for every item whether it gets packed into the knapsack or not. The goal is to maximize the value of the items in the knapsack without exceeding its capacity. In the model of advice complexity of online problems, one asks how many bits of advice about the unknown parts of the input are both necessary and sufficient to achieve a specific competitive ratio. It is well-known that even the unweighted online knapsack problem does not admit any competitive deterministic online algorithm. For this problem, we show that a single bit of advice helps a deterministic online algorithm to become 2-competitive, but that Ω ( log n ) advice bits are necessary to further improve the deterministic competitive ratio. This is the first time that such a phase transition for the number of advice bits has been observed for any problem. Additionally, we show that, surprisingly, instead of an advice bit, a single random bit allows for a competitive ratio of 2, and any further amount of randomness does not improve this. Moreover, we prove that, in a resource augmentation model, i. e. , when allowing the online algorithm to overpack the knapsack by some small amount, a constant number of advice bits suffices to achieve a near-optimal competitive ratio. We also study the weighted version of the problem proving that, with O ( log n ) bits of advice, we can get arbitrarily close to an optimal solution and, using asymptotically fewer bits, we are not competitive. Furthermore, we show that an arbitrary number of random bits does not permit a constant competitive ratio.

Details DOI

TCS Journal 2013 Journal Article

Fast exact algorithm for L ( 2, 1 ) -labeling of graphs

Konstanty Junosza-Szaniawski
Jan Kratochvíl
Mathieu Liedloff
Peter Rossmanith
Paweł Rzążewski

An L ( 2, 1 ) -labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L ( 2, 1 ) -span of a graph is the minimum possible span of its L ( 2, 1 ) -labelings. We show how to compute the L ( 2, 1 ) -span of a connected graph in time O ∗ ( 2. 648 8 n ). Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O ∗ ( 2. 594 4 n ) for claw-free graphs, and in time O ∗ ( 2 n − r ( 2 + n r ) r ) for graphs having a dominating set of size r.

Details DOI

TCS Journal 2011 Journal Article

An exact algorithm for the Maximum Leaf Spanning Tree problem

Henning Fernau
Joachim Kneis
Dieter Kratsch
Alexander Langer
Mathieu Liedloff
Daniel Raible
Peter Rossmanith

Given an undirected graph with n vertices, the Maximum Leaf Spanning Tree problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O ( 4 k poly ( n ) ) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008 [16]). Daligault et al. (2010) [6] improved the branching and obtained a running time of O ( 3. 7 2 k poly ( n ) ). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the Connected Dominating Set problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Ω ( 2 n ) barrier and proposed an O ( 1. 940 7 n ) -time algorithm (Fomin et al. 2008 [11]). Based on some useful properties of Kneis et al. (2008) [16] and Daligault et al. (2010) [6], we present a branching algorithm whose running time of O ( 1. 896 6 n ) has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Ω ( 1. 442 2 n ) for the worst case running time of our algorithm.

Details DOI

TCS Journal 2009 Journal Article

Reoptimization of Steiner trees: Changing the terminal set

Hans-Joachim Böckenhauer
Juraj Hromkovič
Richard Královič
Tobias Mömke
Peter Rossmanith

Given an instance of the Steiner tree problem together with an optimal solution, we consider the scenario where this instance is modified locally by adding one of the vertices to the terminal set or removing one vertex from it. In this paper, we investigate the problem of whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. Our results are as follows: (i) We prove that these reoptimization variants of the Steiner tree problem are NP-hard, even if edge costs are restricted to values from { 1, 2 }. (ii) We design 1. 5-approximation algorithms for both variants of local modifications. This is an improvement over the currently best known approximation algorithm for the classical Steiner tree problem which achieves an approximation ratio of 1 + ln ( 3 ) / 2 ≈ 1. 55. (iii) We present a PTAS for the subproblem in which the edge costs are natural numbers { 1, …, k } for some constant k.

Details DOI

MFCS Conference 2005 Conference Paper

On the Parameterized Complexity of Exact Satisfiability Problems

Joachim Kneis
Daniel Mölle
Stefan Richter 0001
Peter Rossmanith

Abstract For many problems, the investigation of their parameterized complexity provides an interesting and useful point of view. The most obvious natural parameterization for the maximum satisfiability problem—the number of satisfiable clauses—makes little sense, because at least half of the clauses can be satisfied in any formula. We look at two optimization variants of the exact satisfiability problem, where a clause is only said to be fulfilled iff exactly one of its literals is set to true. Interestingly, these variants behave quite differently. In the case of ResMaxExactSAT, where over-satisfied clauses are entirely forbidden, we show fixed parameter tractability. On the other hand, if we choose to ignore over-satisfied clauses, the MaxExactSAT problem is obtained. Surprisingly, it is W[1]-complete. Still, restricted variants of the problem turn out to be tractable.

Details

TCS Journal 2001 Journal Article

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries

Thomas Erlebach
Peter Rossmanith
Hans Stadtherr
Angelika Steger
Thomas Zeugmann

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time O(n2 logn), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time O(n4 logn) (cf. Angluin, J. Comput. Systems Sci. 21(1) (1980) 46–62). Second, we give a parallel version of this algorithm that requires time O(logn) and O(n3/log n) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is O(ℓ2 logℓ) provided the sample strings are drawn from the target language according to a probability distribution with expected string length ℓ. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.

Details DOI

TCS Journal 1998 Journal Article

Unambiguous computations and locally definable acceptance types

Rolf Niedermeier
Peter Rossmanith

Hertrampf's locally definable acceptance types show that many complexity classes can be defined in terms of polynomial-time bounded NTMs with simple local conditions on the nodes of its computation tree, rather than global concepts like number of accepting paths, etc. We introduce a modification of Hertrampf's locally definable acceptance types which allows to get a larger number of characterizable complexity classes. Among others the newly characterizable classes are UP and MOD Zk P. It is shown how different types of oracle access, e. g. , guarded access, can be characterized by this model. This sheds new light on the discussion on how to access unambiguous computation. We present simple functions that describe precisely objects of current research as the unambiguous oracle, alternation, and promise hierarchies. We exhibit the new class UAP which seems to be an unambiguous analogue of Wagner's ▽P. UAP (and thus ▽P) contains Few and is currently the smallest class known with this property.

Details DOI

MFCS Conference 1992 Invited Paper

Parallel Recognition and Ranking of Context-Free Languages

Klaus-Jörn Lange
Peter Rossmanith
Wojciech Rytter

Abstract We survey the efficiency of the ‘fast’ parallel algorithms for the recognition and ranking of context-free languages on the Parallel Random Access Machine without write conflicts. The efficiency of the algorithm is the total number of operations (the product of time and number of processors). Such efficiency depends heavily on the class of context-free grammars and on the meaning of ‘fast’: log(n), log 2 n or sublinear time. The slower is the algorithm the better is its total efficiency. Several new results are presented in the paper. A new simpler version of the log(n) time parallel recognition of unambiguous cfl's is presented. The parallel complexity of ranking and max-word problems for several classes of cfl's is related to the complexity of certain (⊕, ⊗)-transitive closure problems, where (⊕, ⊗)=(+, * ) for the ranking problem of unambiguous languages and (⊕, ⊗)=(max, concat) for the max-word problem. This simplifies the ranking and max-word algorithms and reduces the number of processors.

Details

MFCS Conference 1992 Conference Paper

The Emptiness Problem for Intersections of Regular Languages

Klaus-Jörn Lange
Peter Rossmanith

Abstract Given m finite automata, the emptiness of intersection problem is to determine whether there exists a string which is accepted by all m automata. In the following we consider the case, when m is bounded by a function in the input length, i. e. , in the size and number of the automata. In this way we get complete problems for nondeterministic space-bounded and timespace-bounded complexity classes. Further on, we get close relations to nondeterministic sublinear time classes and to classes which are defined by bounding the number of nondeterministic steps.

Details

MFCS Conference 1990 Conference Paper

Characterizing Unambiguous Augmented Pushdown Automata by Circuits

Klaus-Jörn Lange
Peter Rossmanith

Abstract The notions of weak and strong unambiguity of augmented push-down automata are considered and related to unambiguities of circuits. In particular we exhibit circuit classes exactly characterizing polynomially time bounded unambiguous augmented push-down automata.

Details