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 $\hat{I}=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…