Longest path problem | EPFL Graph Search

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems. The NP-hardness of the unweighted longest path problem can be shown using a reduction from the Hamiltonian path problem: a graph G has a Hamiltonian path if and only if its longest path has length n − 1, where n is the number of vertices in G. Because the Hamiltonian path problem is NP-complete, this reduction shows that the decision version of the longest path problem is also NP-complete. In this decision problem, the input is a graph G and a number k; the desired output is yes if G contains a path of k or more edges, and no otherwise. If the longest path problem could be solved in polynomial time, it could be used to solve this decision problem, by finding a longest path and then comparing its length to the number k. Therefore, the longest path problem is NP-hard. The question "does there exist a simple path in a given graph with at least k edges" is NP-complete. In weighted complete graphs with non-negative edge weights, the weighted longest path problem is the same as the Travelling salesman path problem, because the longest path always includes all vertices.

Problèmes de cheminements optimaux dans les réseaux avec contraintes associées aux arcs

In this thesis we consider two optimal routing problems in networks. Both are NP-hard and are often used to modelize real life problems of large size. We first present the capacitated arc routing problem (CARP). In this problem, we have to serve a set of customers represented by the arcs of a network with vehicles of restricted capacity. The aim is to design a set of vehicle routes of least total cost. We describe two heuristic methods for the CARP based on local search techniques. The first one is a Tabu Search heuristic using an original post-optimization procedure. Principles appearing in this procedure are used to define a class of neighborhoods we combine in a Variable Neighborhood Descent method. Our algorithms compare favorably with some of her methods. They were initially developed to deal with the undirected CARP. We describe how to transform them so that they can be applied to the directed CARP. We also propose an adaptation to the directed case of a lower bound originally developed for the undirected CARP. This lower bound is used to evaluate the quality of the solutions produced by our algorithms for the directed CARP. Our methods obtain solutions whose value is, on average, close to known lower bounds. We use the CARP to tackle a real life problem of boat routing and scheduling. This problem can be viewed as a directed CARP with time windows. We describe in detail its modeling process and we analyze our first results. We obtain solutions that require less boats than the present schedule. Nevertheless, these solutions are not completely feasible in practice. We suggest some ways to improve them. The second problem treated in this thesis is the shortest capacitated paths problem (SCPP). We present a Tabu Search heuristic and some post-optimization procedures for the SCPP. These procedures are called in our Tabu Search algorithm. Two versions of this algorithm are considered. In the first one, post-optimization procedures are intensively used. In the second one, they are less frequently applied. This second version is faster. Compared with a greedy approach, the two versions of our Tabu Search heuristic obtain solutions which are, on average, of better quality. The SCPP was proposed to us by EDF (Electricité de France) in order to minimize the total length of the paths followed by cables in a nuclear power-station. It can also be viewed as a subproblem of the bandwidth packing problem (BWP) appearing in telecommunications.

EPFL2000

Problèmes de cheminements optimaux dans les réseaux avec contraintes associées aux arcs

EPFL2000