An optimization problem worthy of our attention

[Stephen Tashi]

Perhaps forum members can advance science by solving this optimization problem from The Protein Engineer http://proteneer.com/blog/?p=1557

My statement of it:

Let M be a N x N symmetric matrix such that N is divisible by 3, all the diagonal entries are 0 and each other entry is either 0 or 1. We think of the matrix entry M[j] as representing whether an object i interacts with another object j. Imagine M partitioned into 3x3 submatrices ("tiles"). The "cost" of M is defined as the number of tiles that have at least one non-zero entry. ( I don't undestand the practical reason why the cost is defined that way.)

The information in M can be arranged differently by changing the order in which the objects are listed. (i.e. let s be a permutation of the numbers 1,2,...n and define a new matrix M' to have entries M'[j] = M[s(i)][s(j)] ) Find an algorithm with determines a matrix M' that has minimum cost and contains the same information as the matrix M.

 

[homeomorphic]

Basically, the problem seems to be how do you partition the vertex set of a graph into 3-element sets such that the number of edges within all the partitioning subsets is minimized.

My first thought was, the obvious brute force strategy, where you just compute the cost for each permutation. Since there are a lot of permutations, that's computationally expensive. You can do a little better if you only compute one for each partition, but I think there are still a lot of partitions of a big set into 3-element sets.

A somewhat related problem is this. Say there are n vertices where n is divisible by 3 and let k = n/3. You could then ask whether the graph is k-partite. That would correspond to a cost of zero. My thought was that maybe graph theorists have thought about ways to determine whether a graph is k-partite and that maybe that would help with this problem.

Let's do a special case. Say we have a graph with 6 vertices. Then k = 2 and the question is whether the graph is bipartite, which would correspond exactly to the question of whether you can apply the permutations to the matrix to get a cost of zero. The answer is if and only if there are no odd cycles. It's clear that a bipartite graph can't have odd cycles, but the converse is a little more difficult to prove. As it happens, I was wanting to review that very result and the proof. It's not very hard, and I think it's constructive, so there should be an algorithm.

Anyway, maybe you could consider this problem as an extension of the question of whether something is k-partite. Like, is it k-partite after you remove one edge, two edges, etc. If you had algorithms for that, it might give you algorithms to minimize that cost. Just a thought.

 

[homeomorphic]

Well, of course, there's a big difference here that I forgot about, which is that the size of the partitioning sets has to be 3, but I still wonder if something like that might help.