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?