Deciding if a DAG is Interesting is Hard

Abstract

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 $\text{score}(\hat{I}):={\sum }_{i=1}^{\ell }w(e_i)\cdot \log (i+1)$, where $w(e_i)$ is the weight of the edge $e_i$. We consider two optimization problems that arise in the analysis of Mapper graphs, which is a powerful tool in topological data analysis. In the IP problem, the objective is to find a collection $\mathcal{P}$ of edge-disjoint paths in $G$ with the maximum total interestingness score. %; that is, two raised to the power of the sum of the weights of the paths in $\mathcal{P}$. For $k\in \mathbb{N}$, the $k$-IP problem is a variant of the IP problem with the extra constraint that each path in $\mathcal{P}$ must have exactly $k$ edges. Kalyanaraman, Kamruzzaman, and Krishnamoorthy (Journal of Computational Geometry, 2019) claim that both IP and $k$-IP (for $k\ge 3$) are NP-complete. We point out some inaccuracies in their proofs. Furthermore, we show that both problems are NP-hard in directed acyclic graphs.