Finding monotone paths in edge-ordered graphs

AbstractAn edge-ordering of a graph G=(V,E) is a one-to-one function f from E to a subset of the set of positive integers. A path P in G is called an f-ascent if f increases along the edge sequence of P. The height h(f) of f is the maximum length of an f-ascent in G.In this paper we deal with computational problems concerning finding ascents in graphs. We prove that for a given edge-ordering f of a graph G the problem of determining the value of h(f) is NP-hard. In particular, the problem of deciding whether there is an f-ascent containing all the vertices of G is NP-complete. We also study several variants of this problem, discuss randomized and deterministic approaches and provide an algorithm for the finding of ascents of order at least k in graphs of order n in running time O(4knO(1))