Temporal graphs are graphs that evolve over time. Many problems which are polynomial-time solvable in standard graphs become NP -hard when appropriately defined in the realm of temporal graphs. This suggested the definition of several parameters for temporal graphs and to prove the fixed-parameter tractability of several problems with respect to these parameters. In this paper, we introduce a hierarchy of parameters based on the previously defined interval membership width and on the temporal evolution of the connected components of the underlying static graph. We then show that the Eulerian trail problem and the temporal 2-coloring problem are both fixed-parameter tractable (in short, FPT ) with respect to any of the parameters in the hierarchy. We also introduce a vertex-variant of the parameters and we show that the firefighter problem (which was known to be FPT with respect to the vertex-variant of the interval membership width) is also FPT with respect to one of the parameters in the second level of the hierarchy.

Abstract Chordal graphs are the intersection graphs of subtrees of a tree, while interval graphs of subpaths of a path. Undirected path graphs, directed path graphs and rooted directed path graphs are intermediate graph classes, defined, respectively, as the intersection graphs of paths of a tree, of directed paths of an oriented tree, and of directed paths of an out branching. All of these path graphs have vertex leafage 2. Dominating Set, Connected Dominating Set, and Steiner tree problems are ‐hard parameterized by the size of the solution on chordal graphs, ‐complete on undirected path graphs, and polynomial‐time solvable on rooted directed path graphs, and hence also on interval graphs. We further investigate the (parameterized) complexity of all these problems when constrained to chordal graphs, taking the vertex leafage and the aforementioned classes into consideration. We prove that Dominating Set, Connected Dominating Set, and Steiner tree are on chordal graphs when parameterized by the size of the solution plus the vertex leafage, and that Weighted Connected Dominating Set is polynomial‐time solvable on strongly chordal graphs. We also introduce a new subclass of undirected path graphs, which we call in–out rooted directed path graphs, as the intersection graphs of directed paths of an in–out branching. We prove that Dominating Set, Connected Dominating Set, and Steiner tree are solvable in polynomial time on this class, generalizing the polynomiality for rooted directed path graphs proved by Booth and Johnson (SIAM J. Comput. 11 (1982), 191‐199.) and by White et al. (Networks 15 (1985), 109‐124.).

Abstract An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph G at least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph $$\varvec{(G,\lambda )}$$ ( G , λ ) , with $$\varvec{\lambda : E(G)}\varvec{\rightarrow } \varvec{2}^{\varvec{[\tau ]}}$$ λ : E ( G ) → 2 [ τ ] , an edge $$\varvec{e}\varvec{\in } \varvec{E(G)}$$ e ∈ E ( G ) is available only at the times specified by $$\varvec{\lambda (e)}\varvec{\subseteq } \varvec{[\tau ]}$$ λ ( e ) ⊆ [ τ ] , in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether $$\varvec{(G,\lambda )}$$ ( G , λ ) has a temporal walk or trail is polynomial, while deciding whether it has a local trail is $$\varvec{\texttt {NP}}$$ NP -complete even if $$\varvec{\tau = 2}$$ τ = 2 . In contrast, in the general case, solving any of these problems is $$\varvec{\texttt {NP}}$$ NP -complete, even under very strict hypotheses. We finally give $$\varvec{\texttt {XP}}$$ XP algorithms parametrized by $$\varvec{\tau }$$ τ for walks, and by $$\varvec{\tau +tw(G)}$$ τ + t w ( G ) for trails and local trails, where $$\varvec{tw(G)}$$ t w ( G ) refers to the treewidth of $$\varvec{G}$$ G .

Given a graph G, a properk-coloring of G is a partition $$c = (S_i)_{i\in [1,k]}$$ of V(G) into k stable sets $$S_1,\ldots , S_{k}$$ . Given a weight function $$w: V(G) \rightarrow {\mathbb {R}}^+$$ , the weight of a color $$S_i$$ is defined as $$w(i) = \max _{v \in S_i} w(v)$$ and the weight of a coloringc as $$w(c) = \sum _{i=1}^{k}w(i)$$ . Guan and Zhu (Inf Process Lett 61(2):77–81, 1997) defined the weighted chromatic number of a pair (G, w), denoted by $$\sigma (G,w)$$ , as the minimum weight of a proper coloring of G. The problem of determining $$\sigma (G,w)$$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time $$n^{o(\log n)}$$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is $$\sigma (G,w) \le \sum _{v \in V(G)} w(v) - k$$ ? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50–61, 2016), who provided an FPT algorithm running in time $$2^{{\mathcal {O}}(k \log k)} \cdot n^{{\mathcal {O}}(1)}$$ , and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time $$9^k \cdot n^{{\mathcal {O}}(1)}$$ , and prove that no algorithm in time $$2^{o(k)} \cdot n^{{\mathcal {O}}(1)}$$ exists under the ETH. On the other hand, we present a kernel with at most $$(2^{k-1}+1) (k-1)$$ vertices, and rule out the existence of polynomial kernels unless $$\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}$$ , even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

For two positive integers k and $$\ell $$ ℓ , a $$(k \times \ell )$$ ( k × ℓ ) -spindle is the union of k pairwise internally vertex-disjoint directed paths with $$\ell $$ ℓ arcs each between two vertices u and v. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed $$\ell \ge 1$$ ℓ ≥ 1 , finding the largest k such that an input digraph G contains a subdivision of a $$(k \times \ell )$$ ( k × ℓ ) -spindle is polynomial-time solvable if $$\ell \le 3$$ ℓ ≤ 3 , and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. Given a weight function $w: V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $\sigma(G,w)$, as the minimum weight of a proper coloring of $G$. The problem of determining $\sigma(G,w)$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on $n$-vertex trees in time $n^{o(\log n)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. In this article we provide some positive results for the problem, by considering its so-called dual parameterization: given a vertex-weighted graph $(G,w)$ and an integer $k$, the question is whether $\sigma(G,w) \leq \sum_{v \in V(G)} w(v) - k$. We prove that this problem is FPT by providing an algorithm running in time $9^k \cdot n^{O(1)}$, and it is easy to see that no algorithm in time $2^{o(k)} \cdot n^{O(1)}$ exists under the ETH. On the other hand, we present a kernel with at most $(2^{k-1}+1) (k-1)$ vertices, and we rule out the existence of polynomial kernels unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.