On the complexity of and algorithms for detecting k-length negative cost cycles

Longkun Guo () and Peng Li ()
Additional contact information
Longkun Guo: Fuzhou University
Peng Li: Amazon.com Inc.

Journal of Combinatorial Optimization, 2021, vol. 42, issue 3, No 5, 396-408

Abstract: Abstract Let G be a directed graph with an integral cost on each edge. For a given positive integer k, the k-length negative cost cycle (kLNCC) problem is to determine whether G contains a negative cost cycle with at least k edges. Because of its applications in deadlock avoidance in synchronized streaming computing network, kLNCC was first studied in paper (Li et al. in Proceedings of the 22nd ACM symposium on parallelism in algorithms and architectures, pp 243–252, 2010), but remains open whether the problem is $${\mathcal{NP}}$$ NP -hard. In this paper, we first show that an even harder problem, the fixed-point k-length negative cost cycle trail (FPkLNCCT) problem that is to determine whether G contains a negative closed trail enrouting a given vertex (as the fixed point) and containing only cycles with at least k edges, is $${\mathcal{NP}}$$ NP -complete in a multigraph even when $$k=3$$ k = 3 by reducing from the 3SAT problem. Then, we prove the $${\mathcal{NP}}$$ NP -completeness of kLNCC by giving a more sophisticated reduction from the 3 occurrence 3-satisfiability (3O3SAT) problem which is known $${\mathcal{NP}}$$ NP -complete. The complexity result for kLNCC is interesting since polynomial-time algorithms are known for both 2LNCC, which is actually equivalent to negative cycle detection, and the k-cycle problem, which is to determine whether G contains a cycle with of length at least k. Thus, this paper closes the open problem proposed by Li et al. (2010) whether kLNCC admits polynomial-time algorithms. Last but not the least, we present for 3LNCC a randomized algorithm that, if G contains a negative cycle of length at most L, can find a solution with a probability $$1-\epsilon $$ 1 - ϵ for any $$\epsilon \in (0,\,1]$$ ϵ ∈ ( 0 , 1 ] within runtime $$O(2^{\min \{L,\,h\}}mn\left\lceil \ln \frac{1}{\epsilon }\right\rceil )$$ O ( 2 min { L , h } m n ln 1 ϵ ) , where m, n and h are respectively the numbers of edges, vertices and length 2 negative cost cycles in G.

Keywords: k-Length negative cost cycle; $${\mathcal{NP}}$$ NP -Complete; 3 occurrence 3-satisfiability; 3-Satisfiability; Randomized algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-00371-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:42:y:2021:i:3:d:10.1007_s10878-018-00371-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-00371-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().