A characterization for tropical polynomials being the minimum finishing time of project networks (Q1797241)

This interesting paper is devoted to the connection between tropical polynomials and project network theory. \par A project network consists of some activities where all activities can be started after all the preceding activities have been finished. By taking the Hasse diagram of the ordered set of activities a project network is represented as a directed acyclic graph where each activity is endowed with a non-negative real number $t_i$ called the time cost. The minimum finishing time of the project network is the minimum time needed for finishing all the activities in this network. The minimum finishing time can be represented by a tropical polynomial. A tropical polynomial is called realizable, or $R$-polynomial, if it can be represented as the minimum finishing time of a certain project network. An $R$-polynomial satisfies the following 3 conditions: (1) the degree of each variable is exactly one, (2) the coefficients of each term is a unity, (3) no term is divisible by any other terms. A tropical polynomial satisfying these three conditions is called prerealizable, or $P$-polynomial. Note that a $P$-polynomial is not always an $R$-polynomial, $t_1t_2+t_2t_3+t_3t_1$ can be considered as an example. \par A characterization of $R$-polynomials in terms of posets was known, but this is not effective for judging whether a given $P$-polynomial is an $R$-polynomial. In this paper, another characterization is given, which uses the graph language. Namely, the authors introduce the notion of term extendability condition, prove that any $R$-polynomial satisfies this condition, and prove that there is a one-to-one correspondence between the set of $P$-polynomials in $n$ variables possessing term extendability and the set of simple graphs on $n$ variables. Via this correspondence two graphs are isomorphic if and only if the corresponding $P$-polynomials coincide up to the permutation of variables. Then it is proved that if $f(t)$ is a $P$-polynomial of degree $d$ possessing term extendability, then $f(t)$ is an $R$-polynomial if and only if there is a vertex coloring of the corresponding graph with the color set $\{1,\ldots,d\}$ such that every increasing path of three vertices is a clique of this graph.