Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913985238925312 |
|---|---|
| author | Bentert, Matthias Crane, Alex Drange, Pål Grønås Mizutani, Yosuke Sullivan, Blair D. |
| author_facet | Bentert, Matthias Crane, Alex Drange, Pål Grønås Mizutani, Yosuke Sullivan, Blair D. |
| contents | We study graph-theoretic formulations of two fundamental problems in algorithmic differentiation. The first (Structural Optimal Jacobian Accumulation) is that of computing a Jacobian while minimizing multiplications. The second (Minimum Edge Count) is to find a minimum-size computational graph. For both problems, we consider the vertex elimination operation. Our main contribution is to show that both problems are NP-complete, thus resolving longstanding open questions. In contrast to prior work, our reduction for Structural Optimal Jacobian Accumulation does not rely on any assumptions about the algebraic relationships between local partial derivatives; we allow these values to be mutually independent. We also provide $O^*(2^n)$-time exact algorithms for both problems, and show that under the exponential time hypothesis these running times are essentially tight. Finally, we provide a data reduction rule for Structural Optimal Jacobian Accumulation by showing that false twins may always be eliminated consecutively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17521 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination Bentert, Matthias Crane, Alex Drange, Pål Grønås Mizutani, Yosuke Sullivan, Blair D. Data Structures and Algorithms Numerical Analysis We study graph-theoretic formulations of two fundamental problems in algorithmic differentiation. The first (Structural Optimal Jacobian Accumulation) is that of computing a Jacobian while minimizing multiplications. The second (Minimum Edge Count) is to find a minimum-size computational graph. For both problems, we consider the vertex elimination operation. Our main contribution is to show that both problems are NP-complete, thus resolving longstanding open questions. In contrast to prior work, our reduction for Structural Optimal Jacobian Accumulation does not rely on any assumptions about the algebraic relationships between local partial derivatives; we allow these values to be mutually independent. We also provide $O^*(2^n)$-time exact algorithms for both problems, and show that under the exponential time hypothesis these running times are essentially tight. Finally, we provide a data reduction rule for Structural Optimal Jacobian Accumulation by showing that false twins may always be eliminated consecutively. |
| title | Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination |
| topic | Data Structures and Algorithms Numerical Analysis |
| url | https://arxiv.org/abs/2506.17521 |