Name
Abstract | ||
|---|---|---|
In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things: We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G)≤k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O *(f(k)). The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00224-009-9167-9 | Theory Comput. Syst. |
Keywords | Field | DocType |
improved fixed-parameter tractable,parameter treewidth,general interest,parameterized complexity,connected graph,large number,bounded max leaf number,max leaf number ml,graph problem,complexity ecology,maximum number,natural computing,polynomial time,spanning tree,optimization problem | Kernelization,Discrete mathematics,Combinatorics,Computational problem,Parameterized complexity,Tree-depth,Connected dominating set,Vertex cover,Spanning tree,Treewidth,Mathematics | Journal |
Volume | Issue | ISSN |
45 | 4 | 1432-4350 |
Citations | PageRank | References |
25 | 0.95 | 38 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Daniel Lokshtanov | 2 | 1438 | 110.05 |
| Neeldhara Misra | 3 | 341 | 31.42 |
| Matthias Mnich | 4 | 253 | 25.44 |
| Frances A. Rosamond | 5 | 684 | 34.52 |
| Saket Saurabh | 6 | 2023 | 179.50 |