Fleszar, Krzysztof

Given a set of \($k$\)-colored points in the plane, we consider the problem of finding \($k$\) trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For \($k=1$\), this is the well-known Euclidean Steiner tree problem. For general \($k$\), a \($k\rho$\)-approximation algorithm is known, where \($\rho \le 1.21$\) is the Steiner ratio. We present a PTAS for \($k=2$\), a \($(5/3+\varepsilon)$\)-approximation for \($k=3$\), and two approximation algorithms for general \($k$\), with ratios \($O(\sqrt n \log k)$\) and \($k+\varepsilon$\).

In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.

An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions. There are at least two computational tasks associated with an NP search problem: (i) Find out whether a solution exists. (ii) Compute an arbitrary solution. Further computational tasks arise in settings with multiple objectives, for example: (iii) Compute a solution that is minimal w.r.t. the first objective, while the second objective does not exceed some budget. Each such computational task defines a class of multivalued functions. We systematically investigate these classes and their relation to traditional complexity classes and classes of multivalued functions, like NP or max·P. For multiobjective problems, some classes of computational tasks turn out to be equivalent to the function class NPMV_g , some to the class of decision problems NP, and some to a seemingly new class that includes both NPMV_g and NP. Under the assumption that certain exponential time classes are different, we show that there are computational tasks of multiobjective problems (more precisely functions in NPMV_g) that are Turing-inequivalent to any set.

Since the proofs of Szelepscényi Szel87 and Immerman Imme88 it is known that nondeterministic space-bounded complexity classes are closed under complementation. Consequently this result is true for nondeterministic Turing machines bounded by logarithmic space, or equivalently for nondeterministic finite automata with two-way input heads. By utilizing the inductive counting technique Cook et al. showed that complementation holds also for LOGCFL, a complexity class that can be represented by nondeterministic finite pushdown automata bounded by polynomial time. This raises the question how the complementation of these automata is related to the increase of input heads of the complementing machine. The following results are evinced: 1. For every language L accepted by a nondeterministic finite automaton with k two-way input heads there exists a nondeterministic finite automaton with 8k+1 two-way input heads accepting the complement of L. 2. For every language L accepted by a nondeterministic pushdown automaton M with k two-way input heads working in time n^r there exists a nondeterministic pushdown automaton M′ with 18k+5r two-way input heads accepting the complement of L in time O(n^8k+2r).