Average-Case Analysis of Parameterized Problems and Algorithms

• Applicants: Professor Dr. Tobias Friedrich, Ph.D.; Professor Dr. Jiong Guo
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 213251566

• Final Report Year: 2016

Final Report Abstract

During the past few decades, several approaches have been suggested to cope with NP-hard problems. Two of them attracted remarkable attention: parameterizerd algortihms and average-case complexity. This project brought researchers from both communities together to develop a framework of average-analysis of parameterized problems and algorithms. We have introduced natural parameterized average-case complexity classes and presented average-case efficient algorithms for worst-case hard problems. The archetypical hard problem of parameterized complexity is CLIQUE. We show that despite its well-known W[1]-completeness, the problem is “on average” and “typically” in FPT. This holds for homogenous Erdos-Rényi random graphs of all densities and for scale-free Chung-Lu random graphs with power-law exponent β > 2. This shows that a worst-case intractable problem can become efficiently solvable in the average-case case for a wide range of input distributions. Kernelization is a standard parameterized technique for designing efficient algorithms by a preprocessing. CLIQUECOVER is a well-known NP-hard problem, which has no kernel of subexponential size in the worst-case, assuming the Exponential Time Hypothesis. We prove that a standard set of reduction rules reduces the graph completely for random intersection graphs if the edge probability is bounded away from 1. This shows that the expected kernel size can be substantially smaller than known exponential worst-case bounds.

Publications

• Parameterized average-case complexity of the hypervolume indicator. Genetic and Evolutionary Computation Conference (GECCO). (2013), 575–582
  K. Bringmann and T. Friedrich
  
• On the average-case complexity of parameterized clique. Theor. Comput. Sci. 576. (2015), 18–29
  N. Fountoulakis, T. Friedrich, and D. Hermelin
  (See online at https://doi.org/10.1016/j.tcs.2015.01.042)
• On the kernel size of clique cover reductions for random intersection graphs. J. Discrete Algorithms 34. (2015), 128–136
  T. Friedrich and C. Hercher
  (See online at https://doi.org/10.1016/j.jda.2015.05.014)
• Parameterized clique on inhomogeneous random graphs. Discrete Applied Mathematics 184. (2015), 130–138
  T. Friedrich and A. Krohmer
  (See online at https://doi.org/10.1016/j.dam.2014.10.018)