7. Marcin Pilipczuk, Michal Ziobro
Experimental Evaluation of Parameterized Algorithms for Graph Separation Problems: Half-Integral Relaxations and Matroid-based Kernelization
We experimentally evaluate matroid-based kernelization and FPT algorithms based on half-integral relaxations for Odd Cycle Transversal and Multiway Cut.
6. Wojciech Nadara
Experimental evaluation of kernelization algorithms to Dominating Set
We experimentally evaluate sparsity-based reduction rule for the classic Dominating Set problem.
5. Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
We experimentally evaluate two basic building blocks in sparse graph classes: weak coloring numbers and uniform quasi-wideness.
4. Krzysztof Kiljan, Marcin Pilipczuk
Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set
We evaluate parameterized algorithms for the Feedback Vertex Set problem, aiming at deeper understanding of the results of Parameterized Algorithms and Computational Experiments Challenge 2016.
3. Michał Ziobro, Marcin Pilipczuk
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
We evaluate algorithms for Hamiltonian Cycle on graphs of bounded treewidth. We find out that many instances of the recent Flinders Hamiltonian Cycle Challenge have small treewidth, and the dynamic programming algorithm based on improved rank-based approach has advantage solving them.
A Deterministic Polynomial Kernel for Odd Cycle
Transversal and Vertex Multiway Cut in Planar Graphs
We show that Vertex Multiway Cut admits a polynomial kernel in planar graphs, extending the framework for kernelizing Planar Steiner Tree to vertex-deletion problems in planar graphs.
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
We show that the Long Path problem admits a polynomial Turing kernel in graphs excluding a fixed graph as a topological minor, significantly broadening the range of graph classes for which such a kernel is known. Furthermore, our kernelization algorithm can also cope with a bounded-in-parameter modulator to the required graph class.