Characterizing Star-PCGs
- PDF / 5,144,152 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 214 Views
Characterizing Star‑PCGs Mingyu Xiao1 · Hiroshi Nagamochi2 Received: 20 January 2019 / Accepted: 15 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, dmin , dmax ) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals dmin ≤ dmax such that G has an edge between two vertices u, v ∈ V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [dmin , dmax ] . The tree T is also called a witness tree of the PCG G. How to recognize PCGs is a wide-open problem in the literature. This paper gives a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs. Keywords Pairwise compatibility graph · Polynomial-time algorithm · Graph algorithm · Graph theory
1 Introduction The pairwise compatibility graph is a graph class originally motivated from computational biology. In biology, the evolutionary history of a set of organisms is represented by a phylogenetic tree, which is a tree with leaves representing known taxa and internal nodes representing ancestors that might have led to these taxa through evolution. Moreover, the edges in the phylogenetic tree may be assigned weights to represent the evolutionary distance among species. Given a set of taxa and some relations among the taxa, we may want to construct a phylogenetic tree of the taxa. The set of taxa may be a subset of taxa from a large phylogenetic tree, subject to some biologically-motivated constraints. Kearney et al. [13] considered the following constraint on sampling based on the observation in [11]: the pairwise distance * Mingyu Xiao [email protected] 1
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China
2
Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan
13
Vol.:(0123456789)
Algorithmica
between any two leaves in the sample phylogenetic tree is between two given integers dmin and dmax . This motivates the introduction of pairwise compatibility graphs (PCGs). Given a phylogenetic tree T with an edge weight w and two real numbers dmin and dmax , we can construct a graph G whose each vertex is corresponding to a leaf of T so that there is an edge between two vertices in G if and only if the corresponding two leaves of T are at a distance within the interval [dmin , dmax ] in T. The graph G is called the PCG of the tuple (T, w, dmin , dmax ). It is straightforward to construct a PCG from a given tuple (T, w, dmin , dmax ) . However, the inverse direction seems to be a considerably hard task. Few methods have been known for constructing a corresponding tuple (T, w, dmin , dmax ) from a given graph G. The inverse problem attracts certain interests in graph algorithm
Data Loading...
