ABSTRACT. We present an algorithm for the efficient generation of all pairwise non-isomorphic cycle permutation graphs, i.e. cubic graphs with a 2-factor consisting of two chordless cycles, and non-hamiltonian cycle permutation graphs, from which the permutation snarks can easily be computed. This allows us to generate all cycle permutation graphs up to order 34 and all permutation snarks up to order 46, improving upon previous computational results by Brinkmann et al. Moreover, we give several improved lower bounds for interesting permutation snarks, such as for a smallest permutation snark of order 6 mod 8 or a smallest permutation snark of girth at least 6. These computational results also allow us to complete a characterisation of the orders for which non-hamiltonian cycle permutation graphs exist, answering an open question by Klee from 1972, and yield many more counterexamples to a conjecture by Zhang.

ABSTRACT. Schnyder woods proved to be a tool of great benefit for the study of planar graphs. We investigate a new structural property of Schnyder woods: every minimal Schnyder wood of a 3-connected planar graph of order $n$ has a tree of depth at least 1/(3log_2(3)) log_2(n). This bound is tight. Our result directly implies that such a graph has an induced path of length at least 1/(3log_2(3)) log_2(n), improving the previous best lower bound on the length of such a path.

ABSTRACT. The H-Induced Minor Containment problem (H-IMC) consists in deciding if a fixed graph H is an induced minor of a graph G given as input, that is, if H can be obtained from G by deleting vertices and contracting edges. Several graphs H are known so that H-IMC is NP-complete, and even when H is a tree. In this paper, we investigate which conditions on H and G are sufficient so that the problem becomes polynomial-time solvable. Our results identify three infinite classes of graphs such that, if H belongs to such a class, then H-IMC can be solved in polynomial time. Moreover, we show that if the input graph G excludes long induced paths, then H-IMC is polynomial-time solvable, for any fixed graph H. As a byproduct of our results, this shows that H-IMC is polynomial-time solvable for all graphs H with at most 5 vertices, except for three open cases.

ABSTRACT. Graph orientation transforms an undirected graph into a directed graph by assigning a direction to each edge. Among the many different optimization problems related to graph orientations, we focus here on the Shortest Longest-Path Orientation problem (SLPO) which is a generalization of the well-known Minimum Graph Coloring problem. The input to SLPO is an edge-bi-weighted undirected graph in which every edge has two (possibly different and not necessarily positive) lengths associated with its two directions. The goal is to find an orientation of the input graph that minimizes the length of the longest simple directed path. Recently, polynomial-time algorithms for simple graph structures such as paths, cycles, stars, and trees were proposed, and a new polynomial-time inapproximability result was also established. This paper presents (i) an $O(n^2 \log n)$-time algorithm for trees, which is a significant improvement over the previously fastest algorithm whose time complexity was $\Omega(n^{14})$ and (ii) polynomial-time algorithms for trees and spiders that run even faster than (i) as long as every edge weight is an integer and the total weight of the edges is sub-exponential.

ABSTRACT. The Orienteering Problem is a well-researched routing problem: A person wants to travel at most some distance B while maximising the total profit collected by visiting sites. In the version with time windows, the profit of a site can only be collected within a certain time window. While the Orienteering Problem and thus the version with time windows are NP-hard in general, it remains open on numerous special graph classes. Since in several applications, especially for planning a route from A to B with waypoints, the input graph can be restricted to tree-like or path-like structures, in this paper we consider Orienteering on these graph classes.

While the Orienteering Problem with time windows is NP-hard even on undireced paths and cycles, and remains so even if all profits must be collected, we show that for directed paths it can be solved in O(m log m) time (where m is the total number of time windows), even if each profit can be collected in one of several time windows. The same case is shown to be NP-hard for directed cycles.

Particularly interesting is the Orienteering Problem on a directed cycle with one time window per profit. We give an efficient algorithm for the case where all time windows are shorter than the length of the cycle, resulting in a 2-approximation for the general setting. Based on the algorithm for directed paths, we further develop a polynomial-time approximation scheme for this problem. For the case where all profits must to be collected, we present an O(n⁴)-time algorithm.

For the Orienteering Problem with time windows for the edges, we give a quadratic time algorithm for undirected paths and observe that the problem is NP-hard for trees.

In the variant without time windows, we show that on trees and thus on graphs with bounded tree-width the Orienteering Problem remains NP-hard. We present, however, an FPT algorithm to solve Orienteering with unit profits that we then use to obtain a 1+ε-approximation algorithm on graphs with arbitrary profits and bounded tree-width, which improves current results on general graphs.

ABSTRACT. In this paper, we investigate the problem of \textsc{Defective Coloring}. Given a graph $G$, two positive integers $k$ and $\d$, the objective is to determine whether it is possible to color the vertices of $G$ using at most $k$ colors such that each vertex in a color class $c$ has at most $\d$ neighbors in the same color class. \textsc{Defective Coloring} is a more general problem than \textsc{Graph Coloring}, where $\d=0$. As a result, any hardness results for \textsc{Graph Coloring} are applicable to \textsc{Defective Coloring}. The optimization variant of this problem, which aims to find the minimum number of colors $k$, is known to be {\sf NP}-hard even for split graphs and cographs.

Belmonte, Lampis, and Mitsou (SIDMA 2020) demonstrated that the problem \dc~is {\sf W[1]}-hard when parameterized by treewidth, pathwidth, tree-depth, or feedback vertex set. Considering that the optimization version of the problem is {\sf NP}-hard on cographs, it can be concluded that the existence of an $\FPT$ algorithm parameterized by modular-width or clique-width is not possible. The authors posed an open question regarding whether \dc~is $\FPT$ when parameterized by modular-width, clique-width, or neighborhood diversity combined with either $k$ or $\d$. In an effort to address the question concerning modular-width, this study investigates the parameters neighborhood diversity and twin-cover, which are special cases of modular-width. The study demonstrates that \dc~is $\FPT$ when parameterized by twin-cover, distance to disjoint paths, or the combined parameters neighborhood diversity and $k$. This provides a partial response to an open question raised in the previous paper. Furthermore, the study also presents a $1$-additive approximation algorithm for split graphs.

ABSTRACT. The objective of this article is to propose two natural generalizations of covering edges by edges (Edge Dominating Set) and study these problems from the multivariate lens. The first is simply considering Edge Dominating Set on hypergraphs, called Hyperedge Dominating Set. Given a hypergraph ${\cal H}=( \mathcal U,{\cal F})$, a set $F \subseteq {\cal F}$ is called a hyperedge dominating set if all hyperedges intersect with at least one hyperedge $e \in F$. The objective of the Hyperedge Dominating Set problem is to determine whether a hyperedge dominating set of size at most $k$ exists. We find it quite surprising that such generalization is missing from the literature. The second extension we consider is the $t$-Path Edge Dominating Set problem. In this problem, the input consists of a graph $G$ and an integer $k$, and the goal is to find a set ${\cal P}$ of at most $k$ paths, each of length at most $t$, such that for every edge in $G$, at least one of its endpoints belongs to the vertex set $V(P)$ for some $P \in {\cal P}$. We show the following results and add to the literature on Edge Dominating Set.

1. Hyperedge Dominating Set is FPT parameterized by $k+d$, where $d$ is the maximum size of a hyperedge in the input hypergraph. 2. A kernel of size $\mathcal{O}(k^d)$ can be obtained for the Hyperedge Dominating Set problem, where $d$ is the maximum size of a hyperedge in the input hypergraph. 3. The problem of finding a Hyperedge Dominating Set is computationally difficult; specifically it is W[2]-hard when parameterized by $k$. This hardness result holds even when each vertex is contained in at most $2$ hyperedges and the intersection between any two hyperedges is at most $1$. 4. $t$-Path Edge Dominating Set is FPT when parameterized by $k+t$. Additionally, it has a kernel of size $\mathcal{O}(k^3t^3)$.

ABSTRACT. For a positive integer $s$, an $s$-club in a graph is a set of vertices inducing a subgraph with diameter at most $s$. As generalizations of cliques, $s$-clubs offer a flexible model for real-world networks. This paper addresses the problems of partitioning and covering vertices with $s$-clubs on bipartite graphs. First we prove that for bipartite graphs and any fixed $s \geq 3$ and $k \geq 3$, determining whether the vertices of $G$ can be partitioned into at most $k$ disjoint $s$-clubs is NP-complete. Note that our NP-completeness result is stronger than the one in \cite{Abbas1999} as we assume that both $s$ and $k$ are constants and not part of the input.

Additionally, we study the Maximum Disjoint $(t,s)$-Club Covering problem (MAX-DCC($t,s$)), which aims to find a collection of vertex-disjoint $(t,s)$-clubs (i.e. $s$-clubs with at least $t$ vertices) that covers the maximum number of vertices in $G$. We prove that it is NP-hard to achieve an approximation factor of $\frac{95}{94} $ for MAX-DCC($t,3$) for any fixed $t\geq 8$ also for bipartite graphs. Previously, results were known only for $t=3$ and $s=2$ \cite{Dondi2019}. Finally, we provide a polynomial-time algorithm for MAX-DCC($2,2$) resolving an open problem from \cite{Dondi2019}.

ABSTRACT. Roman domination is one of few examples where the related extension problem is polynomial-time solvable even if the original decision problem is \NP-complete. This is interesting as it allows to establish polynomial-delay enumeration algorithms for finding minimal Roman dominating functions, while it is open for more than four decades if all minimal dominating sets can be enumerated efficiently. To find the reason why this is the case, we combine the idea of hitting set with the idea of Roman domination. We hence obtain a new combinatorial problem, called \textsc{Roman Hitting Set}, generalizing \textsc{Roman Domination} in a natural way. This allows us to expand the frontier of polynomial-delay enumerability, as opposed to transversal-hardness. The generalization \textsc{Roman Hitting Set} is insofar interesting as it always allows for polynomial-delay enumeration, and we also give an explicit input-sensitive enumeration algorithm for this problem that is optimal in the sense that we can also give a matching lower bound. Based on \textsc{Roman Hitting Set}, we also discuss consequences for Roman variants of \textsc{Vertex Cover} and \textsc{Feedback Vertex Set}. For minimal Roman vertex covers of size upper-bounded by~$k$, we can also deduce an optimal parameterized enumeration algorithm. Also viewed from Parameterized Complexity, the studies on extension problems are interesting, giving more examples of parameterized problems complete for \W{3}. Finally, we also consider implicitly given hypergraphs and prove that, for the example of \textsc{Roman FVS}, our polynomial-delay enumeration algorithm can still be used, avoiding an explicit construction of the hypergraph.

ABSTRACT. In this paper, we study a variant of \textsc{Domination} called \textsc{Minimum membership dominating set}, in short \mmds. The input to the problem is a graph $G$ and an integer $k$ (which is the membership parameter). The goal is to compute a set $S\subseteq V(G)$ such that for each $v\in V(G)$, $1\leq |N[v]\cap S|\leq k$. Such a set $S$ is called a \emph{minimum membership dominating set}. Notice that there is no requirement on the size of $S$.

\begin{itemize} \item A Agrawal et al. (Algorithmica 2023) showed that \mmds is W[1]-hard parameterized by pathwidth of the input graph. They asked as open questions if \mmds is \fpt when parameterized by maximum degree, distance to bounded degree graphs or maximum number of leaves in a spanning tree. We show that \mmds is {\sf NP}-hard even on graphs with maximum degree $\Delta\geq 3$. This provides an answer for the first two parameters. We then consider distance to disjoint paths, a generalization of the maximum number of leaves in a spanning tree and show that the problem is \fpt.

\item They also showed that \mmds is W[2]-hard when parameterized by $k$. As an open question, they asked the complexity of \mmds on subclasses of chordal graphs.

Towards this, we show that membership of an interval graph is at most three. We show that \mmds admits an $k^{O({\sf bw})}n^{O(1)}$ time algorithm where ${\sf bw}$ represents the boolean width of $G$. Since interval graphs have logarithmic boolean width, we obtain a polynomial time algorithm for interval graphs.

\item Recently Sangam et al. (unpublished 2024) showed that \mmds is \fpt parameterized by the combined parameters distance to cluster and membership. However the running time of the algorithm is triple exponential. We show that the problem is single exponential \fpt algorithm parameterized by distance to cluster alone.

\item We show that \mmds can be solved in time $k^{O({\sf cw})}n^{O(1)}$ where $\sf cw$ is the cliquewidth of the input graph. This implies a polynomial time algorithm on graphs of bounded cliquewidth. In particular, as distance hereditary graphs have cliquewidth at most three, the above result implies a polynomial time algorithm., thereby resolving an open question asked by Sangam et al. in the above paper.

\end{itemize}

ABSTRACT. The {\sc Feedback Vertex Set} ({\sc FVS}) problem, together with several of its variants, is arguably one of the most well-studied problems in the field of Parameterized Complexity. Two versions of the problem that have garnered significant interest involve the inclusion of an independence constraint and a connectivity constraint in the solution. This paper introduces generalized versions of both these variants, known as {\sc At least-$c$-FVS} and {\sc At most-$c$-FVS}, respectively, serving as extensions of {\sc Connected FVS} and {\sc Independent FVS}, respectively. The problem {\sc At most-$c$-FVS} (resp., {\sc At least-$c$-FVS}) is defined as follows: given a graph $G$ and an integer $k$, the objective is to determine whether there exists a subset $S \subseteq V(G)$, with $|S| \leq k$, such that the subgraph $G-S$ is a forest and each component of $G[S]$ contains at most $c$ (resp., at least $c$) vertices. We study these problems in the realm of Parameterized Complexity and obtain the following results $\colon$

\begin{itemize}

\item {\sc At most-$c$-FVS} parameterized by $k$ has a kernel of size $\mathcal{O}(k^{3+c})$, and admits an \fpt~algorithm running in time $ 2^{\mathcal{O}(k) +c \cdot \log (k^2)} \cdot n^{\OO(1)}$.

\item {\sc At least-$c$-FVS} parameterized by $k$ has no kernel of size $k^{f(c)}$ for any computable function $f$ (unless \copnpnp), but admits an \fpt~algorithm running in time $2^{\mathcal{O}(k)}\cdot n^{\OO(1)}$.

\end{itemize}

ABSTRACT. The k-rainbow domination problem is a well-known variation of the classical domination problem in graph theory. Motivated by applications in facility location problems, we study colorful k-rainbow domination, a variant of rainbow domination, where at least one color must be assigned to each vertex. Given a graph G=(V,E) and a set of k colors {1, ... , k} we consider a function f that assigns a subset of colors to each vertex, that is f: V → 2^{1, ... , k}. If for each vertex v we have \cup_{x \in N[v]} f(x) = {1, ... , k} and f(v) is not equal to emptyset, then f is a colorful k-rainbow dominating function of G. The weight of f is w(f) = \sum_{v \in V} |f(v)|. The goal of the colorful k-rainbow domination problem is to find a colorful k-rainbow dominating function with the smallest weight. Such weight is called a colorful k-rainbow domination number. For k=2, we give a linear time algorithm that computes an optimal function. For k≥3, we show that the corresponding decision problem is NP-complete. Moreover, for k=3, it remains NP-complete if the input graph is restricted to be split or bipartite. Furthermore, we compute the colorful 3-rainbow domination number for cliques, bicliques, cycles, and paths. For trees and interval graphs, we give linear time algorithms that compute an optimal function.