Finding monotone paths in edge-ordered graphs

An edge-ordering   of a graph G=(V,E)G=(V,E) is a one-to-one function ff from EE to a subset of the set of positive integers. A path PP in GG is called an ff-ascent   if ff increases along the edge sequence of PP. The height  h(f)h(f) of ff is the maximum length of an ff-ascent in GG.In this paper we deal with computational problems concerning finding ascents in graphs. We prove that for a given edge-ordering ff of a graph GG the problem of determining the value of h(f)h(f) is NPNP-hard. In particular, the problem of deciding whether there is an ff-ascent containing all the vertices of GG is NPNP-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 kk in graphs of order nn in running time O(4knO(1))O(4knO(1)).