## Friday, April 07, 2006

### Art of formulating a problem

I have not posted for a few days, I have been sick, mostly.

There is an art to formulating algorithmic problems from applied areas. For example, an applied problem is the following. We have a set of edges over time showing the communication between nodes. Intuitively, we would like to determine which group of nodes form a "group" or a "community".

One way to formalize it is to collapse the multiple edges between pairs of nodes into single edges, and find subset S of nodes that communicate with each other a lot (more than expected, or with others outside the set). This formulation quickly leads one to the k-subgraph problem which is hard to solve. There is a nice note on the complexity of finding such a community and its variants by Ara Hayrapetyan, David Kempe, Martin Pál and Zoya Svitkina.

An alternate notion of a community is found in a note by J. Baumes, M. Goldberg, M. Magdon-Ismail and W. Wallace, where the time is segmented into periods, and in each period i, a graph of communication G_i is constructed by collapsing multi-edges. Then the problem is posed as one of finding a subset of nodes that is connected in each of these graphs. The resulting problem, at least in its simplest form, is quite easy to solve. I like this formulation of the problem.

[Unfortunately, for every easy formulation, there is a hard variant.]