Deciding if a DAG is Interesting is Hard

Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak +3

The \emph{interestingness score} of a directed path $\Pi =e_1,e_2,e_3,\dots ,e_{\ell }$ in an edge-weighted directed graph $G$ is defined as $\texttt{score}(Π) := \sum_{i=1}^\ell w(e…