Search

In this paper, we design and analyze a fast, randomized algorithm for the problem of finding a negative cost cycle having the smallest number of edges in a directed, weighted graph. This problem will henceforth be referred to as the Shortest Negative Cost Cycle problem (SNCC). SNCC is closely related to the problem of checking whether a directed, weighted graph contains a negative cost cycle (NCCD). NCCD is an extremely well-studied problem within the domains of operations research and theoretical computer science. SNCC is important in its own right and finds several applications in program verification (Satisfiability modulo theories), abstract interpretation and real-time scheduling. It is also an important subroutine in solving the generalized submodular flow problem, which has applications in trading networks. The randomized algorithm presented in this paper for SNCC determines a shortest negative cost cycle with probability at least ( 1 − e − 1 ) in O ( m ⋅ n ⋅ log n ) time, on a network with n vertices and m edges. This is, in general, a significant improvement over the best deterministic bound of O ( m ⋅ n ⋅ | C ∗ | ) over the same parameters, where C ∗ is a shortest negative cost cycle. This algorithm requires Ω ( n ⋅ log n ) random bits. We then propose a second randomized algorithm that runs in O ( m ⋅ n ⋅ log n ) expected time and requires O ( n ) random bits (expected). [ABSTRACT FROM AUTHOR]

The undirected negative cost cycle detection (UNCCD) problem is concerned with checking whether an undirected, weighted graph contains a negative cost cycle. Known approaches for solving this problem involve reducing it to either the minimum weight $$b$$ - matching problem or the minimum weight $$T$$ - join problem. In this paper, we formally describe these two approaches and provide the tightest known analysis of the $$b$$ -matching approach. Our analysis establishes that the $$b$$ -matching approach runs in $$O((n+m)^{2}\cdot \log (n+m))$$ time on a graph with $$n$$ nodes and $$m$$ edges. We also explore the case where the edge costs are integers in the range $$\{-K,\ldots , K\}$$ . For $$K = O(1)$$ , we provide improved time bounds for both the above-mentioned approaches by exploiting the existence of specialized procedures for optimization problems in graphs with integral positive edge costs. We show that while the $$T$$ -join algorithm has a better time bound for general graphs, the $$b$$ -matching algorithm is more efficient for sparse graphs. Finally, we present one of the first, extensive empirical studies for the UNCCD problem. We examine both approaches on several different families of undirected graphs. Our findings provide insight into the actual efficiency of each approach and reinforce the asymptotic analysis of our algorithms. [ABSTRACT FROM AUTHOR]

This paper is concerned with the design and analysis of algorithms for optimization problems in arc-dependent networks. A network is said to be arc-dependent if the cost of an arc a depends upon the arc taken to enter a. These networks are fundamentally different from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. We first study the arc-dependent shortest path (ADSP) problem, which is also known as the suffix-1 path-dependent shortest path problem in the literature. This problem has a polynomial time solution if the shortest paths are not required to be simple. The ADSP problem finds applications in a number of domains, including highway engineering, turn penalties and prohibitions, and fare rebates. In this paper, we are interested in the ADSP problem when restricted to simple paths. We call this restricted version the simple arc-dependent shortest path (SADSP) problem. We show that the SADSP problem is NP-complete. We present inapproximability results and an exact exponential algorithm for this problem. We also extend our results for the longest path problem in arc-dependent networks. Additionally, we explore the problem of detecting negative cycles in arc-dependent networks and discuss its computational complexity. Our results include variants of the negative cycle detection problem such as longest, shortest, heaviest, and lightest negative simple cycles. 2 2 An extended abstract of this work appeared in Wojciechowski et al. (2020). [ABSTRACT FROM AUTHOR]

Abstract: The negative cost cycle detection (NCCD) problem in weighted directed graphs is a fundamental problems in theoretical computer science with applications in a wide range of domains ranging from maximum flows to image segmentation. From the perspective of program verification, this problem is identical to the problem of checking the satisfiability of a conjunction of difference constraints. There exist a number of approaches in the literature for NCCD with each approach having its own set of advantages. Recently, a greedy, space-efficient algorithm called the stressing algorithm was proposed for this problem. In this paper, we present a novel proof of the Stressing algorithm and its verification using the Prototype Verification System (PVS) theorem prover. This example is part of a larger research program to verify the soundness and completeness of a core set of decision procedures. [Copyright &y& Elsevier]

Abstract: In this paper, we propose an efficient method for implementing Dijkstra''s algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges have positive length, and where there are few distinct edge lengths. The SSSPP is one of the most widely studied problems in theoretical computer science and operations research. On a graph with n vertices, m edges and K distinct edge lengths, our algorithm runs in time if , and time, otherwise. We tested our algorithm against some of the fastest algorithms for SSSPP on graphs with arbitrary but positive lengths. Our experiments on graphs with few edge lengths confirmed our theoretical results, as the proposed algorithm consistently dominated the other SSSPP algorithms, which did not exploit the special structure of having few distinct edge lengths. [Copyright &y& Elsevier]

Abstract In this paper, we empirically profile three algorithms for the Shortest Negative Cost Cycle (SNCC) problem. In this problem, we are given a directed, weighted graph G = 〈 V , E , c 〉 , and the goal is to identify a negative cost cycle with the fewest number of edges. The SNCC problem finds applications in a number of domains ranging from program verification to certifying algorithm design. The first polynomial time algorithm for this problem was proposed in Subramani (2009). Since then, several additional techniques, including a randomized approach, have been proposed for the SNCC problem. Our goal in this paper is to analyze three algorithmic paradigms for this problem from the empirical perspective. Towards this end, we profile these algorithmic approaches over a wide range of inputs. Our results indicated that the randomized algorithm is the algorithm of choice over a number of graph classes. [ABSTRACT FROM AUTHOR]