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]

We consider a non-monotone activation process (Xt)t2{0,1,2,...} on a graph G, where X0 = V (G), Xt = {u 2 V (G): |NG(u) \ Xt-1| = = (u)} for every positive integer t, and =: V (G) ! Z is a threshold function. The set X0 is a so-called non-monotone target set for (G, ι) if there is some t0 such that Xt = V (G) for every t = t0. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8 (2011) 87-96] asked whether a target set of minimum order can be determined efficiently if G is a tree. We answer their question in the affirmative for threshold functions ι satisfying ι (u) 2 {0, 1, dG(u)} for every vertex u. For such restricted threshold functions, we give a characterization of target sets that allows to show that the minimum target set problem remains NP-hard for planar graphs of maximum degree 3 but is efficiently solvable for graphs of bounded treewidth. [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]

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]

Golumbic, Hirst, and Lewenstein define a matching in a simple, finite, and undirected graph G to be uniquely restricted if no other matching covers exactly the same set of vertices. We consider uniquely restricted edge‐colorings of G, defined as partitions of its edge set into uniquely restricted matchings, and study the uniquely restricted chromatic index χ′ur(G) of G, defined as the minimum number of uniquely restricted matchings required for such a partition. For every graph G, χ′(G)≤a′(G)≤χ′ur(G)≤χ′s(G), where χ′(G) is the classical chromatic index, a′(G) the acyclic chromatic index, and χ′s(G) the strong chromatic index of G. While Vizing's famous theorem states that χ′(G) is either the maximum degree Δ(G) of G or Δ(G)+1, two famous open conjectures due to Alon, Sudakov, and Zaks, and to Erdős and Nešetřil concern upper bounds on a′(G) and χ′s(G) in terms of Δ(G). Since χ′ur(G) is sandwiched between these two parameters, studying upper bounds in terms of Δ(G) is a natural problem. We show that χ′ur(G)≤Δ(G)2 with equality if and only if some component of G is KΔ(G),Δ(G). If G is connected, bipartite, and distinct from KΔ(G),Δ(G), and Δ(G) is at least 4, then, adapting Lovász's elegant proof of Brooks' theorem, we show that χ′ur(G)≤Δ(G)2−Δ(G). Our proofs are constructive and yield efficient algorithms to determine the corresponding edge‐colorings. [ABSTRACT FROM AUTHOR]

A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein and studied in a number of articles. Our contribution is twofold. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of 5/9 for subcubic bipartite graphs, improving over a 1/2-approximation algorithm proposed by Mishra. Furthermore, we study the uniquely restricted chromatic index of a graph, defined as the minimum number of uniquely restricted matchings into which its edge set can be partitioned. We provide tight upper bounds in terms of the maximum degree and characterize all extremal graphs. Our constructive proofs yield efficient algorithms to determine the corresponding edge colorings. [ABSTRACT FROM AUTHOR]

Let be the number of labeled graphs on n vertices and treewidth at most k (equivalently, the number of labeled partial k-trees). We show that ]> ]> k > 1 ]> ]> ]> c > 0 ]> ]> ]> ( log k ) n ]> . The upper bound is a direct consequence of the well-known formula for the number of labeled k-trees, while the lower bound is obtained from an explicit construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most k. [ABSTRACT FROM AUTHOR]

In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in k + r for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of 'base' solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest. [ABSTRACT FROM AUTHOR]