Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by $k$ shortest paths has pathwidth at most $O(3^k)$. In this paper, we improve this upper bound on the pathwidth to a polynomial one; namely, we show that every graph whose edge set can be covered by $k$ shortest paths has pathwidth $O(k^4)$, answering a question from the same paper. Moreover, we prove that when $k\leq 3$, every such graph has pathwidth at most $k$ (and this bound is tight). Finally, we show that even though there exist graphs with arbitrarily large treewidth whose vertex set can be covered by $2$ isometric trees, every graph whose set of edges can be covered by $2$ isometric trees has treewidth at most $2$.

We introduce a new graph sparsification method that targets the neighborhood information available for each node. Our approach is motivated by the fact that neighborhood information is used by several mining and learning tasks on graphs as well as reachability queries. The result of our sparsification technique is a sparsified graph that can be used instead of the original graph in the above tasks while still ensuring fairly good approximations for the results. Moreover, our sparsification method allows users to control the size of the resulting sparsified graph by adjusting the amount of information loss tolerated by the targeted applications. Our extensive experiments conducted on various real and synthetic graphs show that our sparsification considerably reduces the size of the graphs by achieving 40% sparsification rate on average on several input graphs. Furthermore, in the experimental study we show the utility and efficiency of our sparsification algorithm for notable data-driven tasks, such as node classification, graph classification and shortest path approximations.

We introduce the γ -clustering problems, which are variants of the well-known Cluster Editing/Deletion/Completion problems, and defined as: given a graph G , how many edges must be edited in G , deleted from G , or added to G in order to have a disjoint union of γ -quasi-cliques. We provide here the complete complexity classification of these problems along with FPT algorithms parameterized by the number of modifications, for the NP -complete problems. We also study here a variant of these problems where the number of final clusters is a fixed constant, obtaining mostly the same results regarding classical and parameterized complexity.

The building deconstruction field is one of the main generators of waste. Although recovery techniques exist to valorize this waste, most of it is lost due to the scant management of waste flows. This study aims to model this sector in order to optimize the various flows emanating from buildings undergoing deconstruction and thus improve the overall recovery rate of the induced waste. Modeling of the deconstruction sector by a bi-level problem hinging on a weighted flexible job shop problem (FJSP) evaluated by a non-regular criterion is propounded. A hybrid resolution method based on a genetic algorithm is introduced. A new encoding, taking account of machine idle times, and its associated genetic operators are proposed. Two resolution approaches for the lower-level problem are assessed. Experiments are carried out on simulated but realistic datasets. The first results exhibit the potential of the proposed resolution method.

Abstract. For a fixed finite collection of graphs [Formula: see text] the [Formula: see text]-M-Deletion problem is as follows: given an [Formula: see text]-vertex input graph [Formula: see text] find the minimum number of vertices that intersect all minor models in [Formula: see text] of the graphs in [Formula: see text]. by Courcelle’s Theorem, this problem can be solved in time [Formula: see text] where [Formula: see text] is the treewidth of [Formula: see text] for some function [Formula: see text] depending on [Formula: see text]. In a recent series of articles, we have initiated the program of optimizing asymptotically the function [Formula: see text]. Here we provide an algorithm showing that [Formula: see text] for every collection [Formula: see text]. Prior to this work, the best known function [Formula: see text] was double-exponential in [Formula: see text]. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [ Proc. of the 25 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802–1811] for the particular case [Formula: see text] and of Kociumaka and Pilipczuk [ Algorithmica, 81 (2019), pp. 3655–3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [ Inform. Comput., 256 (2017), pp. 62–82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections [Formula: see text] [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135–152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56–77], our algorithm yields the following complexity dichotomy when [Formula: see text] contains a single connected graph [Formula: see text] assuming the Exponential Time Hypothesis: [Formula: see text] if [Formula: see text] is a contraction of the chair or the banner , and [Formula: see text] otherwise.

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. We consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. Our main contribution is an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.

For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f (tw) · n(1), where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and f (tw) = 2Θ(tw·log tw) otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2Θ(tw·log tw)·n(1) for the more general problem where all minor models of connected graphs in a finite family need to be hit. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case = {K5, K3,3}. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds.

Abstract We study the minimum diameter spanning tree problem under the reload cost model (Diameter‐Treefor short) introduced by Wirth and Steffan. In this problem, given an undirected edge‐colored graphG, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree ofGof minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of theDiameter‐Treeproblem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Δ of the input graph. We prove thatDiameter‐Treeispara‐NP‐hard for any combination of two of these three parameters, and that it isFPTparameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we proveDiameter‐Treeto beNP‐hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan proved that the problem can be solved in polynomial time on graphs with Δ = 3, and Galbiati proved that it isNP‐hard if Δ = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem isNP‐hard if Δ = 3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove thatDiameter‐Treeis inXPandW[1]‐hard parameterized by the treewidth plus Δ.

For a finite collection of graphs ${\cal F}$, the $\mathcal{F}$-M-Deletion problem consists in, given a graph $G$ and an integer $k$, deciding whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in the parameterized complexity of $\mathcal{F}$-M-Deletion when the parameter is the treewidth of $G$, denoted by ${tw}$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{{\cal F}}$ such that $\mathcal{F}$-M-Deletion can be solved in time $f_{{\cal F}}({tw}) \cdot n^{\mathcal{O}(1)}$ on $n$-vertex graphs. We prove that $f_{{\cal F}}({tw}) = 2^{2^{\mathcal{O} ({tw} \cdot\log {tw})}}$ for every collection ${\cal F}$, that $f_{{\cal F}}({tw}) = 2^{\mathcal{O} ({tw} \cdot\log {tw})}$ if ${\cal F}$ contains a planar graph, and that $f_{{\cal F}}({tw}) = 2^{\mathcal{O} ({tw})}$ if in addition the input graph $G$ is planar or embedded in a surface. We also consider the version of the problem where the graphs in ${\cal F}$ are forbidden as topological minors, called $\mathcal{F}$-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring $\mathcal{F}$ to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic.

We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that DIAMETER-TREE is para-np-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with Delta=3, and Galbiati (2008) proved that it is NP-hard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta=3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus Delta.

For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that G-S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F}, the smallest function f_F such that F-M-DELETION can be solved in time f_F(tw)n^{O(1)} on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds: - f_{K_4}(w) = 2^{Theta(wlog w)}. - f_{C_i}(w) = 2^{Theta(w)} for every i<5, and f_{C_i}(w) = 2^{Theta(wlog w)} for every i>4. - f_{P_i}(w) = 2^{Theta(w)} for every i<5, and f_{P_i}(w) = 2^{Theta(wlog w)} for every i>5. The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The single-exponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.

Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Gamma_k. A graph class G has the SQGC property if every graph G in G has treewidth O(bcg(G)c) for some 1 <= c < 2. The SQGC property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.