Answer Happy

Exercise 7 (8 pts). The ladder of height k is defined to be the graph on 2k nodes such, that . It can be separated into two parts, each one containing k nodes and being a line graph, • We can number nodes in each line from 1 to k in such a way that there is an edge from node i in one line to node i in another line (see fig. 2) The ladder problem is defined as follows: • Input: An undirected graph G and a number k. • Question: Does G contain a subgraph that is the ladder of height k? Is the 7-step ladder variant of this problem in P? In other words is this problem in P if we are looking for a ladder of height 7 in any given input graph. Which one is the correct answer to this question: 'yes', 'no' or 'unknown' (assuming P + NP)? You must justify your answer (if your answer is "yes", briefly describe a polynomial-time algorithm, if your answer is 'no' or 'unknown' please explain why do you think so). 12 k 12 k Figure 2: Graph for Exercise 7