More-efficient computation: Finding local solutions to overwhelmingly complex problems

March 31, 2011 by Larry Hardesty
Graphic: Christine Daniloff

At a time when the Internet puts an untold amount of information at anyone’s fingertips, and automated scientific experiments churn out data faster than researchers can keep up with it, and communications networks can include billions of people, even the simplest computational tasks can become so enormous that they would overwhelm even a powerful supercomputer. But sometimes it’s enough to know just a little bit about the solution to a monstrous calculation: biologists mining genomic data, for instance, might be interested in just a handful of genes.

At the Innovations in Computer Science conference at Tsinghua University earlier this year, MIT researchers, together with colleagues at Tel Aviv University, presented a new mathematical framework for finding such localized solutions to complex calculations. They applied their approach to some classic problems in computer science, which involve mathematical abstractions known as graphs.

The most familiar example of a graph is probably a diagram of a , where the nodes of the network — the communications devices — are depicted as circles, and the connections between them are depicted as lines. A graph is any such combination of circles and lines, or, as mathematicians say, of vertices and edges. A flow chart is another example of a graph; or a graph could depict citations of scientific papers, where every vertex is a paper, connected by edges to the papers that cite it.

Graphs can represent an endless diversity of data, but for any given graph, it’s often useful to compute what’s called a maximal independent set. An independent set is one where enough vertices have been deleted from the graph that there are no longer any edges: the remaining vertices are desert islands, none connected to any other. An independent set is maximal if trying to restore any of the deleted vertices will also restore an edge. That is, every vertex left out of the set is connected to one of the vertices in the set.

Community representatives

Each vertex in a maximal independent set thus stands in for a cluster of connected vertices. If the graph represents a mesh of citations, for instance, a cluster could be a set of papers on related topics.

A graph could have many different maximal independent sets, and for a large enough graph, computing even one of them could be a prohibitively time-consuming chore. Ning Xie, a graduate student in the Department of Electrical Engineering and Computer Science; his advisor, computer science professor Ronitt Rubinfeld; and Shai Vardi and Gil Tamir of Tel Aviv University devised a method to efficiently determine, for a particular region of a graph, which vertices are and are not included in at least one of the graph’s maximal independent sets. The key to the researchers’ system is that, without having to specify the entire set, they can guarantee that applying their algorithm to a second region of the — or a dozen or a hundred other regions — will yield results consistent with the first.

The researchers’ paper is theoretical: the researchers don’t apply their algorithm to any particular problems. But problems in research areas as diverse as bioinformatics, chemistry, artificial intelligence, scheduling and networking have been characterized as problems of calculating independent sets.

Seshadhri Comandur, a researcher at Sandia National Labs in Livermore, Calif., points out that — as the researchers acknowledge in their paper — others have previously proposed particular algorithms for calculating local solutions of complex problems. “There have been lots of related concepts that have been sort of floating around,” he says, but the MIT and Tel Aviv researchers “have formalized it in an interesting way and, I think, the correct way.” He adds that he’s intrigued to see whether other local-computation algorithms can also be subsumed under the researchers’ new framework. “There are a lot of other results that have a similar flavor,” he says.

This story is republished courtesy of MIT News (, a popular site that covers news about MIT research, innovation and teaching.

Explore further: Fundamental algorithm gets first improvement in 10 years

Related Stories

Fundamental algorithm gets first improvement in 10 years

September 27, 2010

The maximum-flow problem, or max flow, is one of the most basic problems in computer science: First solved during preparations for the Berlin airlift, it’s a component of many logistical problems and a staple of introductory ...

Minimizing communication between cores

February 28, 2011

In the mid-1990s, Matteo Frigo, a graduate student in the research group of computer-science professor Charles Leiserson (whose work was profiled in the previous installment in this series), developed a parallel version of ...

New standard proposed for supercomputing

November 15, 2010

A new supercomputer rating system will be released by an international team led by Sandia National Laboratories at the Supercomputing Conference 2010 in New Orleans on Nov. 17.

Explained: Ad hoc networks

March 10, 2011

In recent years, many network scientists have turned their attention away from centralized networks — such as the Internet and the cell-phone network -- and toward ad hoc networks, wireless networks formed on the fly ...

Chart junk? How pictures may help make graphs better

November 4, 2009

Those oft-maligned, and highly embellished, graphs and charts in USA Today and other media outlets may actually help people understand data more effectively than traditional graphs, according to new research from North Carolina ...

Recommended for you

WhatsApp vulnerable to snooping: report

January 13, 2017

The Facebook-owned mobile messaging service WhatsApp is vulnerable to interception, the Guardian newspaper reported on Friday, sparking concern over an app advertised as putting an emphasis on privacy.

US gov't accuses Fiat Chrysler of cheating on emissions

January 12, 2017

The U.S. government accused Fiat Chrysler on Thursday of failing to disclose software in some of its pickups and SUVs with diesel engines that allows them to emit more pollution than allowed under the Clean Air Act.

1 comment

Adjust slider to filter visible comments by rank

Display comments: newest first

5 / 5 (1) Mar 31, 2011
Graph theory FTW! It's always great to know about new developments. These guys are in the trenches battling the NP-Hard monster every day!

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.