Search

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]

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629– 638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503–510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 7965 (2013), pp. 613–624] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions, but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper, we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in counting monadic second order logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-Dominating Set and r-Scattered Set on apex-minor-free graphs, and for PLANAR-F-DELETION on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected. [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]

We provide a framework for the design and analysis of dynamic programming algorithms for surfaceembedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2O(k·log k) · n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called surface cut decomposition, generalizing sphere cut decompositions of planar graphs, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of noncrossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2O(k)· n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improvemost previous results in this direction. [ABSTRACT FROM AUTHOR]

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if { u, v} is an edge of H, then there is an edge of G between components C and C. A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming. [ABSTRACT FROM AUTHOR]

Abstract: In this article we study the parameterized complexity of problems consisting in finding degree-constrained subgraphs, taking as the parameter the number of vertices of the desired subgraph. Namely, given two positive integers d and k, we study the problem of finding a d-regular (induced or not) subgraph with at most k vertices and the problem of finding a subgraph with at most k vertices and of minimum degree at least d. The latter problem is a natural parameterization of the d-girth of a graph (the minimum order of an induced subgraph of minimum degree at least d). We first show that both problems are fixed-parameter intractable in general graphs. More precisely, we prove that the first problem is -hard using a reduction from Multi-Color Clique. The hardness of the second problem (for the non-induced case) follows from an easy extension of an already known result. We then provide explicit fixed-parameter tractable (FPT) algorithms to solve these problems in graphs with bounded local treewidth and graphs with excluded minors, using a dynamic programming approach. Although these problems can be easily defined in first-order logic, hence by the results of Frick and Grohe (2001) are FPT in graphs with bounded local treewidth and graphs with excluded minors, the dependence on k of our algorithms is considerably better than the one following from Frick and Grohe (2001) . [Copyright &y& Elsevier]

For a fixed graph H , the H -IS-Deletion problem asks, given a graph G , for the minimum size of a set S ⊆ V (G) such that G ∖ S excludes H as an induced subgraph. We are interested in determining, for a fixed H , the smallest function f H (t) such that H -IS-Deletion can be solved in time f H (t) ⋅ n O (1) assuming the Exponential Time Hypothesis, where t and n denote the treewidth and the number of vertices of G , respectively. We show that f H (t) = 2 O (t h − 2) for every H on h ≥ 3 vertices, and that f H (t) = 2 O (t) if H is a clique or an independent set. When H deviates slightly from a clique, the function f H (t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then f H (t) = 2 Θ (t h − 2). Moreover, f H (t) = 2 Ω (t h) when H = K h , h , answering a question of Pilipczuk [MFCS 2011]. [ABSTRACT FROM AUTHOR]

Abstract Given a simple graph G , a weight function w : E (G) → N ∖ { 0 } , and an orientation D of G , we define μ − (D) = max v ∈ V (G) ⁡ w D − (v) , where w D − (v) = ∑ u ∈ N D − (v) w (u v). We say that D is a weighted proper orientation of G if w D − (u) ≠ w D − (v) whenever u and v are adjacent. We introduce the parameter weighted proper orientation number of G , denoted by χ → (G , w) , which is the minimum, over all weighted proper orientations D of G , of μ − (D). When all the weights are equal to 1, this parameter is equal to the proper orientation number of G , which has been object of recent studies and whose determination is NP -hard in general, but polynomial-time solvable on trees. Here, we prove that the equivalent decision problem of the weighted proper orientation number (i.e., χ → (G , w) ≤ k ?) is (weakly) NP -complete on trees but can be solved by a pseudo-polynomial time algorithm whose running time depends on k. Furthermore, we present a dynamic programming algorithm to determine whether a general graph G on n vertices and treewidth at most tw satisfies χ → (G , w) ≤ k , running in time O (2 tw 2 ⋅ k 3 tw ⋅ tw ⋅ n) , and we complement this result by showing that the problem is W [ 1 ] -hard on general graphs parameterized by the treewidth of G , even if the weights are polynomial in n. [ABSTRACT FROM AUTHOR]

The Outerplanar Diameter Improvement problem asks, given a graph G and an integer D , whether it is possible to add edges to G in a way that the resulting graph is outerplanar and has diameter at most D . We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open. [ABSTRACT FROM AUTHOR]

Abstract: All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any optical–electrical–optical conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in GMPLS terminology. We define a cost function for the hypergraph layout, depending on its total length plus its total hop count. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely for general directed networks we prove that it is NP-hard to find a -approximation, where is a positive constant and is the number of nodes of the network. For symmetric directed networks, we prove that the problem is APX-hard. These hardness results hold even if the traffic instance is a partial broadcast. On the other hand, we provide approximation algorithms, in particular an -approximation for symmetric directed networks. Finally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number of sources running in time. [Copyright &y& Elsevier]

Abstract: The -Minor containment problem asks whether a graph contains some fixed graph as a minor, that is, whether can be obtained by some subgraph of after contracting edges. The derivation of a polynomial-time algorithm for -Minor containment is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. -Minor containment for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1–9], providing an algorithm that in time decides if a graph with edges and branchwidth , contains a fixed graph on vertices as a minor. In this work we improve the dependence on of Hicks’ result by showing that checking if is a minor of can be done in time . We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time , with . Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment. [Copyright &y& Elsevier]