I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum clique in the graph which is created with distance matrix.

Knowing that there exists a pattern in the distance matrix can I find the maximum clique more efficiently?

  • $\begingroup$ That would depend on what kind of 'pattern' you have and on the complexity of your 'pattern'. Could you describe what you mean by 'pattern' more clearly? In particular, it would help if you can explain how to construct the distance matrix given the pattern. Also, I don't immediately see why you're looking for cliques to solve your problem. Does the graph your looking for cliques in only have an edge when two nodes have distance at least d? $\endgroup$ – Discrete lizard Jan 23 '18 at 7:51

Although the question lacks some details, I propose my solution to the general version of your problem.

Yes. It really depends on the "pattern" based on which you create the graph. There is an infinite number of patterns. For example, one can propose a simple pattern that makes it easy to find the cliques in linear time:

Pattern 1: There is a link between two vertices if the labels of the vertices are two consecutive numbers. Clique detection algorithm? Simply list the cliques "{1,2}, {2,3}, ..., {n-1, n}".

Pattern 2: There is a link between two vertices if their distance in the original graph is at most two. Clique detection algorithm? Np-hard problem.

  • 1
    $\begingroup$ To me, the only thing we learn from your general version is that the question should be more specific to get meaningful answers. $\endgroup$ – Discrete lizard Jan 23 '18 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.