Ignasi Sau

Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza et al.

An elimination tree of a connected graph $G$ is a rooted tree on the vertices of $G$ obtained by choosing a root $v$ and recursing on the connected components of $G-v$ to obtain the subtrees of $v$. The graph associahedron of $G$ is a polytope whose vertices correspond to elimination trees of $G$ and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where $G$ is a path. Ito et al. [ICALP 2023] recently proved that the problem of computing distances on graph associahedra is NP-hard. In this paper we prove that the problem, for a general graph $G$, is fixed-parameter tractable parameterized by the distance $k$. Prior to our work, only the case where $G$ is a path was known to be fixed-parameter tractable. To prove our result, we use a novel approach based on a marking scheme that restricts the search to a set of vertices whose size is bounded by a (large) function of $k$. On the negative side, we show that it is unlikely that FPT algorithms exist on a natural generalization of graph associahedra, namely hypergraphic polytopes, by proving that computing distances on them is W[2]-hard parameterized by the distance. We also prove that, on hypergraphic polytopes, the distance cannot be approximated in polynomial time within a factor $c \cdot \log(|V|+|\mathcal{E}|)$ for some constant $c > 0$ unless P = NP, where $H=(V, \mathcal{E})$ is the input hypergraph. This result strengthens the hardness result of Cardinal and Steiner [Combin. Theory 2025], who proved that the problem cannot be approximated within a factor $(1 + \varepsilon)$ for some absolute constant $\varepsilon > 0$ unless P = NP. Finally, we rule out the existence of polynomial kernels parameterized by the number of vertices of the input hypergraph, a parameter for which the problem is easily seen to be FPT.

Davi de Andrade, Júlio Araújo, Laure Morelle et al.

A good edge-labeling (gel for short) of a graph $G$ is a function $λ: E(G) \to \mathbb{R}$ such that, for any ordered pair of vertices $(x, y)$ of $G$, there do not exist two distinct increasing paths from $x$ to $y$, where ``increasing'' means that the sequence of labels is non-decreasing. This notion was introduced by Bermond et al. [Theor. Comput. Sci. 2013] motivated by practical applications arising from routing and wavelength assignment problems in optical networks. Prompted by the lack of algorithmic results about the problem of deciding whether an input graph admits a gel, called GEL, we initiate its study from the viewpoint of parameterized complexity. We first introduce the natural version of GEL where one wants to use at most $c$ distinct labels, which we call $c$-GEL, and we prove that it is NP-complete for every $c \geq 2$ on very restricted instances. We then provide several positive results, starting with simple polynomial kernels for GEL and $c$-\GEL parameterized by neighborhood diversity or vertex cover. As one of our main technical contributions, we present an FPT algorithm for GEL parameterized by the size of a modulator to a forest of stars, based on a novel approach via a 2-SAT formulation which we believe to be of independent interest. We also present FPT algorithms based on dynamic programming for $c$-GEL parameterized by treewidth and $c$, and for GEL parameterized by treewidth and the maximum degree. Finally, we answer positively a question of Bermond et al. [Theor. Comput. Sci. 2013] by proving the NP-completeness of a problem strongly related to GEL, namely that of deciding whether an input graph admits a so-called UPP-orientation.

Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz et al.

Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions of first-order logic such as FO+dp admit efficient model checking on graph classes excluding a fixed topological minor, comparable results for richer fragments of CMSO were previously unknown. We further develop the framework of Sau, Stamoulis, and Thilikos [SODA 2025] for fragmenting CMSO via annotated graph parameters, which restrict set quantification to vertex sets satisfying bounded structural conditions. Following this approach, we identify a fragment of CMSO, namely the one defined by allowing quantification only over sets having what we call low monodimensionality, that generalizes several previously-known logics and we show that model checking for this fragment, enhanced with the disjoint-paths predicate, is fixed-parameter tractable on topological-minor-free graph classes. Such classes essentially delimit the tractability for this logic on subgraph-closed classes. As a consequence, our results lift several known algorithmic meta-theorems beyond first-order logic to the topological-minor-free setting.

Marin Bougeret, Guilherme C. M. Gomes, Ignasi Sau

Enumerative kernelization is a recent promising at the intersection of parameterized complexity and enumeration algorithms, with two proposed models. The first, known as enum-kernels and due to Creignou et al., was too permissive, leading to constant-sized kernels for every problem solvable with FPT-delay. To remedy this, Golovach et al. proposed the polynomial-delay enumeration kernelization model that, while addressing the shortcoming of the previous one, appears to be too strict, which we believe is a central reason for the slow development of the area. In this paper, we propose a new model for enumeration kernels, which we have called polynomial-delay (PD) kernels. It is more flexible than Golovach et al.'s kernels while still preserving their qualities; informally, it allows us to ignore ``bad'' solutions of the compressed instance when producing the solution set of the input instance, but still requires that the ``good'' solutions are lifted with polynomial-delay. After discussing the main properties of our model, we design a generic framework for vertex-subset problems to adapt decision kernels into PD kernels of the same size. We showcase our model's versatility and the framework's expressive power on the \textsc{Enum Vertex Cover} problem, where we want to list all vertex covers of size at most $k$ of a given graph. We generalize the kernelization dichotomy by Bougeret et al. about the existence of polynomial kernels for \textsc{Vertex Cover} parameterized by the vertex deletion distance to a minor-closed graph class, as well as by the solution size or feedback vertex number. The second one, in particular, is significantly simpler than the known kernel, requiring only a few lines for its lifting algorithm. Beyond our framework, we also show how to generalize to the enumeration setting the kernel of Bougeret et al. for the vertex-deletion distance to $c$-treedepth.