  In this work, we seek a more refined understanding of the complexity of local
optimum computation for Max-Cut and pure Nash equilibrium (PNE) computation for
congestion games with weighted players and linear latency functions. We show
that computing a PNE of linear weighted congestion games is PLS-complete either
for very restricted strategy spaces, namely when player strategies are paths on
a series-parallel network with a single origin and destination, or for very
restricted latency functions, namely when the latency on each resource is equal
to the congestion. Our results reveal a remarkable gap regarding the complexity
of PNE in congestion games with weighted and unweighted players, since in case
of unweighted players, a PNE can be easily computed by either a simple greedy
algorithm (for series-parallel networks) or any better response dynamics (when
the latency is equal to the congestion). For the latter of the results above,
we need to show first that computing a local optimum of a natural restriction
of Max-Cut, which we call \emph{Node-Max-Cut}, is PLS-complete. In
Node-Max-Cut, the input graph is vertex-weighted and the weight of each edge is
equal to the product of the weights of its endpoints. Due to the very
restricted nature of Node-Max-Cut, the reduction requires a careful combination
of new gadgets with ideas and techniques from previous work. We also show how
to compute efficiently a $(1+\eps)$-approximate equilibrium for Node-Max-Cut,
if the number of different vertex weights is constant.
