ABSTRACT. Let $G=(V,E)$ be a graph. A set $D \subseteq V$ is a dominating set if every vertex in $V \setminus D$ has a neighbor in $D$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set. The \emph{bondage number} of a graph $G$ is the minimum number of edges whose removal increases $\gamma(G)$, while the \emph{reinforcement number} is the minimum number of edges whose addition decreases $\gamma(G)$. Hu and Xu initiated the complexity study of the \textsc{Bondage} and \textsc{Reinforcement} problems, establishing NP-hardness for general graphs (J.\ Complexity, 2012). Subsequently, Hu and Sohn strengthened these NP-hardness results for bipartite graphs (Theoret.\ Comput.\ Sci., 2014). The complexity of these problems on chordal graphs has remained unexplored. Hu and Xu asked whether these problems belong to NP and whether they admit polynomial-time approximation algorithms with small performance ratios.\\~ \quad In this paper, we prove that the \textsc{Bondage} and \textsc{Reinforcement} problems are NP-hard and coNP-hard for $k = 1$, even when restricted to split graphs, a well-known subclass of chordal graphs. Consequently, unless $\mathrm{NP} = \mathrm{coNP}$, none of these problems is in NP, answering the first question. Furthermore, these hardness results rule out any polynomial-time approximation algorithm with performance ratio better than~$2$, unless $\mathrm{P} = \mathrm{NP}$, thereby answering second question.

ABSTRACT. A monitoring edge-geodetic set (or meg-set for short) of a graph is a set of vertices M such that if any edge is removed, then the distance between some two vertices of M increases. This notion was introduced by Foucaud et al. in 2023 as a way to monitor networks for communication failures. As computing a minimal meg-set is hard in general, recent works aimed to find polynomial-time algorithms to compute minimal meg-sets when the input belongs to a restricted class of graphs. Most of these results are based on the property of some classes of graphs to admit a unique minimum meg-set, which is then easy to compute. In this work, we prove that chordal graphs also admit a unique minimal meg-set, answering a standing open question of Foucaud et al.

ABSTRACT. The Maximum Matching realization problem requires, for a sequence $d$ of $n$ positive integers, to compute a realizing graph (whose degree sequence corresponds to $d$) with the largest possible matching. We present a polynomial time algorithm for this problem.

ABSTRACT. Vertex splitting is a graph modification operation in which a vertex is replaced by multiple vertices such that the union of their neighborhoods equals the neighborhood of the original vertex. We study vertex splitting as a graph modification operation for transforming graphs into interval graphs. Given a graph G and an integer k, we consider the problem of deciding whether G can be transformed into an interval graph using at most k vertex splits. We prove that this problem is NP-hard. We further observe that vertex splitting differs fundamentally from vertex deletion as a graph modification operation. On the positive side, we identify tractable cases. We give polynomial-time algorithms for transforming graphs into trees using vertex splitting and show that deciding whether a graph can be split into a disjoint union of paths is also solvable in polynomial time.

ABSTRACT. We study a natural generalization of the classical \textsc{Dominating Set} problem, called \textsc{Dominating Set with Quotas} (DSQ). In this problem, we are given a graph \( G \), an integer \( k \), and for each vertex \( v \in V(G) \), a lower quota \( \mathrm{lo}_v \) and an upper quota \( \mathrm{up}_v \). The goal is to determine whether there exists a set \( S \subseteq V(G) \) of size at most \( k \) such that for every vertex \( v \in V(G) \), the number of vertices in its closed neighborhood that belong to \( S \), i.e., \( |N[v] \cap S| \), lies within the range \( [\mathrm{lo}_v, \mathrm{up}_v] \). This richer model captures a variety of practical settings where both under- and over-coverage must be avoided—such as in fault-tolerant infrastructure, load-balanced facility placement, or constrained communication networks.

While DS is already known to be computationally hard, we show that the added expressiveness of per-vertex quotas in DSQ introduces additional algorithmic challenges. In particular, we prove that DSQ becomes \W[1]-hard even on structurally sparse graphs—such as those with degeneracy 2, or excluding \( K_{3,3} \) as a subgraph—despite these classes admitting FPT algorithms for DS. On the positive side, we show that DSQ is fixed-parameter tractable when parameterized by solution size and treewidth, and more generally, on nowhere dense graph classes. Furthermore, we design a subexponential-time algorithm for DSQ on apex-minor-free graphs using the bidimensionality framework. These results collectively offer a refined view of the algorithmic landscape of DSQ, revealing a sharp contrast with the classical DS problem and identifying the key structural properties that govern tractability.

ABSTRACT. In this paper, we study the parameterized complexity of several variants of scheduling with precedence constraints between jobs. Namely, we consider the single machine setting with minimum, maximum or exact delay values on top of the precedence constraints. Such scheduling problems are related to several decades-old problems with open parameterized complexity status, notably Shuffle Product and Directed Bandwidth. We obtain XNLP-completeness results for both problems, and derive implications to scheduling with minimum (resp. maximum) delays parameterized by the width of the directed acyclic graph giving the precedence constraints, and/or by the maximum delay value in the input. Regarding Directed Bandwidth, we also settle the case of trees by showing XNLP-completeness parameterized by the target value. On top of giving an answer to several open questions in the literature, each of independent interest, these results highlight the relevancy of both scheduling and class XNLP in studying the parameterized complexity of computer science problems. In particular, Shuffle Product is an unusual and promising addition to the list of XNLP-complete problems.

ABSTRACT. Given a graph $G = (V, E)$, a signed dominating function is a function $f: V \rightarrow \{-1, 1\}$ such that for every vertex $u \in V$, $\sum\limits_{v \in N[u]} f(v) \geq 1$. The weight of $f$ is defined as $\sum\limits_{u \in V} f(u)$. The objective of the \sd{} problem is to compute a signed dominating function $f$ of minimum weight. The problem is known to be NP-complete even when restricted to bipartite, chordal, and planar graphs. In this paper, we extend the known complexity results for the \sd{} problem. Since the problem is NP-complete on chordal graphs, we study its complexity on split graphs, a subclass of chordal graphs, and show that it remains NP-complete. Moreover, as the problem is W[2]-hard parameterized by weight, we investigate its parameterized complexity with respect to structural parameters. We prove that the problem is W[1]-hard when parameterized by feedback vertex set number (and hence by treewidth and clique-width). Motivated by this hardness result, we consider a more restrictive parameter, neighbourhood diversity, and present an FPT algorithm.