Nytimes.com is creating a paywall (a system that prevents Internet users from accessing certain

webpage content without a paid subscription). The site is modeled as a directed graph G = (V,E) in which

nodes are webpages and edges are hyperlinks. The homepage is accessible to everyone and the rest of

the sites is split into k zones (Z1,Z2 ... Zk) in which each page (node) belongs to a single zone. A path taken

by a non-subscriber is restricted to include at most one node (page) from each zone.

You’ve been hired to develop an algorithm to analyze the reachability of pages on Nytimes.com.

Specifically the question: Is it possible for a non-subscriber to visit a given page, p? More precisely, we

define the Non-payer Path problem as follows: Given G, Z1,Z2 ... Zk (k zones), a start page, s € V and a

target page, t € V; is there an s-t path that includes at most one page from each zone.

Is the Non-payer Path problem NP-complete? If so, prove it. If not, come up with a polynomial-time

algorithm to find an s-t path.