We consider the following problem: Given a set $S$ of $n$ distinct points in the plane, how many edge-disjoint plane straight-line spanning paths can be drawn on $S$? Each spanning path must be crossing-free, but edges from different paths are allowed to intersect at arbitrary points. It is known that if the points of $S$ are in convex position, then $\lfloor n/2 \rfloor$ such paths always exist. However, for general point sets, the best known construction yields only two edge-disjoint plane spanning paths. In this paper, we prove that for any set $S$ of at least ten points in general position (i.e., no three points are collinear), it is always possible to draw at least three edge-disjoint plane straight-line spanning paths. Our proof relies on a structural result about halving lines in point sets and builds on the known two-path construction, which we also strengthen: we show that for any set $S$ of at least six points, and for any two specified points on the boundary of the convex hull of $S$, there exist two edge-disjoint plane spanning paths that start at those prescribed points. Finally, we complement our positive results with a lower bound: for every $n \geq 6$, there exists a set of $n$ points for which no more than $\lceil n/3 \rceil$ edge-disjoint plane spanning paths are possible.

The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend this algorithmic question to deterministic automata beyond finite automata. We prove that the question of synchronizability becomes undecidable even when looking at deterministic one-counter automata. This is also true for another classical mild extension of regularity, namely that of deterministic one-turn push-down automata. However, when we combine both restrictions, we arrive at scenarios with a PSPACE-complete (and hence decidable) synchronizability problem. Likewise, we arrive at a decidable synchronizability problem for (partially) blind deterministic counter automata. There are several interpretations of what synchronizability should mean for deterministic push-down automata. This is depending on the role of the stack: should it be empty on synchronization, should it be always the same or is it arbitrary? For the automata classes studied in this paper, the complexity or decidability status of the synchronizability problem is mostly independent of this technicality, but we also discuss one class of automata where this makes a difference.

In this paper we propose a novel approach for checking satisfiability of non-linear constraints over the reals, called ksmt. The procedure is based on conflict resolution in CDCL style calculus, using a composition of symbolical and numerical methods. To deal with the non-linear components in case of conflicts we use numerically constructed restricted linearisations. This approach covers a large number of computable non-linear real functions such as polynomials, rational or trigonometrical functions and beyond. A prototypical implementation has been evaluated on several non-linear SMT-LIB examples and the results have been compared with state-of-the-art SMT solvers.

An obstacle representation of a graph $G$ consists of a set of polygonal obstacles and a drawing of $G$ as a visibility graph with respect to the obstacles: vertices are mapped to points and edges to straight-line segments such that each edge avoids all obstacles whereas each non-edge intersects at least one obstacle. Obstacle representations have been investigated quite intensely over the last few years. Here we focus on outside-obstacle representations (OORs) that use only one obstacle in the outer face of the drawing. It is known that every outerplanar graph admits such a representation. We strengthen this result by showing that every (partial) 2-tree has an OOR. We also consider restricted versions of OORs where the vertices of the graph form a convex polygon or even a regular polygon. We characterize when the complement of a tree and when a complete graph minus a simple cycle admits a convex OOR. We construct regular OORs for all (partial) outerpaths, cactus graphs, and grids.

We study the algorithmic complexity of partitioning the vertex set of a given (di)graph into a small number of paths. The Path Partition problem (PP) has been studied extensively, as it includes Hamiltonian Path as a special case. The natural variants where the paths are required to be either \emph{induced} (Induced Path Partition, IPP) or \emph{shortest} (Shortest Path Partition, SPP), have received much less attention. Both problems are known to be NP-complete on undirected graphs; we strengthen this by showing that they remain so even on planar bipartite directed acyclic graphs (DAGs), and that SPP remains NP-hard on undirected bipartite graphs. When parameterized by the natural parameter ``number of paths'', both SPP and IPP are shown to be W[1]-hard on DAGs. We also show that SPP is in XP both for DAGs and undirected graphs for the same parameter, as well as for other special subclasses of directed graphs (IPP is known to be NP-hard on undirected graphs, even for two paths). On the positive side, we show that for undirected graphs, both problems are in FPT, parameterized by neighborhood diversity. We also give an explicit algorithm for the vertex cover parameterization of PP. When considering the dual parameterization (graph order minus number of paths), all three variants, IPP, SPP and PP, are shown to be in FPT for undirected graphs. We also lift the mentioned neighborhood diversity and dual parameterization results to directed graphs; here, we need to define a proper novel notion of directed neighborhood diversity. As we also show, most of our results transfer to the case of covering by edge-disjoint paths, and purely covering.

In this paper, we study the task of enumerating (and counting) locally and globally minimal defensive alliances in graphs. We consider general graphs as well as special graph classes. From an input-sensitive perspective, our presented algorithms are mostly optimal.

We exhibit a winning strategy for Synchronizer in the synchronization game on every synchronizing automaton in whose transition monoid the regular D-classes form subsemigroups

The literature on word-representable graphs is quite rich, and a number of variations of the original definition have been proposed over the years. We are initiating a systematic study of such variations based on formal languages. In our framework, we can associate a graph class to each language over the binary alphabet \{0,1\}. All graph classes that are language-representable in this sense are hereditary and enjoy further common properties. Besides word-representable graphs and, more generally, 1^k- or k-11-representable graphs, we can identify many more graph classes in our framework, like (co)bipartite graphs, (co)comparability graphs, to name a few. It was already known that any graph is 111- or 2-11-representable. When such representations are considered for storing graphs, 111- or 2-11-representability bears the disadvantage of being significantly inferior to standard adjacency matrices or lists. We prove that quite famous languages like the palindromes, the copy language or the Lyndon words can match the efficiency of standard graph representations. The perspective of language theory allows us to prove general results that hold for all graph classes that can be defined in this way. This includes certain closure properties (e.g., all language-definable graph classes are hereditary) as well as certain limitations (e.g., all language-representable graph classes contain graphs of arbitrarily large treewidth and of arbitrarily large degeneracy, except a trivial case). As each language describes a graph class, we can also ask decidability questions concerning graph classes, given a concrete presentation of a formal language. We also present a systematic study of graph classes that can be represented by languages in which each letter occurs at most twice. Here, we find graph classes like interval, permutation, circle, bipartite chain, convex, and threshold graphs.

Keyword-based searches are today's standard in digital libraries. Yet, complex retrieval scenarios like in scientific knowledge bases, need more sophisticated access paths. Although each document somewhat contributes to a domain's body of knowledge, the exact structure between keywords, i.e., their possible relationships, and the contexts spanned within each single document will be crucial for effective retrieval. Following this logic, individual documents can be seen as small-scale knowledge graphs on which graph queries can provide focused document retrieval. We implemented a full-fledged graph-based discovery system for the biomedical domain and demonstrated its benefits in the past. Unfortunately, graph-based retrieval methods generally follow an 'exact match' paradigm, which severely hampers search efficiency, since exact match results are hard to rank by relevance. This paper extends our existing discovery system and contributes effective graph-based unsupervised ranking methods, a new query relaxation paradigm, and ontological rewriting. These extensions improve the system further so that users can retrieve results with higher precision and higher recall due to partial matching and ontological rewriting.

The aim of this article is to define and compare several distances (or metrics) between operators acting on different (separable) Hilbert spaces. We consider here three main cases of how to measure the distance between two bounded operators: first by taking the distance between their unitary orbits, second by isometric embeddings (this generalises a concept of Weidmann) and third by quasi-unitary equivalence (using a concept of the first author of the present article). Our main result is that the unitary and isometric distances are equal provided the operators are both self-adjoint and have $0$ in their essential spectra. Moreover, the quasi-unitary distance is equivalent (up to a universal constant) with the isometric distance for any pair of bounded operators. The unitary distance gives an upper bound on the Hausdorff distance of their spectrum. If both operators have purely essential spectrum, then the unitary distance equals the Hausdorff distance of their spectra. Using a finer spectral distance respecting multiplicity of discrete eigenvalues, this spectral distance equals the unitary distance also for operators with essential and discrete spectrum. In particular, all operator distances mentioned above are equal to this spectral distance resp. controlled by it in the quasi-unitary case for self-adjoint operators with $0$ in the essential spectrum. We also show that our results are sharp by presenting various (counter-)examples. Finally, we discuss related convergence concepts complementing results from our first article arXiv:2202.03234

We present results concerning the norm convergence of resolvents for wildperturbations of the Laplace-Beltrami operator. This article is a continuation of ouranalysis on wildly perturbed manifolds presented in [AP21]. We study here manifoldswith an increasing number of small (i.e., short and thin) handles added. The handlescan also be seen as wormholes, as they connect different parts being originally far this http URL consider two situations: if the small handles are distributed too sparse the limitoperator is the unperturbed one on the initial manifold, the handles are fading. Onthe other hand, if the small handles are dense in certain regions the limit operator isthe Laplace-Beltrami operator acting on functions which are identical on the two partsjoined by the handles, the handles hence produce adhesion. Our results also apply tonon-compact manifolds. Our work is based on a norm convergence result for operatorsacting in varying Hilbert spaces described in the book [P12] by the second author.

We study the computational complexity of the membership problem for arithmetic circuits over natural numbers with division. We consider different subsets of the operations {intersection,union,complement,+,x,/}, where / is the element-wise integer division (without remainder and without rounding). Results for the subsets without division have been studied before, in particular by McKenzie and Wagner and Yang. The division is expressive because it makes it possible to describe the set of factors of a given number as a circuit. Surprisingly, the cases {intersection,union,complement,+,/} and {intersection,union,complement,x,/} are PSPACE-complete and therefore equivalent to the corresponding cases without division. The case {union,/} is NP-hard in contrast to the case {union} which is NL-complete. Further upper bounds, lower bounds and completeness results are given.

In this article we discuss the convergence of first order operators on a thickened graph (a graph-like space) towards a similar operator on the underlying metric graph. On the graph-like space, the first order operator is of the form exterior derivative (the gradient) on functions and its adjoint (the negative divergence) on closed 1-forms (irrotational vector fields). Under the assumption that each cross section of the tubular edge neighbourhood is convex, that each vertex neighbourhood is simply connected and under suitable uniformity assumptions (which hold in particular, if the spaces are compact) we establish generalised norm resolvent convergence of the first order operator on the graph-like space towards the one on the metric graph. The square of the first order operator is of Laplace type; on the metric graph, the function (0-form) component is the usual standard (Kirchhoff) Laplacian. A key ingredient in the proof is a uniform Gaffney estimate: such an estimate follows from an equality relating here the divergence operator with all (weak) partial derivatives and a curvature term, together with a (localised) Sobolev trace estimate.

The purpose of this article is to give a short introduction to the concept of quasi-unitary equivalence of quadratic forms and its consequences. In particular, we improve an estimate concerning the transitivity of quasi-unitary equivalence for forms. We illustrate the abstract setting by two classes of examples.

We consider Schr\"odinger operators on a bounded, smooth domain of dimension $d \ge 2$ with Dirichlet boundary conditions and a properly scaled potential, which depends only on the distance to the boundary of the domain. Our aim is to analyse the convergence of these operators as the scaling parameter tends to zero. If the scaled potential is resonant, the limit in strong resolvent sense is a Robin Laplacian with boundary coefficient expressed in terms of the mean curvature of the boundary. A counterexample shows that norm resolvent convergence cannot hold in general in this setting. If the scaled potential is non-negative (hence non-resonant), the limit in strong resolvent sense is the Dirichlet Laplacian. We conjecture that we can drop the non-negativity assumption in the non-resonant case.

In this paper, we address the enumeration of (induced) $s$-$t$ paths and minimal $s$-$t$ separators. These problems are some of the most famous classical enumeration problems that can be solved in polynomial delay by simple backtracking for a (un)directed graph. As a generalization of these problems, we consider the (induced) $s$-$t$ hyperpath and minimal $s$-$t$ separator enumeration in a \emph{directed hypergraph}. We show that extending these classical enumeration problems to directed hypergraphs drastically changes their complexity. More precisely, there are no output-polynomial time algorithms for the enumeration of induced $s$-$t$ hyperpaths and minimal $s$-$t$ separators unless $P = NP$, and if there is an output-polynomial time algorithm for the $s$-$t$ hyperpath enumeration, then the minimal transversal enumeration can be solved in output polynomial time even if a directed hypergraph is $BF$-hypergraph. Since the existence of an output-polynomial time algorithm for the minimal transversal enumeration has remained an open problem for over 45 years, it indicates that the $s$-$t$ hyperpath enumeration for a $BF$-hypergraph is not an easy problem. As a positive result, the $s$-$t$ hyperpath enumeration for a $B$-hypergraph can be solved in polynomial delay by backtracking.

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.

We study the pricing and hedging of derivative securities with uncertainty about the volatility of the underlying asset. Rather than taking all models from a prespecified class equally seriously, we penalise less plausible ones based on their "distance" to a reference local volatility model. In the limit for small uncertainty aversion, this leads to explicit formulas for prices and hedging strategies in terms of the security's cash gamma.

In many spinning processes, as for example in dry spinning, solvent evaporates out of the spun jets and leads to thinning and solidification of the produced fibers. Such production processes are significantly driven by the interaction of the fibers with the surrounding airflow. Faced with industrial applications producing up to several hundred fibers simultaneously, the direct numerical simulation of the three-dimensional multiphase, multiscale problem is computationally extremely demanding and thus in general not possible. In this paper, we hence propose a dimensionally reduced, efficiently evaluable fiber model that enables the realization of fiber-air interactions in a two-way coupling with airflow computations. For viscous dry spinning of an uni-axial two-phase flow, we deduce one-dimensional equations for fiber velocity and stress from cross-sectional averaging and combine them with two-dimensional advection-diffusion equations for polymer mass fraction and temperature revealing the radial effects that are observably present in experiments. For the numerical treatment of the resulting parametric boundary value problem composed of one-dimensional ordinary differential equations and two-dimensional partial differential equations we develop an iterative coupling algorithm. Thereby, the solution of the advection-diffusion equations is implicitly given in terms of Green's functions and leads for the surface values to Volterra integral equations of second kind with singular kernel, which we can solve very efficiently by the product integration method. For the ordinary differential equations a suitable collocation-continuation procedure is presented. Compared with the referential solution of a three-dimensional setting, the numerical results are very convincing. They provide a good approximation while drastically reducing the computational time.