Example Assignment Below:

Assignment: For each of the eight Recommended Target graph problems (see below), design a real- world problem that can be reduced to the target graph problem. Real-world problems may come from any field(s): security, computer networks, biology, linguistics, social networks, scheduling, match making, stocks market, etc. You can search Google or Google Scholar or any other sources for real-problem examples. Usually, the research papers (e.g., papers on Vertex Cover (VC) Problem, will include Motivation in their Introduction section where they mention examples of real-world problems where such VC problem can be or has been applied. o No two real-world problems for the same graph problem are allowed o See an example of the posted solution from the previous class Recommended Target Graph Problems (8 problems total). You may offer your own set of eight Graph Problems: make sure to clearly define each of the graph problems before using it for the real-world application example. o Clique, o Vertex Cover, o Independent Set, o Dominating Set o Hamiltonian path o Hamiltonian cycle, Shortest path, Shortest Cycle o 0 Grading Rubric for Each of the Target Problem (5 points per problem; 40 points total): o Description of a real-world problem (1 point) o Identification of the corresponding graph problem (1 point) o Description of the reduction from real to graph problem (3 points): What nodes and edges are, what the problem solution corresponds to (e.g., VC solution for the graph means what in the context of the real-world problem) Problem: Optimal placement of power plants among a group of cities. Consider a group of cities, some of which are connected by power lines. You wish to place power plants in some of the cities, such that all of the cities receive power. A power plant can power the city that it is in, as well as any number of cities directly connected by power lines; however, because of losses due to power transmission, power cannot be economically transmitted through multiple power line links (e.g., through an intermediate city or cities to a remotely connected city). Question: What is the fewest number of power plants that can be placed such that all cities receive power, and what is one such configuration? Corresponding graph problem: Minimum Dominating Set. Reduction: Let each city be represented by a node in a graph, and let each direct power line connection between 2 cities be represented by an edge connecting the corresponding vertices in the graph. A minimum dominating set in this graph is a set of vertices such that every vertex not in S is adjacent to some member of S. If power plants are built in each of the cities corresponding to a vertex in S, every city will either contain a power plant, or be directly connected via power lines to a city that contains a power plant. Since S is a minimum dominating set, it contains the fewest number of vertices (power plants) possible for a dominating set. Thus any minimum dominating set S is a solution to this problem, and represents a possible configuration of power plants. Problem: Computer network routing with minimum latency. Consider a computer network which consists of a number of switches and computers, some of which are connected to each other via network links (Cat5 cables, wireless connections, etc.). Suppose each network link has certain transmission latency associated with it. Question: Given any two computers that wish to communicate, what is the series of intermediate switches that a packet must travel through such that the total transmission latency is minimized? Corresponding graph problem: Shortest path. Reduction: Let each computer and switch be represented by a node in a graph, and let the network links be represented by edges, and let each edge be weighted according to the transmission latency of the associated network link. Given any two computers, the problem can be solved by finding the shortest path in the graph between the nodes that represent those computers. This shortest path will contain the switches through which a packet can be transmitted such that the total transmission latency is minimum, thus it represents the solution to the original problem. Problem: Project scheduling. Consider a large project undertaken by a firm (for instance, a large piece of software). The project can be broken into a number of smaller tasks, some of which have prerequisites (can only be started after another task/tasks is/are completed). Suppose each task has a known estimated time for completion. Assume that the firm has enough resources to execute many tasks concurrently, assuming that all prerequisites have been met. Question: How long will the project take (e.g. how long will it take to complete all tasks)? Corresponding graph problem: Longest path. Reduction: Let the completion of each task be represented by a vertex in a graph. Also add a vertex to represent the start of the project (call it vertex S), and one to represent the end of the project (vertex E). If some task B has some task A as a prerequisite, add a directed edge from the vertex representing task A to the vertex for task B, and weight that edge with the time for completing task B. Also add directed edges from vertex S (the start vertex) to the vertices for all tasks that have no prerequisites (that can be started immediately), and weight them with the time for completing the corresponding task. Also add directed edges from vertices for terminal tasks (tasks that no other tasks rely on as prerequisites) to vertex E (the end vertex), all of weight 0. Now, the amount of time the project will take is the longest path from vertex Sto vertex E. This longest path represents the chain of tasks, each of which has the previous task as a prerequisite, such that the time for completing all of these tasks is maximal. Since it is the longest path, there is no other sequence of tasks that will take longer. Also, the project cannot be completed in less time than this sequence of tasks. This is because the last task in the path before vertex E must be completed, and since it relies on the task before it to be completed before it, that task must also be completed. This reasoning can be iterated back to the first task with no prerequisites, which will be started immediately. Since none of these tasks can be omitted, and they must all be completed in serial order, this sequence of tasks in the longest path will dictate the time span of the project. Problem: Video surveillance: A grocery store wants to have a camera recording activity on every aisle in the store. Only one camera is required to cover an aisle. The store owner wants to buy the least amount of cameras to accomplish this task. Corresponding graph problem: Minimum Vertex Cover: for an undirected graph, the minimum subset of vertices such that each edge has at least one endpoint in the subset (i.e. for each edge in the graph, one of its vertices must be an element of the vertex cover). Reduction: The aisles in the grocery store are the edges and the vertices represent intersections. The Minimum Vertex Cover of this graph will be the fewest number of cameras the store owner can place at aisle intersections in order to monitor activity on each aisle. Problem: School bus route: A school bus driver boards his/her school bus at the elementary school in the morning. The driver must stop at every bus stop on his/her route to pick up school children, and at the end of his/her route, drop the children off at school. Corresponding graph problem: Hamiltonian Cycle: a cycle in an undirected graph which visits each vertex exactly once and also returns to the starting vertex. Reduction: The school bus driver's graph is composed of his/her predefined bus stops and route. Each bus stop is a vertex in the graph and the roads are edges. The starting and ending vertex is the elementary school. The bus driver is required to visit every bus stop and he/she cannot visit a bus stop more than once because that would deviate from the predefined route. Problem: Scavenger hunt: A professor sets up a scavenger hunt for his students by placing the hunted items around the university campus. He then gives the list of items to be hunted to the students. The students are required to find every item. Corresponding graph problem: Hamiltonian Path: a path in an undirected graph which visits each vertex exactly once. Reduction: Each hunted item is a vertex in the graph and the routes around campus are edges. Students must visit each vertex in order to find every item on the scavenger hunt list. It is pointless for students to return to an item they have already found. Assignment: For each of the eight Recommended Target graph problems (see below), design a real- world problem that can be reduced to the target graph problem. Real-world problems may come from any field(s): security, computer networks, biology, linguistics, social networks, scheduling, match making, stocks market, etc. You can search Google or Google Scholar or any other sources for real-problem examples. Usually, the research papers (e.g., papers on Vertex Cover (VC) Problem, will include Motivation in their Introduction section where they mention examples of real-world problems where such VC problem can be or has been applied. o No two real-world problems for the same graph problem are allowed o See an example of the posted solution from the previous class Recommended Target Graph Problems (8 problems total). You may offer your own set of eight Graph Problems: make sure to clearly define each of the graph problems before using it for the real-world application example. o Clique, o Vertex Cover, o Independent Set, o Dominating Set o Hamiltonian path o Hamiltonian cycle, Shortest path, Shortest Cycle o 0 Grading Rubric for Each of the Target Problem (5 points per problem; 40 points total): o Description of a real-world problem (1 point) o Identification of the corresponding graph problem (1 point) o Description of the reduction from real to graph problem (3 points): What nodes and edges are, what the problem solution corresponds to (e.g., VC solution for the graph means what in the context of the real-world problem) Problem: Optimal placement of power plants among a group of cities. Consider a group of cities, some of which are connected by power lines. You wish to place power plants in some of the cities, such that all of the cities receive power. A power plant can power the city that it is in, as well as any number of cities directly connected by power lines; however, because of losses due to power transmission, power cannot be economically transmitted through multiple power line links (e.g., through an intermediate city or cities to a remotely connected city). Question: What is the fewest number of power plants that can be placed such that all cities receive power, and what is one such configuration? Corresponding graph problem: Minimum Dominating Set. Reduction: Let each city be represented by a node in a graph, and let each direct power line connection between 2 cities be represented by an edge connecting the corresponding vertices in the graph. A minimum dominating set in this graph is a set of vertices such that every vertex not in S is adjacent to some member of S. If power plants are built in each of the cities corresponding to a vertex in S, every city will either contain a power plant, or be directly connected via power lines to a city that contains a power plant. Since S is a minimum dominating set, it contains the fewest number of vertices (power plants) possible for a dominating set. Thus any minimum dominating set S is a solution to this problem, and represents a possible configuration of power plants. Problem: Computer network routing with minimum latency. Consider a computer network which consists of a number of switches and computers, some of which are connected to each other via network links (Cat5 cables, wireless connections, etc.). Suppose each network link has certain transmission latency associated with it. Question: Given any two computers that wish to communicate, what is the series of intermediate switches that a packet must travel through such that the total transmission latency is minimized? Corresponding graph problem: Shortest path. Reduction: Let each computer and switch be represented by a node in a graph, and let the network links be represented by edges, and let each edge be weighted according to the transmission latency of the associated network link. Given any two computers, the problem can be solved by finding the shortest path in the graph between the nodes that represent those computers. This shortest path will contain the switches through which a packet can be transmitted such that the total transmission latency is minimum, thus it represents the solution to the original problem. Problem: Project scheduling. Consider a large project undertaken by a firm (for instance, a large piece of software). The project can be broken into a number of smaller tasks, some of which have prerequisites (can only be started after another task/tasks is/are completed). Suppose each task has a known estimated time for completion. Assume that the firm has enough resources to execute many tasks concurrently, assuming that all prerequisites have been met. Question: How long will the project take (e.g. how long will it take to complete all tasks)? Corresponding graph problem: Longest path. Reduction: Let the completion of each task be represented by a vertex in a graph. Also add a vertex to represent the start of the project (call it vertex S), and one to represent the end of the project (vertex E). If some task B has some task A as a prerequisite, add a directed edge from the vertex representing task A to the vertex for task B, and weight that edge with the time for completing task B. Also add directed edges from vertex S (the start vertex) to the vertices for all tasks that have no prerequisites (that can be started immediately), and weight them with the time for completing the corresponding task. Also add directed edges from vertices for terminal tasks (tasks that no other tasks rely on as prerequisites) to vertex E (the end vertex), all of weight 0. Now, the amount of time the project will take is the longest path from vertex Sto vertex E. This longest path represents the chain of tasks, each of which has the previous task as a prerequisite, such that the time for completing all of these tasks is maximal. Since it is the longest path, there is no other sequence of tasks that will take longer. Also, the project cannot be completed in less time than this sequence of tasks. This is because the last task in the path before vertex E must be completed, and since it relies on the task before it to be completed before it, that task must also be completed. This reasoning can be iterated back to the first task with no prerequisites, which will be started immediately. Since none of these tasks can be omitted, and they must all be completed in serial order, this sequence of tasks in the longest path will dictate the time span of the project. Problem: Video surveillance: A grocery store wants to have a camera recording activity on every aisle in the store. Only one camera is required to cover an aisle. The store owner wants to buy the least amount of cameras to accomplish this task. Corresponding graph problem: Minimum Vertex Cover: for an undirected graph, the minimum subset of vertices such that each edge has at least one endpoint in the subset (i.e. for each edge in the graph, one of its vertices must be an element of the vertex cover). Reduction: The aisles in the grocery store are the edges and the vertices represent intersections. The Minimum Vertex Cover of this graph will be the fewest number of cameras the store owner can place at aisle intersections in order to monitor activity on each aisle. Problem: School bus route: A school bus driver boards his/her school bus at the elementary school in the morning. The driver must stop at every bus stop on his/her route to pick up school children, and at the end of his/her route, drop the children off at school. Corresponding graph problem: Hamiltonian Cycle: a cycle in an undirected graph which visits each vertex exactly once and also returns to the starting vertex. Reduction: The school bus driver's graph is composed of his/her predefined bus stops and route. Each bus stop is a vertex in the graph and the roads are edges. The starting and ending vertex is the elementary school. The bus driver is required to visit every bus stop and he/she cannot visit a bus stop more than once because that would deviate from the predefined route. Problem: Scavenger hunt: A professor sets up a scavenger hunt for his students by placing the hunted items around the university campus. He then gives the list of items to be hunted to the students. The students are required to find every item. Corresponding graph problem: Hamiltonian Path: a path in an undirected graph which visits each vertex exactly once. Reduction: Each hunted item is a vertex in the graph and the routes around campus are edges. Students must visit each vertex in order to find every item on the scavenger hunt list. It is pointless for students to return to an item they have already found