The Complexity of List Ranking of Trees

Abstract

A vertex \(k\)-ranking of a graph \(G\) is a function \(c: V(G) \to \{1,\ldots,k\}\) such that if \(c(u) = c(v)\), \(u,v \in V(G)\), then each path connecting vertices \(u\) and \(v\) contains a vertex \(w\) with \(c(w) > c(u)\). If each vertex \(v\) has a list of integers \(L(v)\) and for a vertex ranking \(c\) it holds \(c(v) \in L(v)\) for each \(v \in V(G)\), then \(c\) is called an \(L\)-list \(k\)-ranking, where \(\mathcal{L} = \{L(v) : v \in V(G)\}\). In this paper, we investigate both vertex and edge (vertex ranking of a line graph) list ranking problems. We prove that both problems are NP-complete for several classes of acyclic graphs, like full binary trees, trees with diameter at most \(4\), and comets. The problem of finding vertex (edge) \(\mathcal{L}\)-list ranking is polynomially solvable for paths and trees with a bounded number of non-leaves, which includes trees with diameter less than \(4\).