As some people remember, and many have been told, the idea of hypertext predates the World...

As some people remember, and many have been told, the idea of hypertext predates the World Wide Web by decades. Even hypertext fiction is a relatively old idea: Rather than being constrained by the linearity of the printed page, you can plot a story that consists of a collection of interlocked virtual "places" joined by virtual "passages."[1] So a piece of hypertext fiction is really riding on an underlying directed graph; to be concrete (though narrowing the full range of what the domain can do), we ll model this as follows.

Let s view the structure of a piece of hypertext fiction as a directed graph G = (V, E). Each node u e V contains some text; when the reader is currently at u, he or she can choose to follow any edge out of u; and if the reader chooses e = (u, v), he or she arrives next at the node v. There is a start node s e V where the reader begins, and an end node t e V; when the reader first reaches t, the story ends. Thus any path from s to t is a valid plot of the story. Note that, unlike one s experience using a Web browser, there is not necessarily a way to go back; once you ve gone from u to v, you might not be able to ever return to u.

In this way, the hypertext structure defines a huge number of different plots on the same underlying content; and the relationships among all these possibilities can grow very intricate. Here s a type of problem one encounters when reasoning about a structure like this. Consider a piece of hypertext fiction built on a graph G = (V, E) in which there are certain crucial thematic elements: love, death, war, an intense desire to major in computer science, and so forth. Each thematic element i is represented by a set Ti ⊆ V consisting of the nodes in G at which this theme appears. Now, given a particular set of thematic elements, we mayask: Is there a valid plot of the story in which each of these elements is encountered? More concretely, given a directed graph G, with start node s and end node t, and thematic elements represented by sets T1, T2,…,Tk, the Plot Fulfillment Problem asks: Is there a path from s to t that contains at least one node from each of the sets Ti?

Prove that Plot Fulfillment is NP-complete.