World's most popular travel blog for travel bloggers.

[Solved]: Reduction to longest path from longest chain of tiles

, , No Comments
Problem Detail: 

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?

Asked By : sudomakeinstall2

Answered By : tarulen

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback