# Shortest Paths in Nearly Conservative Digraphs

Preprint · Zoltán Király

- Archive id: arxiv:1409.7033
- Published: 2014-09-24
- Venue: Repository of the Academy's Library (Library of the Hungarian Academy of Sciences)
- arXiv: https://arxiv.org/abs/1409.7033
- Citations: 0
- Source URL: https://arxiv.org/abs/1409.7033
- PDF: https://arxiv.org/pdf/1409.7033
- Provenance: arxiv

## Abstract

We introduce the following notion: a digraph $D=(V,A)$ with arc weights $c: A\\rightarrow \\R$ is called nearly conservative if every negative cycle consists of two arcs. Computing shortest paths in nearly conservative digraphs is NP-hard, and even deciding whether a digraph is nearly conservative is coNP-complete. We show that the "All Pairs Shortest Path" problem is fixed parameter tractable with various parameters for nearly conservative digraphs. The results also apply for the special case of conservative mixed graphs.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.