Problem 1: Catering Contracts, (K Narayan Kumar, CMI)

The government has invited bids from contractors to run canteens at all railway stations. Contractors will be allowed to bid for the catering contract at more than one station. However, to avoid monopolistic price-fixing, the government has declared that no contractor may bid for a pair of neighbouring stations.

The railway network has exactly one route between any pair of stations. Each station is directly connected by a railway line to at most 50 neighbouring stations.

To help contractors plan their bids, the government has provided data on the number of passengers who pass through each station each year. Contractors would like to bid for stations with a higher volume of passenger traffic to increase their turnover.

For instance, suppose the railway network is as follows, where the volume of passenger traffic is indicated by the side of each station.