Deciding if a DAG is Interesting is Hard
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910879140806656 |
|---|---|
| author | De Carufel, Jean-Lou Maheshwari, Anil Odak, Saeed Roy, Bodhayan Smid, Michiel Vicuna, Marc |
| author_facet | De Carufel, Jean-Lou Maheshwari, Anil Odak, Saeed Roy, Bodhayan Smid, Michiel Vicuna, Marc |
| contents | The \emph{interestingness score} of a directed path $Π= 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_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 \geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_13398 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deciding if a DAG is Interesting is Hard De Carufel, Jean-Lou Maheshwari, Anil Odak, Saeed Roy, Bodhayan Smid, Michiel Vicuna, Marc Computational Complexity Data Structures and Algorithms Combinatorics The \emph{interestingness score} of a directed path $Π= 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_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 \geq 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. |
| title | Deciding if a DAG is Interesting is Hard |
| topic | Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2503.13398 |