Search

In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species X; these relationships are often depicted via a phylogenetic tree-a tree having its leaves labeled bijectively by elements of X and without degree-2 nodes-called the "species tree." One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g., DNA sequences originating from some species in X), and then constructing a single phylogenetic tree maximizing the "concordance" with the input trees. The obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping-but not identical-sets of labels, is called "supertree." In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of "containing as a minor" and "containing as a topological minor" in the graph community. Both problems are known to be fixed parameter tractable in the number of input trees k, by using their expressibility in monadic second-order logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on k of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time [Formula: see text], where n is the total size of the input.

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 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. [ABSTRACT FROM AUTHOR]

Given a graph G, we define bcg (G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γ k . A graph class G has the SQGC property if every graph G ∈ 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 wide family of graph classes that satisfy the SQGC property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems. [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]

In this paper, we introduce a problem called Minimum subTree problem with Degree Weights , or MTDW. This problem generalized covering tree problems like Spanning Tree , Steiner Tree , Minimum Branch Vertices , Minimum Leaf Spanning Tree , or Prize Collecting Steiner Tree. It consists, given an undirected graph G = (V , E) , a set of m + 1 mappings C 1 , C 2 , ... , C m , D : V × N → Z , a set of m integers K 1 , K 2 , ... , K m ∈ Z and a positive integer ℓ , in the search of a forest (T 1 , T 2 , ... , T ℓ) containing ℓ node-disjoint trees of G. Along with K j , the mapping C j defines a constraint that should be satisfied by the trees of the forest. For each tree T i , it associates each node v of V to the score C j (v , d T i (v)) where d T i (v) is the degree of v in T i (possibly 0 if the node is not in T i). The sum ∑ v ∈ V C j (v , d T i (v)) should not exceed K j. In addition, the forest should minimize ∑ i = 1 ℓ ∑ v ∈ V D (v , d T i (v)). We proceed to a parameterized analysis of the MTDW problem with regard to four parameters that are the number of constraints m , the value ℓ , the treewidth of the input graph G and Δ, the minimum degree above which all the constraints and D are constant (for every j ∈ 〚 1 , m 〛 , v ∈ V and d ≥ Δ , C j (v , d) = C j (v , Δ) , and D (v , d) = D (v , Δ)). For this problem, we provide a first dichotomy P versus NP -hard depending whether the previous parameters are fixed to be constant or not and a second dichotomy FPT versus W[1] -hard depending whether each of these parameters is constant, considered as a parameter, or disregard. As a side effect, we obtained parameterized algorithms, previously undescribed, for problems such that Budget Steiner Tree problem with Profits , Minimum Branch Vertices , Generalized branch vertices , or k -Bottleneck Steiner Tree. [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 (2001) and studied in a number of articles. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs, namely those excluding a C 4 or with maximum degree at most three. In particular, we achieve a ratio of 5 ∕ 9 for subcubic bipartite graphs, improving over a 1 ∕ 2 -approximation algorithm proposed by Mishra (2011). [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]

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]