Correlation detection in trees for planted graph alignment
  Motivated by alignment of correlated sparse random graphs, we introduce a
hypothesis testing problem of deciding whether or not two random trees are
correlated. We obtain sufficient conditions under which this testing is
impossible or feasible. We propose MPAlign, a message-passing algorithm for
graph alignment inspired by the tree correlation detection problem. We prove
MPAlign to succeed in polynomial time at partial alignment whenever tree
detection is feasible. As a result our analysis of tree detection reveals new
ranges of parameters for which partial alignment of sparse random graphs is
feasible in polynomial time. We then conjecture that graph alignment is not
feasible in polynomial time when the associated tree detection problem is
impossible. If true, this conjecture together with our sufficient conditions on
tree detection impossibility would imply the existence of a hard phase for
graph alignment, i.e. a parameter range where alignment cannot be done in
polynomial time even though it is known to be feasible in non-polynomial time.
