An Organic View of Computational Complexity

"How are we able to have this conversation?''

For one thing, the reader of this discussion is processing strings of symbols over an alphabet of 26 distinct kinds (not 10,000) and making making new associations between three or four ideas concurrently (not 5000). Our natural intuitions about the complexity of information processing tell us that these relatively small parameters of the situation make a big difference in our ability to accomplish the task (of reading). Similarly, small structural parameters can make an enormous difference in the ability of computer algorithms to process information. These parameters may describe the number of tracks in the layout plan for a microcircuit, the number of genes in an evolutionary family, or the number of processors to be scheduled. Frequently these numbers are also in the range of 10 or 20 or 50 for realistic applications.

It's not just a matter of being clever enough. Some problems, such as factoring an integer into primes, appear to be intrinsically resistant to any kind of efficient information chemistry. (As lemonade can be made from lemons, this is actually useful: internet commerce via cryptographically secure communications depends on computational intractability, the impossibility of any efficient solution). The tragedy of the mathematical theory of computing is that there are thousands of natural and important computational problems that, like factoring, appear not to admit any efficient general means of solution. But wait ---

What do we mean by "efficient''? In the theoretical framework for computer science that has emerged over the first few decades of this new discipline, the basic definitions are one-dimensional: attention is focused on the cost of information processing as a function solely of the {\em overall input length}. This makes sense if the input is random or arbitrary and does not have any hidden or implicit structure. But as we have suggested, we seem to be able to read and write (and accomplish many other computational tasks) because the information processing problem involved is governed by parameters and structures of modest size, even though the total length of the input to be processed is much longer.

This is the main intuition and issue addressed by the subject of designing fixed-parameter algorithms in the parameterized complexity framework, which introduces a two-dimensional analysis, where one dimension (as classically) is the overall input length, and where the other dimension represents the restricted structure of the realistic situation (the relevant "problem parameter(s)''). The goal is to confine any explosive computational costs to a function only of the (relatively small) parameter(s). This relatively new research program is showing very wide-ranging successes in addressing in this way the computational challenges that face us, in confronting the thousands of computational problems that appear to be (one-dimensionally) quite hard.

Numerous recent working algorithms in computational biology and bio-informatics (e.g., genome and proteome analysis) are based on these new ideas about designing useful algorithms by exploiting natural problem parameters. Bio-informatics continues to be an area of exciting successes for the field. The Dagstuhl workshop brought together algorithms and complexity theorists, as well as implementors and applications-oriented researchers. We anticipate, from the collaborative connections made at Dagstuhl Castle, that the richly developing toolkit of mathematical ideas for designing and analyzing parameterized algorithms, will continue to move quickly into practical deployment.

The seminar on Fixed-Parameter Algorithms brought together researchers from around the world to share their experiences in developing algorithms for a wide range of application areas (e.g. computational biology, graph theory, and motion planning) using diverse approaches. Many of the results presented at the workshop were improved algorithms for classic fixed-parameter problems such as Vertex Cover. The workshop brought to focus how new techniques, such as automated generation of search trees or crown rules and duality, can lead to "feasible in practice'' fixed-parameter algorithms.

Several talks discussed implementations capable of solving these problems on graphs with more than 2000 vertices! The design of general schemes for the distributed computation of search trees, automating the identification of good reduction rules, amortized analysis of the behavior of fixed-parameter algorithms, and the relationship between approximation and fixed-parameter complexity were identified as strong areas of interest in the near future.

In order to take advantage of the diversity of expertise and to foster new research collaborations, a portion of the seminar time was set aside for active research, as detailed below in the section on training. At least one of the results presented at the meeting arose from new collaboration that started at the last Dagstuhl meeting on parameterized complexity, two years ago.

In order to facilitate working relationships among senior and junior participants, we scheduled the talks to allow for extra active working sessions of two types.

In his opening session, Mike Fellows presented a series of challenges for the participants, both long-term and short-term ideas for future work. Two specific problems were identified for immediate work; the goal was to come up with the fastest possible fixed-parameter algorithms for packing of k disjoint three-stars (a problem known to have fixed-parameter algorithms) and for planar directed feedback vertex set (a problem whose status is still unresolved). Early in the week, we scheduled an afternoon session for work on the packing problem, where researchers shared their partial results and then broke into small groups for further progress.

During another session, researchers were asked to present open problems for further work by small groups. The problems ranged in application area as well as technique. Researchers then gathered in small groups to join forces in solving the problems; groups resulted in new working partners, senior researchers alongside junior ones, each contributing using different approaches. Further "cross-fertilization'' took place in the summary meeting on the last day, where progress reports were made by all the groups. The impact of the seminar will be felt in years to come, as results are found and collaborations continue.