Laminar set systems consist of non-crossing subsets of a universe with set inclusion essentially corresponding to the descendant relationship of a tree, the so-called laminar tree. Laminar set systems lie at the core of many graph decompositions such as modular decompositions, split decompositions, and bi-join decompositions. We show that from a laminar set system we can obtain the corresponding laminar tree by means of a monadic second order logic (MSO) transduction. This resolves an open question originally asked by Courcelle and is a satisfying resolution as MSO is the natural logic for set systems and is sufficient to define the property "laminar". Using results from Campbell et al. [STACS 2025], we can now obtain transductions for obtaining modular decompositions, co-trees, split decompositions and bi-join decompositions using MSO instead of CMSO. We further gain some insight into the expressive power of counting quantifiers and provide some results towards determining when counting quantifiers can be simulated in MSO in laminar set systems and when they cannot.

International audience

International audience

We show that given a graph G we can CMSO-transduce its modular decomposition, its split decomposition and its bi-join decomposition. This improves results by Courcelle [Logical Methods in Computer Science, 2006] who gave such transductions using order-invariant MSO, a strictly more expressive logic than CMSO. Our methods more generally yield C_{2}MSO-transductions of the canonical decomposition of weakly-partitive set systems and weakly-bipartitive systems of bipartitions.

Abstract Given a graph G and an integer b, Bandwidth asks whether there exists a bijection $$\pi $$ π from V(G) to $$\{1, \ldots , |V(G)|\}$$ { 1 , … , | V ( G ) | } such that $$\max _{\{u, v \} \in E(G)} | \pi (u) - \pi (v) | \le b$$ max { u , v } ∈ E ( G ) | π ( u ) - π ( v ) | ≤ b . This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the tree-depth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number. In this paper we make progress in understanding the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number $$\omega $$ ω , thus significantly strengthening the previously mentioned result for vertex cover number. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results develop and generalize some of the methods of argumentation of the previous results and narrow some of the complexity gaps.

Additively Separable Hedonic Game (ASHG) are coalition-formation games where we are given a graph whose vertices represent $n$ selfish agents and the weight of each edge $uv$ denotes how much agent $u$ gains (or loses) when she is placed in the same coalition as agent $v$. We revisit the computational complexity of the well-known notion of core stability of ASHGs, where the goal is to construct a partition of the agents into coalitions such that no group of agents would prefer to diverge from the given partition and form a new (blocking) coalition. Since both finding a core stable partition and verifying that a given partition is core stable are intractable problems ($Σ_2^p$-complete and coNP-complete respectively) we study their complexity from the point of view of structural parameterized complexity, using standard graph-theoretic parameters, such as treewidth.

Abstract. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix [Formula: see text] is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix [Formula: see text] that is not testable. In the dense graph model, a similar picture has long been known [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451–476] despite the very different nature of the two models. In particular, we obtain our lower bound by an FO formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then use our class of FO definable bounded-degree expanders to answer a long-standing open problem for proximity-oblivious testers (POTs). POTs are a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on the proximity parameter, but the basic test itself is independent of the proximity parameter. In their seminal work, Goldreich and Ron [STOC 2009; SIAM J. Comput., 40 (2011), pp. 534–566] show that the graph properties that are constant-query proximity-oblivious testable in the bounded-degree model are precisely the properties that can be expressed as a generalized subgraph freeness (GSF) property that satisfies the non-propagation condition. It is left open whether the non-propagation condition is necessary. Indeed, calling properties expressible as a generalized subgraph freeness property GSF-local properties, they ask whether all GSF-local properties are non-propagating. We give a negative answer by showing that our FO definable property is GSF-local and propagating. Hence, in particular, our property does not admit a POT, despite being GSF-local. For this result we establish a new connection between FO properties and GSF-local properties via neighborhood profiles.

Abstract. A homomorphism [Formula: see text] from a guest graph [Formula: see text] to a host graph [Formula: see text] is locally bijective, injective, or surjective if for every [Formula: see text], the restriction of [Formula: see text] to the neighbourhood of [Formula: see text] is bijective, injective, or surjective, respectively. We prove a number of new FPT (fixed-parameter tractable), W [1]-hard, and paraNP -complete results for the corresponding decision problems LBHom, LIHom, and LSHom by considering a hierarchy of parameters of the guest graph [Formula: see text]. In this way we strengthen several existing results. For our FPT results, we develop a new algorithmic framework that involves a general ILP (integer linear program) model. We also use our framework to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms.

Given a graph G and an integer b, Bandwidth asks whether there exists a bijection π from V(G) to {1, …, |V(G)|} such that max_{{u, v} ∈ E(G)} | π(u) - π(v) | ≤ b. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number ω of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps.

We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that K_{t,t}-free segment graphs, and axis-parallel H_t-free unit segment graphs have bounded twin-width, where H_t is the half-graph or ladder of height t. In contrast, axis-parallel H₄-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM '22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) ⋅ |V(G)|^O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.

In Property Testing, proximity-oblivious testers (POTs) form a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on the proximity parameter, but the basic test itself is independent of the proximity parameter. In their seminal work, Goldreich and Ron [STOC 2009; SICOMP 2011] show that the graph properties that allow constant-query proximity-oblivious testing in the bounded-degree model are precisely the properties that can be expressed as a generalised subgraph freeness (GSF) property that satisfies the non-propagation condition. It is left open whether the non-propagation condition is necessary. Indeed, calling properties expressible as a generalised subgraph freeness property GSF-local properties, they ask whether all GSF-local properties are non-propagating. We give a negative answer by exhibiting a property of graphs that is GSF-local and propagating. Hence in particular, our property does not admit a POT, despite being GSF-local. We prove our result by exploiting a recent work of the authors which constructed a first-order (FO) property that is not testable [SODA 2021], and a new connection between FO properties and GSF-local properties via neighbourhood profiles.

We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix ∃∗∀∗ is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix ∀∗∃∗ that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then prove testability of some first-order properties that speak about isomorphism types of neighbourhoods, including testability of 1-neighbourhood-freeness, and r-neighbourhood-freeness under a mild assumption on the degrees.