We define the family of Maya-Tupi graphs as those graphs that admit a partition ( A, B) of their vertex sets such that A induces a complete multipartite graph where each part has size at most two, and B induces a graph where every connected component is K 1 or K 2 . The family of Maya-Tupi graphs is self complementary, generalizes split graphs, falls into the sparse-dense partitioning schema and is characterized by finitely many forbidden induced subgraphs. Unfortunately, our computational experiments show that the number of minimal forbidden induced subgraphs to characterize Maya-Tupi graphs is greater than 2000. In this work, we study Maya-Tupi graphs when restricted to some well-known graph classes. We find characterizations in terms of minimal forbidden induced subgraphs for disconnected graphs, trees and cographs; our results imply linear time certifying recognition algorithms for Maya-Tupi graphs within these classes. We also show that Maya-Tupi graphs can be recognized in O( n 3 )-time in C 4 -free graphs and in graphs with bounded neighborhood diversity.

A proper k -colouring of a graph G = (V, E) is a function c : V(G) → {1,..., k} such that c(u) ≠ c(v) for every edge uv ∈ E(G). The chromatic number χ(G) is the minimum k such that there exists a proper k -colouring of G. Given a spanning subgraph H of G , a q-backbone k -colouring of (G,H) is a proper k -colouring c of G such that | c(u) - c(v) | ≥ q for every edge uv ∈ E(H). The q -backbone chromatic number BBC q (G, H) is the smallest k for which there exists a q -backbone k-colouring of (G,H). In their seminal paper, Broersma et al. [12] ask whether, for any chordal graph G and any spanning forest H of G , we have that BBC 2 ( G, H) ≤ χ( G ) + O( 1) . In this work, we first show that this is true as long as H is bipartite and G is an interval graph in which each vertex belongs to at most two maximal cliques. We then show that this does not extend to bipartite graphs as backbone by exhibiting a family of chordal graphs G with spanning bipartite subgraphs H satisfying BBC 2 (G,H)≥5χ(G)/3. Then, we show that if G is chordal and H has bounded maximum average degree (in particular, if H is a forest), then BBC 2 (G,H)≤χ(G) + O(√χ(G)). We finally show that BBC 2 (G,H) ≤ 3/2χ(G) + O(1) holds whenever G is chordal and H is C 4 -free.

An orientation D of a graph G is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation D of a graph G is a k-orientation if the in-degree of each vertex in D is at most k. An orientation D of G is proper if any two adjacent vertices have different in-degrees in D. The proper orientation number of a graph G, denoted by →χ (G), is the minimum k such that G has a proper k-orientation. A weighted orientation of a graph G is a pair (D, w), where D is an orientation of G and w is an arc-weighting A(D) → N \ {0}. A semi-proper orientation of G is a weighted orientation (D, w) of G such that for every two adjacent vertices u and v in G, we have that S(d,w)(v) ≠ S(d,w)(u), where S(d,w)(v) is the sum of the weights of the arcs in (D, w) with head v. For a positive integer k, a semi-proper k-orientation (D, w) of a graph G is a semi-proper orientation of G such that maxvϵV(G) S(d,w)(v) ≤ k. The semi-proper orientation number of a graph G, denoted by →χs(G), is the least k such that G has a semi-proper k-orientation. In this work, we first prove that →χs(G) ϵ {ω(G) - 1, ω(G)} for every split graph G, and that, given a split graph G, deciding whether →χs(G) = ω(G) - 1 is an NP-complete problem. We also show that, for every k, there exists a (chordal) graph G and a split subgraph H of G such that →χ(G) ≤ k and →χ(H) = 2k - 2. In the sequel, we show that, for every n ≥ p(p + 1), →χs(Ppn) = [3/2 p], where Ppn is the pth power of the path on n vertices. We investigate further unit interval graphs with no big clique: we show that →χ(G) ≤ 3 for any unit interval graph G with ω(G) = 3, and present a complete characterization of unit interval graphs with →χ(G)= ω(G) = 3. Then, we show that deciding whether →χs(G) = ω(G) can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing →χs(G) is FPT when parameterized by the minimum size of a vertex cover in G or by the treewidth of G. We also prove that not only computing →χs(G) but also →χ(G), admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size 40(k2) and 0(2kk2), in chordal graphs and split graphs, respectively, for the problem of deciding whether →χs(G) ≤ k parameterized by k. We also present exponential kernels for computing both →χ(G) and →χs(G) parameterized by the value of the solution when G is a cograph. On the other hand, we show that computing →χs(G) does not admit a polynomial kernel parameterized by the value of the solution when G is a chordal graph, unless NP ⊆ coNP/poly.

In this work, for a given oriented graph D, we study its interval and hull numbers, denoted by ⃗in (D) and ⃗hn (D), respectively, in the oriented geodetic, ⃗P3 and ⃗P*3 convexities. This last one, we believe to be formally defined and first studied in this paper, although its undirected version is well-known in the literature. Concerning bounds, for a strongly oriented graph D and the oriented geodetic convexity, we prove that ⃗hn g(D) ≤ m(D)-n(D) + 2 and that there is at least one such that ⃗hn g(D) = m(D) - n(D). We also determine exact values for the hull numbers in these three convexities for tournaments, which imply polynomial-time algorithms to compute them. These results allow us to deduce polynomial-time algorithms to compute ⃗hn P3 (D) when the underlying graph of D is split or cobipartite. Moreover, we provide a meta-theorem by proving that if deciding whether ⃗ing(D) ≤ k or ⃗hn g(D) ≤ k is NP-hard or W[i]-hard parameterized by k, for some i ϵ Z*+, then the same holds even if the underlying graph of D is bipartite. Next, we prove that deciding whether ⃗hn P3 (D) ≤ k or ⃗hn P3* (D) ≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is bipartite; that deciding whether ⃗in P3(D) ≤ k or whether ⃗in P3*(D) ≤ k is NP-complete, and the same for ⃗hn P3*(D) ≤ k even if D has no directed cycles and the underlying graph of D is a chordal bipartite graph; and that deciding whether ⃗in P3(D) ≤ k or whether ⃗in P3*(D) ≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is split. Finally, we also argue that the interval and hull numbers in the ⃗P3 and ⃗P*3 convexities can be computed in polynomial time for directed graphs with underlying graph of bounded tree-width by using Courcelle's theorem.

In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain lower bounds on the degrees of a certain type of polynomial kernels for vertex-optimization problems, which we call {lop-kernels}. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. On the positive side, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP / poly. This indicates that parameters smaller than the solution size are unlike to yield polynomial kernels for MMVC.

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.

In order to optimize energy efficiency, network operators try to switch off as many network devices as possible. Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing network congestion. In this work, we study the impact of using in-network caches and content delivery network (CDN) cooperation on an energy efficient routing. We formulate this problem as Energy Efficient Content Distribution; we propose an integer linear program and a heuristic algorithm to solve it. The objective of this problem is to find a feasible routing, so that the total energy consumption of the network is minimized while the constraints given by the demands and the link capacity are satisfied. We exhibit for which range of parameters (size of caches, popularity of content, demand intensity, etc.) it is useful to use caches. Experimental results show that by placing a cache on each backbone router to store the most popular content, along with choosing well the best content provider server for each demand to a CDN, we can save about 20% of power on average in all the backbone networks considered.

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu (1997) defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. Max Coloring Problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes, in particular, there exists a PTAS for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The Exponential Time Hypothesis (ETH) states that 3-SAT cannot be solved in sub-exponential time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n O(log(n)). Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components.

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu defined the weighted chromatic number of a vertex-weighted graph $G$ as the smallest weight of a proper coloring of $G$. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. the max coloring problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes; in particular, there exists a polynomial-time approximation scheme for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The exponential time hypothesis (ETH) states that 3-SAT cannot be solved in subexponential time. We show that, assuming the ETH, the best algorithm to compute the weighted chromatic number of $n$-node trees has time-complexity $n^{\Theta(\log n)}$. Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph $G$, it is hard to combine colorings of its connected components.

To optimize energy efficiency in network, operators try to switch off as many network devices as possible. Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing network congestion. In this work, we study the impact of using in-network caches and content delivery network (CDN) cooperation on an energy-efficient routing. We formulate this problem as Energy Efficient Content Distribution. The objective is to find a feasible routing, so that the total energy consumption of the network is minimized subject to satisfying all the demands and link capacity. We exhibit the range of parameters (size of caches, popularity of content, demand intensity, etc.) for which caches are useful. Experimental results show that by placing a cache on each backbone router to store the most popular content, along with well choosing the best content provider server for each demand to a CDN, we can save a total up to 23% of power in the backbone, while 16% can be gained solely thanks to caches.