We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications, however, the graph that defines which vertex sets are feasible is not the same as the graph that governs how tokens, agents, or resources may move. Existing models such as token sliding and token jumping typically do not distinguish the problem graph and the movement graph. Motivated by this mismatch, we introduce a directed weighted two-graph model that cleanly separates feasibility from movement. A problem graph specifies the desired combinatorial objects, while a movement graph specifies admissible relocations and their costs. This yields a flexible framework that captures asymmetry, heterogeneous movement constraints, and weighted transitions, while subsuming classical discovery models as special cases. We investigate this model through Path Discovery and Shortest Path Discovery, where the task is to realize a vertex set containing an s-t-path or a shortest s-t-path in the problem graph. These problems are particularly natural in applications, since directed and weighted shortest paths are among the most fundamental algorithmic primitives. At the same time, previous work has already shown that discovery can be computationally hard even when the underlying optimization problem is easy. Our results show that this phenomenon persists, and becomes especially rich, in the two-graph setting. We obtain a detailed complexity picture, identifying tractable cases as well as strong hardness results.

Abstract. Given two [Formula: see text]-vertex graphs [Formula: see text] and [Formula: see text] of bounded treewidth, is there an [Formula: see text]-vertex graph [Formula: see text] of bounded treewidth having subgraphs isomorphic to [Formula: see text] and [Formula: see text]? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if [Formula: see text] is a binary tree and [Formula: see text] is a ternary tree. We also provide an extensive study of cases where such “gluing” is possible. In particular, we prove that if [Formula: see text] has treewidth [Formula: see text] and [Formula: see text] has pathwidth [Formula: see text], then there is an [Formula: see text]-vertex graph of treewidth at most [Formula: see text] containing both [Formula: see text] and [Formula: see text] as subgraphs.

We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs is monadically stable if it is impossible to define arbitrarily long linear orders in vertex-colored graphs from using a fixed first-order formula. Similarly, monadic dependence corresponds to the impossibility of defining all graphs in this way. Examples of monadically stable graph classes are nowhere dense classes, which provide a robust theory of sparsity. Examples of monadically dependent classes are classes of bounded rankwidth (or equivalently, bounded cliquewidth), which can be seen as a dense analog of classes of bounded treewidth. Thus, monadic stability and monadic dependence extend classical structural notions for graphs by viewing them in a wider, model-theoretical context. We explore this emerging theory by proving the following: 1) A class of graphs is a first-order transduction of a class with bounded treewidth if and only if has bounded rankwidth and a stable edge relation (i.e. graphs from exclude some half-graph as a semi-induced subgraph). 2) If a class of graphs is monadically dependent and not monadically stable, then has in fact an unstable edge relation. As a consequence, we show that classes with bounded rankwidth excluding some half-graph as a semi-induced subgraph are linearly χ-bounded. Our proofs are effective and lead to polynomial time algorithms.

Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths. These results show a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes: 1) Graphs with linear rankwidth at most r are linearly χ-bounded. Actually, they have bounded c-chromatic number, meaning that they can be colored with f (r) colors, each color inducing a cograph. 2) Based on a Ramsey-like argument, we prove for every proper hereditary family of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in . 3) For a class with bounded linear rankwidth the following conditions are equivalent: a) is stable, b) excludes some half-graph as a semi-induced subgraph, c) is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.

We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on a given structure is considered intractable in general, but it does become tractable on interesting classes of structures, such as on classes whose Gaifman graphs have bounded treewidth. In this article, we continue this line of research and study model-checking for first- and monadic second-order logic in the presence of an ordering on the input structure. We do so in two settings: the general ordered case, where the input structures are equipped with a fixed order or successor relation, and the order-invariant case, where the formulas may resort to an ordering, but their truth must be independent of the particular choice of order. In the first setting we show very strong intractability results for most interesting classes of structures. In contrast, in the order-invariant case we obtain tractability results for order-invariant monadic second-order formulas on the same classes of graphs as in the unordered case. For first-order logic, we obtain tractability of successor-invariant formulas on classes whose Gaifman graphs have bounded expansion. Furthermore, we show that model-checking for order-invariant first-order formulas is tractable on coloured posets of bounded width.

The notions of bounded expansion [Nešetřil and Ossona de Mendez, 2008] and nowhere denseness [Nešetřil and Ossona de Mendez, 2011], introduced by Nešetřil and Ossona de Mendez as structural measures for undirected graphs, have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expansion and nowhere crownfulness on directed graphs, introduced by Kreutzer and Tazari [Kreutzer and Tazari, 2012]. The classes of directed graphs having those properties are very general classes of sparse directed graphs, as they include, on one hand, all classes of directed graphs whose underlying undirected class has bounded expansion, such as planar, bounded-genus, and H-minor-free graphs, and on the other hand, they also contain classes whose underlying undirected class is not even nowhere dense. We show that many of the algorithmic tools that were developed for undirected bounded expansion classes can, with some care, also be applied in their directed counterparts, and thereby we highlight a rich algorithmic structure theory of directed bounded expansion and nowhere crownful classes.

We study the version of the k -disjoint paths problem where k demand pairs ( s 1 , t 1 ) , …, ( s k , t k ) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n O ( d ) if we allow congestion k − d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f ( k ) n o ( d / log ⁡ d ) for any computable function f .

Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness , a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this article, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. A powerful method in parameterized complexity theory is to compute a problem kernel in a pre-computation step, that is, to reduce the input instance in polynomial time to a sub-instance of size bounded in the parameter only (independently of the input graph size). Our new tools allow us to obtain for every fixed radius r ∈ N a polynomial kernel for the distance- r dominating set problem on nowhere dense classes of graphs. This result is particularly interesting, as it implies that for every class C of graphs that is closed under taking subgraphs, the distance- r dominating set problem admits a kernel on C for every value of r if, and only if, it already admits a polynomial kernel for every value of r (under the standard assumption of parameterized complexity theory that FPT ≠ W[2]).

\noindent We provide a new constant factor approximation algorithm for the (connected) \mboxdistance- r dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar graphs and graphs with excluded (topological) minors, and notably, these classes form the most general subgraph closed classes of graphs for which a sequential constant factor approximation algorithm for the distance- r dominating set problem is currently known. Our algorithm can be implemented in the \congestbc model of distributed computing and uses $Øof(r^2 łog n)$ communication rounds. % Our techniques, which may be of independent interest, are based on a distributed computation of sparse neighborhood covers of small radius on bounded expansion classes. We show how to compute an r -neighborhood cover of radius~$2r$ and overlap $f(r)$ on every class of bounded expansion in $Øof(r^2łog n)$ communication rounds for some function~ f .% in the \congestbc model. % Finally, we show how to use the greater power of the łocal model to turn any distance- r dominating set into a constantly larger connected distance- r dominating set in $3r+1$ rounds on any class of bounded expansion. Combining this algorithm, e.g., with the constant factor approximation algorithm for dominating sets on planar graphs of Lenzen et al.\ gives a constant factor approximation algorithm for connected dominating sets on planar graphs in a constant number of rounds in the łocal model, where the approximation ratio is only $6$ times larger than that of Lenzen et al.'s algorithm.

In [M. Grohe, S. Kreutzer, and S. Siebertz, J. ACM, 64 (2017), 17] it was shown that nowhere dense classes of graphs admit sparse neighborhood covers of small degree. We show that a monotone graph class admits sparse neighborhood covers if and only if it is nowhere dense. The existence of such covers for nowhere dense classes is established through bounds on so-called weak coloring numbers. The core results of this paper are various lower and upper bounds on the weak coloring numbers and other, closely related, generalized coloring numbers. We prove tight bounds for these numbers on graphs of bounded treewidth. We clarify and tighten the relation between the density of shallow minors and the various generalized coloring numbers. These upper bounds are complemented by new, stronger exponential lower bounds on the weak and strong coloring numbers, and by superpolynomial lower bounds on the weak coloring numbers on classes of polynomial expansion. Finally, we show that computing weak $r$-coloring numbers is NP-complete for all $r\geq 3$.

We prove that whenever G is a graph from a nowhere dense graph class C, and A is a subset of vertices of G, then the number of subsets of A that are realized as intersections of A with r-neighborhoods of vertices of G is at most f(r,eps)|A|^(1+eps), where r is any positive integer, eps is any positive real, and f is a function that depends only on the class C. This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by [Reidl et al., CoRR, 2016]. As an algorithmic application of the above result, we show that for every fixed integer r, the parameterized Distance-r Dominating Set problem admits an almost linear kernel on any nowhere dense graph class. This proves a conjecture posed by [Drange et al., STACS 2016], and shows that the limit of parameterized tractability of Distance-r Dominating Set on subgraph-closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.

A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the particular interpretation of this relation. It is well known that successor-invariant formulas are more expressive on finite structures than plain first-order formulas without a successor relation. This naturally raises the question whether this increase in expressive power comes at an extra cost to solve the model-checking problem, that is, the problem to decide whether a given structure together with some (and hence every) successor relation is a model of a given formula. It was shown earlier that adding successor-invariance to first-order logic essentially comes at no extra cost for the model-checking problem on classes of finite structures whose underlying Gaifman graph is planar [1], excludes a fixed minor [2] or a fixed topological minor [3], [4]. In this work we show that the model-checking problem for successor-invariant formulas is fixed-parameter tractable on any class of finite structures whose underlying Gaifman graphs form a class of bounded expansion. Our result generalises all earlier results and comes close to the best tractability results on nowhere dense classes of graphs currently known for plain first-order logic.

Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this paper, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. As an algorithmic application of our new methods, we obtain for every fixed value of r ∊ ℕ a polynomial kernel for the distance-r dominating set problem on nowhere dense classes of graphs. This is particularly interesting, as it implies that for every subgraph-closed class C, the distance-r dominating set problem admits a kernel on C for every value of r if, and only if, it admits a polynomial kernel for every value of r (under the standard assumption of parameterized complexity theory that FPT ≠ W[2]). Finally, we demonstrate how to use the new methods to improve the parameter dependence of many fixed- parameter algorithms. As an example we provide a single exponential parameterized algorithm for the Connected Dominating Set problem on nowhere dense graph classes.

Bounded expansion and nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of uniformly sparse graphs which includes the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs. Since their initial definition it was shown that these graph classes can be defined in many equivalent ways: by generalised colouring numbers, neighbourhood complexity, sparse neighbourhood covers, a game known as the splitter game, and many more. We study the corresponding concepts for directed graphs. We show that the densities of bounded depth directed minors and bounded depth topological minors relate in a similar way as in the undirected case. We provide a characterisation of bounded expansion classes by a directed version of the generalised colouring numbers. As an application we show how to construct sparse directed neighbourhood covers and how to approximate directed distance-r dominating sets on classes of bounded expansion. On the other hand, we show that linear neighbourhood complexity does not characterise directed classes of bounded expansion.

The generalised colouring numbers $\mathrm{adm}_r(G)$, $\mathrm{col}_r(G)$, and $\mathrm{wcol}_r(G)$ were introduced by Kierstead and Yang as generalisations of the usual colouring number, also known as the degeneracy of a graph, and have since then found important applications in the theory of bounded expansion and nowhere dense classes of graphs, introduced by Nešetřil and Ossona de Mendez. In this paper, we study the relation of the colouring numbers with two other measures that characterise nowhere dense classes of graphs, namely with uniform quasi-wideness, studied first by Dawar et al. in the context of preservation theorems for first-order logic, and with the splitter game, introduced by Grohe et al. We show that every graph excluding a fixed topological minor admits a universal order, that is, one order witnessing that the colouring numbers are small for every value of $r$. Finally, we use our construction of such orders to give a new proof of a result of Eickmeyer and Kawarabayashi, showing that the model-checking problem for successor-invariant first-order formulas is fixed-parameter tractable on classes of graphs with excluded topological minors.

In cops and robber games a number of cops tries to capture a robber in a graph. A variant of these games on undirected graphs characterises tree width by the least number of cops needed to win. We consider cops and robber games on digraphs and width measures (such as DAG-width, directed tree width or D-width) corresponding to them. All of them generalise tree width and the game characterising it. For the DAG-width game we prove that the problem to decide the minimal number of cops required to capture the robber (which is the same as deciding DAG-width), is PSPACE-complete, in contrast to most other similar games. We also show that the cop-monotonicity cost for directed tree width games cannot be bounded by any function. As a consequence, D-width is not bounded in directed tree width, refuting a conjecture by Safari. A large number of directed width measures generalising tree width has been proposed in the literature. However, only very little was known about the relation between them, in particular about whether classes of digraphs of bounded width in one measure have bounded width in another. In this paper we establish an almost complete order among the most prominent width measures with respect to mutual boundedness.