Search

The NP-hard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set S of leaf labels and a set R of resolved triplets over S and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R . This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a 1 ∕ 4 -approximation in polynomial time. Next, we generalize Wu’s exact exponential-time algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted k -ary phylogenetic tree for any specified k ≥ 2 subsequently leads to an exponential-time approximation scheme (ETAS) for MTC. We then present a polynomial-time approximation scheme (PTAS) for complete instances of MTC (meaning that for every S ′ ⊆ S with | S ′ | = 3 , R contains at least one rooted triplet involving the leaf labels in S ′ ), based on the techniques introduced by Jiang et al. (2001) for a related problem. We also study the computational complexity of MTC restricted to fan triplets and forbidden fan triplets. Finally, extensions to weighted instances are considered.

We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size $s$ and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slowe...

The maximum rooted resolved triplets consistency problem takes as input a set \(\mathcal {R}\) of resolved triplets and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in \(\mathcal {R}\). This paper studies the polynomial-time approximability of a generalization of the problem where in addition to resolved triplets, the input may contain fan triplets and forbidden triplets. To begin with, we observe that the generalized problem admits a 1/4-approximation in polynomial time. Next, we present a polynomial-time approximation scheme (PTAS) for dense instances based on smooth polynomial integer programming. Finally, we generalize Wu’s exact exponential-time algorithm in [19] for the original problem to also allow fan triplets, forbidden resolved triplets, and forbidden fan triplets. Forcing the algorithm to always output a \(k\)-ary phylogenetic tree for any specified \(k \ge 2\) then leads to an exponential-time approximation scheme (ETAS) for the generalized, unrestricted problem.