Reduction to longest path from longest chain of tiles

Question

We have some tiles that each tile has 2 number written on it. We can rotate each tile in order to swap the position of numbers. We want to find the longest chain of tiles starting with a certain tile so that adjacent tiles have the same number on their common endpoint. If the tiles were

 7-4, 11-8, 11-11, 4-2, 7-5, 11-10, 10-5

the longest chain starting with tile 11-8 would be:

8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2

I tried to reduce this problem to the longest path problem:

• Consider every tile as a vertex.
• If two tiles have a common number in them they are adjacent.
• create a sink vertex and connect it to every other vertices.

the resulting adjacency list of graph is:

7-4  : 4-2, 7-5, sink
11-8 : 11-11, 11-10, sink
11-11: 11-8, 11-10, sink
4-2  : 7-4, sink
7-5  : 7-4, sink
11-10: 11-8, 11-11, sink
10-5 : 11-10, 7-5, sink

Now for finding the longest chain starting vertex 11-8 you simply have to find the longest simple path form 11-8 to sink which is 8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2.

But I am being told that in order to say that this problem is reducible to longest path problem I have to prove it the other way around. It means I have to prove that every graph can be represented by some configuration of tiles. However I know that some graphs can't be represented by tiles for example the below graph couldn't be represented by any such tiles.

A-----B 
|   / |
| /   |
C-----D

So technically my approach is wrong. But I wonder, I have shown that in general you have to solve the longest path problem to find the longest chain of such tiles, why isn't it enough to show that this problem can't be solved in polynomial time? Why is it necessary to show that all the graphs can be represented by a combination of such tiles?

Answer 1

But I wonder, I have shown that in general you have to solve the longest path problem to find the longest chain of such tiles

Not exactly, you have given a way of finding the longest chain of tiles (transform the tiles into a graph and solve longest path). There are many other possible approaches (you can try to transform it into a boolean formula and solve a SAT instance).... how do you know that none of them is easier? You could also use undecidable problems to solve your tile question (build a turing machine that halts iff the tiles have a solution of some size), it doesn't mean that your problem is undecidable.

Reductions work the other way around. I like to see an NP-hard problem as "a tool that may be used to solve any other NP problem". So you need to show that your tile problem is one possible tool for solving longest path. That is, you are given a graph, and you need to describe a set of tiles with the good property (the tiles have a length-k solution iff the graph has a length-k path). This way, you know that your tile problem is a new possible tool for solving longest path, and, in turn, every other NP problem.

PS: there are also errors in the reduction you describe, beside the method problem discussed here: if the same integer appears in three different tiles (say, 4-2,4-7,4-9), then theses three nodes would form a valid path in the graph, but not a valid sequence of tiles. You'll find it easier to see a tile as an edge rather than a vertex

Answer 2

It is much simpler to prove that your problem is NP-hard by reducing it from another problem than longest path problem. It's name is longest trail problem and you are asked to find the longest path in an undirected graph such that no edge is repeated. Note that in longest path problem, no vertex is repeated.

So, given a longest trail problem, every edge corresponds to a tile in your problem. And longest chain in your problem, corresponds to the longest trail in the graph.

See this question, for NP-hardness proof of longest trail problem.

So, if you can solve your problem in polynomial time, you can also solve longest trial problem in polynomial time. However, since longest trial problem is NP-hard, this is not possible unless P = NP. Therefore, we proved that your problem is also NP-hard.

Note that you should always reduce from a problem that you know NP-hard to the problem that you want to prove that is NP-hard.