The inverse 1-maxian problem with edge length modification

We consider the problem of modifying the lengths of the edges of a graph at minimum cost such that a prespecified vertex becomes a 1-maxian with respect to the new edge lengths. The inverse 1-maxian problem with edge length modification is shown to be strongly -hard and remains weakly -hard even on series-parallel graphs. Moreover, a transformation of the inverse 1-maxian problem with edge length modification on a tree to a minimum cost circulation problem is given which solves the original problem in . This research has been supported by the Austrian Science Fund (FWF) Project P18918-N18.