The list of known NP-Complete problems are Circuit-SAT, SAT, 3-SAT, Clique, Independent Set, Vertex Cover, Set Cover, Hamiltonian Cycle, Hamiltonian Path, Longest Path, and Traveling Salesperson.

Over break, you decide to take a road trip, driving around to see as much of the country as you can. Being environmentally conscious, you are using your electric car for the trip. You have a map showing all cities in the US and want to visit as many as possible without duplicating any stops. At the same time, you need to be careful because your car has a limited range and only certain cities have charging stations. Ths problem is formalized as RoadTrip. You have an unweighted graph, where the vertices represent the cities. Some of the vertices, including your starting point (Galesburg), are marked as having a charging station. The input also includes an integer k. You are asked if it is possible to visit at least k cities in sequence, following the edges and never returning to a city you have already visited. In addition, the sequence cannot go more than 3 cities without visiting a marked city or your car will run out of charge. Note that you aren't required to reach any particular destination or return to Galesburg.

(a) Show that RoadTRIP is in NP.

(b) Give a reduction from one of our known NP-complete problems to RoADTRIP.