Search

Given two integers ℓ and p as well as ℓ graph classes H1, . . ., Hℓ, the problems GraphPart(H1, . . ., Hℓ, p), VertPart(H1, . . ., Hℓ), and EdgePart(H1, . . ., Hℓ) ask, given graph G as input, whether V (G), V (G), E(G) respectively can be partitioned into ℓ sets S1, . . ., Sℓ such that, for each i between 1 and ℓ, G[Si] ∈ Hi, G[Si] ∈ Hi, (V (G), Si) ∈ Hi respectively. Moreover in GraphPart(H1, . . ., Hℓ, p), we request that the number of edges with endpoints in different sets of the partition is bounded by p. We show that if there exist dynamic programming treedecomposition-based algorithms for recognizing the graph classes Hi, for each i, then we can constructively create a dynamic programming tree-decomposition-based algorithms for GraphPart(H1, . . ., Hℓ, p), VertPart(H1, . . ., Hℓ), and EdgePart(H1, . . ., Hℓ). We apply this approach to known problems. For well-studied problems, like VERTEX COVER and GRAPH q-COLORING, we obtain running times that are comparable to those of the best known problemspecific algorithms. For an exotic problem from bioinformatics, called DISPLAYGRAPH, this approach improves the known algorithm parameterized by treewidth. [ABSTRACT FROM AUTHOR]

For a fixed finite collection of graphs F, the F-M-DELETION problem is as follows: given an n-vertex input graph G, find the minimum number of vertices that intersect all minor models in G of the graphs in F. by Courcelle's Theorem, this problem can be solved in time fF(tw) - n°(1), where tw is the treewidth of G for some function ƒ depending on F. In a recent series of articles, we have initiated the program of optimizing asymptotically the function ff. Here we provide an algorithm showing that fF(tw) = 2° (tw.log tw) for every collection F. Prior to this work, the best known function ƒ was double- exponential in tw. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802-1811] for the particular case F = {K5, K3,3} 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 F [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 F = {H} contains a single connected graph H, assuming the Exponential Time Hypothesis: ƒH(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and fH(tw) = 2Θ(tw-log tw) otherwise. [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, deciding whether there exists S ⊆ V (G) with |S| ≤ 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 fF such that F-M-DELETION can be solved in time fF(tw) . nO(1) on n-vertex graphs. We prove that fF(tw) = 2²O(tw.logtw) for every collection F, that fF(tw) = 2O(tw.log tw) if F contains a planar graph, and that fF(tw) = 2O(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 F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring 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. [ABSTRACT FROM AUTHOR]

For a finite fixed collection of graphs F , the F -M-Deletion problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor. We provide lower bounds under the ETH on 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, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, f F (tw) = 2 Ω (tw) , even if G is planar. Our main result is that if F contains a single connected graph H that is either P 5 or is not a minor of the b a n n e r , then f F (tw) = 2 Ω (tw ⋅ log ⁡ tw). [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F , the F -M-Deletion (resp. F -TM-Deletion) problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G , denoted by tw , and specifically in the cases where F contains a single connected planar graph H. We present algorithms running in time 2 O (tw) ⋅ n O (1) , called single-exponential , when H is either P 3 , P 4 , C 4 , the paw , the chair , and the banner for both { H } -M-Deletion and { H } -TM-Deletion , and when H = K 1 , i , with i ≥ 1 , for { H } -TM-Deletion. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. (2015) [7]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of { H } -M-Deletion in terms of H. [ABSTRACT FROM AUTHOR]

We study the minimum diameter spanning tree problem under the reload cost model (Diameter‐Tree for short) introduced by Wirth and Steffan. 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 Δ 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 proved that the problem can be solved in polynomial time on graphs with Δ = 3, and Galbiati proved that it is NP‐hard if Δ = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP‐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 that Diameter‐Tree is in XP and W[1]‐hard parameterized by the treewidth plus Δ. [ABSTRACT FROM AUTHOR]

Given a graph G , a proper k-coloring of G is a partition c = ( S i ) i ∈ [ 0 , k − 1 ] of V ( G ) into k stable sets S 0 , … , S k − 1 . Given a weight function w : V ( G ) → R + , the weight of a color S i is defined as w ( i ) = max v ∈ S i ⁡ w ( v ) and the weight of a coloring c as w ( c ) = ∑ i = 0 k − 1 w ( i ) . Guan and Zhu (1997) [11] defined the weighted chromatic number of a pair ( G , w ) , denoted by σ ( G , w ) , as the minimum weight of a proper coloring of G . For a positive integer r , they also defined σ ( G , w ; r ) as the minimum of w ( c ) among all proper r -colorings c of G . The complexity of determining σ ( G , w ) when G is a tree was open for almost 20 years, until Araújo et al. (2014) [1] recently proved that the problem cannot be solved in time n o ( log ⁡ n ) on n -vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing σ ( G , w ) and σ ( G , w ; r ) when G is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis FPT ≠ W [ 1 ] . Building on the techniques of Araújo et al., we prove that when G is a forest, the decision problem of computing σ ( G , w ) is W [1]-hard parameterized by the size of a largest connected component of G , and that computing σ ( G , w ; r ) is W [2]-hard parameterized by r . Our results rule out the existence of FPT algorithms for computing these invariants on trees or forests for many natural choices of the parameter. [ABSTRACT FROM AUTHOR]

A proper k-coloring of a graph G is a partition c = ( S i ) i ∈ [ 1 , k ] of V ( G ) into k stable sets S 1 , … , S k . Given a weight function w : V ( G ) → R + , the weight of a color S i is defined as w ( i ) = max v ∈ S i ⁡ w ( v ) and the weight of a coloring c as w ( c ) = ∑ i = 1 k w ( i ) . Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair ( G , w ), denoted by σ ( G , w ) , as the minimum weight of a proper coloring of G . For a positive integer r , they also defined σ ( G , w ; r ) as the minimum of w ( c ) among all proper r -colorings c of G . The complexity of determining σ ( G , w ) when G is a tree was open for almost 20 years, until Araújo et al. [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time n o ( log ⁡ n ) on n -vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing σ ( G , w ) and σ ( G , w ; r ) when G is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis FPT ≠ W [ 1 ] . Building on the techniques of Araújo et al. , we prove that when G is a forest, computing σ ( G , w ) is W [ 1 ] -hard parameterized by the size of a largest connected component of G , and that computing σ ( G , w ; r ) is W [ 2 ] -hard parameterized by r . Our results rule out the existence of FPT algorithms for computing these invariants on trees or forests for many natural choices of the parameter. [ABSTRACT FROM AUTHOR]

For some years it was believed that for “connectivity” problems such as Hamiltonian Cycle , algorithms running in time 2 O ( tw ) ⋅ n O ( 1 ) – called single-exponential – existed only on planar and other topologically constrained graph classes, where tw stands for the treewidth of the n -vertex input graph. This was recently disproved by Cygan et al. [ 3 , FOCS 2011], Bodlaender et al. [ 1 , ICALP 2013], and Fomin et al. [ 11 , SODA 2014], who provided single-exponential algorithms on general graphs for most connectivity problems that were known to be solvable in single-exponential time on topologically constrained graphs. In this article we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. Known results from the literature imply that there exist problems, like Cycle Packing , that cannot be solved in time 2 o ( tw log ⁡ tw ) ⋅ n O ( 1 ) on general graphs but that can be solved in time 2 O ( tw ) ⋅ n O ( 1 ) when restricted to planar graphs. Our main contribution is to show that there exist natural problems that can be solved in time 2 O ( tw log ⁡ tw ) ⋅ n O ( 1 ) on general graphs but that cannot be solved in time 2 o ( tw log ⁡ tw ) ⋅ n O ( 1 ) even when restricted to planar graphs. Furthermore, we prove that Planar Cycle Packing and Planar Disjoint Paths cannot be solved in time 2 o ( tw ) ⋅ n O ( 1 ) . The mentioned negative results hold unless the ETH fails. We feel that our results constitute a first step in a subject that can be further exploited. [ABSTRACT FROM AUTHOR]