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.

We present and describe the solver OBLX for the Dominating Set problem on graphs. This solver was developed during the PACE challenge 2025 for the Exact track. It first applies several data reduction rules and performs a polynomial time reduction to Max Sat. The resulting Max Sat instance is in turn solved using the EvalMaxSat solver by Florent Avellaneda.

Abstract We study reduction rules for Directed Feedback Vertex Set (DFVS) on directed graphs without long cycles. A DFVS instance without cycles longer than d naturally corresponds to an instance of d -Hitting Set, however, enumerating all cycles in an n-vertex graph and then kernelizing the resulting d -Hitting Set instance can be too costly, as already enumerating all cycles can take time $$\Omega (n^d)$$ Ω ( n d ) . To the best of our knowledge, the kernelization of DFVS on graphs without long cycles has not been studied in the literature, except for very restricted cases, e.g., for tournaments, in which all induced cycles are of length three. We show that the natural reduction rule to delete all vertices and edges that do not lie on induced cycles cannot be implemented efficiently, that is, it is W[1]-hard (with respect to parameter d) to decide if a vertex or edge lies on an induced cycle of length at most d even on graphs that become acyclic after the deletion of a single vertex or edge. Based on different reduction rules we then show how to compute a kernel with at most $$2^dk^d$$ 2 d k d vertices and at most $$d^{3d}k^d$$ d 3 d k d induced cycles of length at most d (which however, cannot be enumerated efficiently), where k is the size of a minimum directed feedback vertex set. We then study classes of graphs whose underlying undirected graphs have bounded expansion or are nowhere dense. These are very general classes of sparse graphs, containing e.g. classes excluding a minor or a topological minor. We prove that for every class $$\mathscr {C} $$ C with bounded expansion there is a function $$f_\mathscr {C} (d)$$ f C ( d ) such that for graphs $$G\in \mathscr {C} $$ G ∈ C without induced cycles of length greater than d we can compute a kernel with $$f_\mathscr {C} (d)\cdot k$$ f C ( d ) · k vertices in time $$f_\mathscr {C} (d)\cdot n^{\mathcal {O}(1)}$$ f C ( d ) · n O ( 1 ) . For every nowhere dense class $$\mathscr {C} $$ C there is a function $$f_\mathscr {C} (d,\varepsilon )$$ f C ( d , ε ) such that for graphs $$G\in \mathscr {C} $$ G ∈ C without induced cycles of length greater than d we can compute a kernel with $$f_\mathscr {C} (d,\varepsilon )\cdot k^{1+\varepsilon }$$ f C ( d , ε ) · k

We present an exact solver for the DFVS, submitted for the exact track of the Parameterized Algorithms and Computational Experiments challenge (PACE) in 2022. The solver heavily relies on data reduction (known from the literature and new reduction rules). The instances are then further processed by integer linear programming approaches. We implemented the algorithm in the scope of a student project at the University of Bremen.