Recently, Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number of rows among all matrices with this property. In this paper we disprove several claims about this problem, including an NP-hardness proof of it. However, we show that the problem is indeed NP-hard, by providing a different proof. We also prove NP-completeness of a variant of this problem proposed in the same paper. On the positive side, we propose an efficient (though not necessarily optimal) heuristic algorithm based on coloring co-comparability graphs, and a polynomial time algorithm for solving the problem optimally on matrix instances in which no column is contained in both columns of a pair of conflicting columns. Implementations of these algorithms are freely available at https://github.com/alexandrutomescu/MixedPerfectPhylogeny.
While discussing his spectral bound on the independence number of a graph, Herbert Wilf asked back in 1986 what kind of a graph admits an eigenvector consisting solely of +1/-1 entries? We prove that Wilf's problem is NP-complete, but also that the set of graphs having a +1/-1 eigenvector is quite rich, being closed under a number of different graph compositions.
The main aim of this interdisciplinary paper is to characterize all maps on finite Minkowski space of arbitrary dimension n that map pairs of distinct light-like events into pairs of distinct light-like events. Neither bijectivity of maps nor preservation of light-likeness in the opposite direction, i.e. from codomain to domain, is assumed. We succeed in in many cases, which include the one with n divisible by 4 and the one with n odd and at least 9, by showing that both bijectivity of maps and the preservation of light-likeness in the opposite direction is obtained automatically. In general, the problem of whether there exist non-bijective mappings that map pairs od distinct light-like events into pairs of distinct light-like events is shown to be related to one of the central problems in finite geometry, namely to existence of ovoids in orthogonal polar space. This problem is still unsolved in general despite a huge amount of research done in this area in the last few decades. The proofs are based on the study of a core of an affine polar graph, which yields results that are closely related to the ones obtained previously by Cameron and Kazanidis (2008) for the point graph of a polar space.