INVITATION TO FIXED-PARAMETER ALGORITHMS
CONTENTS I FOUNDATIONS INTRODUCTION TO FIXED-PARAMETER ALGORITHMS THE SATIS?ABILITY PROBLEM AN EXAMPLE FROM RAILWAY OPTIMIZATION A COMMUNICATION PROBLEM IN TREE NETWORKS SUMMARY EXERCISES BIBLIOGRAPHICAL REMARKS PRELIMINARIES AND AGREEMENTS BASIC SETS AND PROBLEMS MODEL OF COMPUTATION AND RUNNING TIMES STRINGS AND GRAPHS COMPLEXITY AND APPROXIMATION PARAMETERIZED COMPLEXITY THEORY—A PRIMER BASIC THEORY INTERPRETING ?XED-PARAMETER TRACTABILITY VERTEX COVER—AN ILLUSTRATIVE EXAMPLE PARAMETERIZING SPECIALIZING GENERALIZING COUNTING OR ENUMERATING LOWER BOUNDS IMPLEMENTING AND APPLYING USING VERTEX COVER STRUCTURE FOR OTHER PROBLEMS THE ART OF PROBLEM PARAMETERIZATION PARAMETER REALLY SMALL? GUARANTEED PARAMETER VALUE? MORE THAN ONE OBVIOUS PARAMETERIZATION? CLOSE TO “TRIVIAL” PROBLEM INSTANCES? SUMMARY AND CONCLUDING REMARKS II ALGORITHMIC METHODS DATA REDUCTION AND PROBLEM KERNELS BASIC DE?NITIONS AND FACTS MAXIMUM SATIS?ABILITY CLUSTER EDITING VERTEX COVER KERNELIZATION BASED ON MATCHING KERNELIZATION BASED ON LINEAR PROGRAMMING KERNELIZATION BASED ON CROWN STRUCTURES COMPARISON AND DISCUSSION 3-HITTING SET DOMINATING SET IN PLANAR GRAPHS THE NEIGHBORHOOD OF A SINGLE VERTEX THE NEIGHBORHOOD OF A PAIR OF VERTICES REDUCED GRAPHS AND THE PROBLEM KERNEL ON LOWER BOUNDS FOR PROBLEM KERNELS 710 BIBLIOGRAPHICAL REMARKS DEPTH-BOUNDED SEARCH TREES HITTING SET CLOSEST STRING DATA REDUCTION RULES MAIN RESULT AND SOME REMARKS INTERLEAVING SEARCH TREES AND KERNELIZATION BASIC METHODOLOGY INTERLEAVING IS NECESSARY AUTOMATED SEARCH TREE GENERATION AND ANALYSIS 810 EXERCISES 811 BIBLIOGRAPHICAL REMARKS DYNAMIC PROGRAMMING KNAPSACK STEINER PROBLEM IN GRAPHS MULTICOMMODITY DEMAND FLOW IN TREES TREE-STRUCTURED VARIANTS OF SET COVER ALGORITHM FOR PATH-LIKE WEIGHTED SET COVER ALGORITHM FOR TREE-LIKE WEIGHTED SET COVER SHRINKING SEARCH TREES 10 TREE DECOMPOSITIONS OF GRAPHS 101 BASIC DE?NITIONS AND FACTS 102 ON THE CONSTRUCTION OF TREE DECOMPOSITIONS 103 PLANAR GRAPHS 104 DYNAMIC PROGRAMMING FOR VERTEX COVER 105 DYNAMIC PROGRAMMING FOR DOMINATING SET 106 MONADIC SECOND-ORDER LOGIC (MSO) 107 RELATED GRAPH WIDTH PARAMETERS 108 SUMMARY AND CONCLUDING REMARKS 109 EXERCISES 1010BIBLIOGRAPHICAL REMARKS 11 FURTHER ADVANCED TECHNIQUES 111 COLOR-CODING 112 INTEGER LINEAR PROGRAMMING 113 ITERATIVE COMPRESSION 1131 VERTEX COVER 1132 FEEDBACK VERTEX SET 114 GREEDY LOCALIZATION 1141 SET SPLITTING 1142 SET PACKING 115 GRAPH MINOR THEORY 116 SUMMARY AND CONCLUDING REMARKS 117 EXERCISES 118 BIBLIOGRAPHICAL REMARKS 12 SUMMARY AND CONCLUDING REMARKS III SOME THEORY, SOME CASE STUDIES 13 PARAMETERIZED COMPLEXITY THEORY 131 BASIC DE?NITIONS AND CONCEPTS 1311 PARAMETERIZED REDUCIBILITY 1312 PARAMETERIZED COMPLEXITY CLASSES 132 THE COMPLEXITY CLASS W [1] 133 CONCRETE PARAMETERIZED REDUCTIONS 1331 W [1]-HARDNESS PROOFS 1332 FURTHER REDUCTIONS AND W [2]-HARDNESS 134 SOME RECENT DEVELOPMENTS 1341 LOWER BOUNDS AND THE COMPLEXITY CLASS M [1] 1342 LOWER BOUNDS AND LINEAR FPT REDUCTIONS 1343 MACHINE MODELS, LIMITED NONDETERMINISM, AND BOUNDED FPT 135 SUMMARY AND CONCLUDING REMARKS 136 EXERCISES 137 BIBLIOGRAPHICAL REMARKS 14 CONNECTIONS TO APPROXIMATION ALGORITHMS 141 APPROXIMATION HELPING PARAMETERIZATION 142 PARAMETERIZATION HELPING APPROXIMATION 143 FURTHER (NON-)RELATIONS 144 DISCUSSION AND CONCLUDING REMARKS 145 BIBLIOGRAPHICAL REMARKS 15 SELECTED CASE STUDIES 151 PLANAR AND MORE GENERAL GRAPHS 1511 PLANAR GRAPHS 1512 MORE GENERAL GRAPHS 152 GRAPH MODI?CATION PROBLEMS 1521 GRAPH MODI?CATION AND HEREDITARY PROPERTIES 1522 FEEDBACK VERTEX SET REVISITED 1523 GRAPH BIPARTIZATION 1524 MINIMUM FILL-IN 1525 CLOSEST 3-LEAF POWER 153 MISCELLANEOUS GRAPH PROBLEMS 1531 CAPACITATED VERTEX COVER 1532 CONSTRAINT BIPARTITE VERTEX COVER 1533 GRAPH COLORING 1534 CROSSING NUMBER 1535 POWER DOMINATING SET 154 COMPUTATIONAL BIOLOGY PROBLEMS 1541 MINIMUM QUARTET INCONSISTENCY 1542 COMPATIBILITY OF UNROOTED PHYLOGENETIC TREES 1543 LONGEST ARC-PRESERVING COMMON SUBSEQUENCES 1544 INCOMPLETE PERFECT PATH PHYLOGENY HAPLOTYP- ING 155 LOGIC AND RELATED PROBLEMS 1551 SATIS?ABILITY 1552 MAXIMUM SATIS?ABILITY 1553 CONSTRAINT SATISFACTION PROBLEMS 1554 DATABASE QUERIES 156 MISCELLANEOUS PROBLEMS 1561 TWO-DIMENSIONAL EUCLIDEAN TSP 1562 MULTIDIMENSIONAL MATCHING 1563 MATRIX DOMINATION 1564 VAPNIK–CHERVONENKIS DIMENSION 157 SUMMARY AND CONCLUDING REMARKS 16 ZUKUNFTSMUSIK REFERENCES