title: Isomorphism and similarity for 2-generation pedigrees.
abstract: We consider the emerging problem of comparing the similarity between (unlabeled) pedigrees. More specifically, we focus on the simplest pedigrees, namely, the 2-generation pedigrees. We show that the isomorphism testing for two 2-generation pedigrees is GI-hard. If the 2-generation pedigrees are monogamous (i.e., each individual at level-1 can mate with exactly one partner) then the isomorphism testing problem can be solved in polynomial time. We then consider the problem by relaxing it into an NP-complete decomposition problem which can be formulated as the Minimum Common Integer Pair Partition (MCIPP) problem, which we show to be FPT by exploiting a property of the optimal solution. While there is still some difficulty to overcome, this lays down a solid foundation for this research.
authors: Haitao
authors: H
authors: Jiang
authors: Guohui
authors: G
authors: Lin
authors: Weitian
authors: W
authors: Tong
authors: Daming
authors: D
authors: Zhu
authors: Binhai
authors: B
authors: Zhu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D005260:Female; D006801:Humans; D008297:Male; D010375:Pedigree