Q5) & Q6) Agent Ω Solution

Q5): In like a Lion, Out on the Lam Solution

Description

Background: The Lion is preparing to launch his final assault to take over Mars, but Agent Ω has isolated all of the remaining locations with C.H.I.M.E.R.A. operatives - she needs to stike first.  She has a graph of all of the bases and their communication channels.  If she can hit at least one base on either side of each channel she’ll be able to completely take down C.H.I.M.E.R.A. and send the Lion on the run.  She has a limited number of agents to use, though, so she needs to strike at as few bases as possible.

This is the Vertex Cover problem!  Unfortunately Vertex Cover is NP-Complete and Agent Ω may be working with a large graph and too short of a timetable to code a fast solver.  But all hope is not lost, since she DOES have an amazingly fast solver for the K-Clique problem.

Problem: You must convert instances of the Vertex Cover problem to K-Clique such that it always returns the same YES/NO answer.

The conversion is easy. If you convert your K to N - K (that is, looking for the opposite of the vertex cover), you will have converted to the independent set problem. Then if you toggle all edges (that is, remove all edges that were present and add in all of the edges that were originally missing) to produce the complement graph, you will have converted from the independent set problem to the Clique problem. Once these conversions are done, you merely need to output the resulting problem instance.

Input Format

The first line contains three values, N, M, K. 

N is the number of vertices in the graph (with IDs 0 through N - 1)
M is the number of edges in the graph
K is the number of vertices being tested for
The next M lines each describe an edge with two values indicating the IDs of the vertices being connected.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ K ≤ N
Output Format

You must output the converted problem instance for the K-Clique problem that would have the same YES/NO answer as the original vertex cover problem. Otherwise, it should have the same format as the input.

NOTE: Each edge pair must have the lower ID first and be sorted in numerical order.

Example 0

Sample Input

5 6 3 

0 1 

0 2 

0 4 

1 4 

2 3 

2 4

Sample Output

5 4 2 

0 3 

1 2 

1 3 

3 4

Explanation

There are 5 vertices and 6 edges in the input graph; the question asks if 3 vertices can cover the graph.

To change this to independent set, we simply need to ask if the same graph has an independent set of size (5 - 3) = 2.

THEN to change this problem to K-Clique, we have to turn off the existing edges and turn on the ones that were missing in the original graph. There are (5 x 4 / 2) = 10 possible edges; 6 of them were in the original graph, but 4 were missing. We list only those four missing edges in out output.

Example 1

input01.txt

output01.txt

Example 2

input02.txt

output02.txt

 

Q6) Agent Ω: The Lion Flees Tonight (EXTRA CREDIT)

Gradescope link

Description

Background: Agent Ω’s plan succeeded and as expected the Lion fled before all of the bases fell.  He used a ship to get to a giant and well armed “panic satellite”.  Before hunkering down, he is racing to a series of other satellites for extra supplies and then coming back.  If Agent Ω can figure out what order he’s going to them in, she may be able to stop him before he’s ready for his last stand.

Going through the C.H.I.M.E.R.A. computer systems, Agent Ω determines which satellites are close enough together to travel between and a set of possible cycles that the Lion should choose from.  Some of those cycles are not valid, however!  Can you go through these cycles to determine which of them are legal possibilities?

Problem: You must write a program that takes an input graph and a set of output cycles, and then verifies if each one is correct or not.

Input Format

The first line contains N and M, the number of vertices and the number of edges in the input graph, respectively.
The next M lines each describe an edge, providing the IDs of the two vertices it connects.
The next line provides T, the number of test cycles.
The final T lines each provides a test cycle with N vertex IDs in the proposed order of traversal.
Constraints

5 ≤ N ≤ 1,000
5 ≤ M ≤ 50,000
1 ≤ T ≤ 10
0 ≤ vi < N (for all vi, as vertex IDs)
Output Format

T lines, each with the word “YES” or “NO”, indicating whether the associated test cycle is valid.  A valid cycle must be able to go through every vertex exactly once using only valid edges, and be able to loop back to the start.

Example 0

Sample Input

5 6

0 2

0 3

1 3

1 4

2 4

3 4

3

1 3 0 2 4

0 1 2 3 4

2 0 3 1 4

Sample Output

YES 

NO 

YES 

Example 1

input01.txt

output01.txt

Example 2

input02.txt

output02.txt

Example 3

input05.txt

output05.txt