Two Algorithmic Problems

Sometimes, an applied problem brings up a technical problem, simple or not, and it is fun. Here are two examples (from social networks):

• Given an undirected graph G, output a set S of vertices (the neighbor-dominating set) so that each edge should have at least one common neighbor in S if the endpoints are not in S. This sounds related to vertex cover, dominating set etc., and there is a simple log approximation possible. The problem arose in an interesting proposal for decentralized social networks (as opposed to centralized ones like facebook) by my colleagues Lu Han, Liviu Iftode and Badri Nath of Rutgers CS and the paper will appear in the upcoming Social Computing 2011 conference.
• Given a directed graph G, determine a mapping r from vertices to set of integers such that sum_{(u,v)\in E} max(r(u) − r(v) + 1,0) is minimized. The interpretation is as follows (and arose due to the work of my collagues Mangesh Gupte, Liviu Iftode and Pravin Shankar of Rutgers CS and REU visitor Jing Li): In social networks, where nodes are aware of their ranks, higher rank nodes are less likely to connect to lower rank nodes. Hence, directed edges that go from lower rank nodes to higher rank nodes are more prevalent than edges that go in the other direction. In particular, if r(u) < r(v) then, edge u → v is expected and does not cause any “agony” to u. However, if r(u) ≥ r(v), then edge u → v causes agony to the user u and the amount of agony depends on the difference between their ranks. We posit that the agony caused to u by each such reverse edge is equal to r(u) − r(v) + 1 (+1 is for technical reasons). Then the problem of finding best social hierarchy can be stated as above. Unlike a related way to formalize this problem as feedback arc set problem, this problem is solvable in polynomial time as we show in the paper that appears in WWW 2011.