The Algorithm Engineering group has a close relationship with the Optimisation and Logistics group at the University of Adelaide. Last year, The University of Adelaide awarded Tobias Friedrich the honorary title of Adjunct Professor. He is also Partner Investigator of two ARC projects and currently visiting the School of Computer Science within the University of Adelaide. He is giving an invited talk on April 7, 2017.
Place: Room 5.55, Ingkarni Wardli, University of Adelaide
Time: Friday, April 7, 11am
Title: Average-Case Analysis of Parameterized Problems
Abstract: Many computational problems are NP-hard and are therefore generally believed not to be solvable in polynomial time. Additional assumptions on the inputs are necessary to solve such problems efficiently. Two typical approaches are (i) parameterized complexity where we assume that a certain parameter of the instances is small, and (ii) average-case complexity where we assume a certain probability distribution on the inputs. There is a vast literature on both approaches, but very little about their intersection. Nevertheless, combining these two approaches seems natural and potentially useful in practice. The talk presents the following line of results:
- A hierarchy of parameterized average-case complexity classes [2].
- The W[1]-complete problem k-Clique drops to an average-case analog of FPT for homogeneous Erdős-Rényi random graphs of all densities [2] and for inhomogeneous Chung-Lu random graphs with power-law exponent γ>=2 [4, 5].
- The bounded search tree paradigm allows analyzing average-case run times for a very relaxed graph model that only assumes stochastic independence of the edges. This is demonstrated for the parameterized problems k-Clique, Vertex Cover, and Hitting Set [unpublished].
- The Edge Cover Problem has no kernel of subexponential size in the worst- case (unless P=NP). We study a well-known set of reduction rules and prove that random intersection graphs are reduced completely by these rules [3].
- The geometric problem of computing the hypervolume indicator is W[1]-hard in the worst-case, but can be solved in expected FPT-time if the input is distributed at random on a d-dimensional simplex [1].
The presented work is based on joint work with Karl Bringmann (MPI Saarbrücken), Danny Hermelin (U. Ben Gurion), Christian Hercher (U. Flensburg), and Nikolaos Fountoulakis (U. Birmingham).
References:
- Karl Bringmann and Tobias Friedrich. Parameterized average-case complexity of the hypervolume indicator. In Genetic and Evolutionary Computation Conference (GECCO), pages 575–582. ACM, 2013.
- Nikolaos Fountoulakis, Tobias Friedrich, and Danny Hermelin. On the average-case complexity of parameterized clique. Theoretical Computer Science, 576:18-29, 2015.
- Tobias Friedrich and Christian Hercher. On the kernel size of clique cover reductions for random intersection graphs. Journal of Discrete Algorithms, 34:128-136, 2015.
- Tobias Friedrich and Anton Krohmer. Parameterized clique on scale-free networks. In International Symposium on Algorithms and Computation (ISAAC), volume 7676 of Lecture Notes in Computer Science, pages 659-668. Springer, 2012.
- Tobias Friedrich and Anton Krohmer. Parameterized clique on inhomogeneous random graphs. Discrete Applied Mathematics, 184:130-138, 2015.
