Here you can find links to repositories with code developed in the project.
Most of the code has been released under a free license; please check details inside each repository.
title: Weak coloring numbers and uniform quasi-wideness
author: Wojciech Nadara, Marcin Pilipczuk, Felix Reidl, Roman Rabinovich, Sebastian Siebertz
The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary for several important algorithmic questions. We experiment with the two structural properties of these graph classes that are of particular importance in this context, namely the property of having bounded generalized coloring numbers and the property of being uniformly quasi-wide.
title: Hamiltonian Cycle on graphs of bounded treewidth
author: Michał Ziobro, Marcin Pilipczuk
Experimental evaluation of algorithms for Hamiltonian Cycle on graphs of bounded treewidth. In the recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth, including a number of surprising techniques for connectivity problems. We provide an experimental comparison of the naive, rank-based, and Cut&Count approaches for the Hamiltonian Cycle problem.
title: Feedback Vertex Set experiments
author: Krzysztof Kiljan, Marcin Pilipczuk
Experimental evaluation of parameterized algorithms for the Feedback Vertex Set problem. The results of PACE 2016 that on one hand showed large discrepancy between performance of different classic approaches to the problem, and on the other hand indicated a new approach based on half-integral relaxations of the problem as probably the most efficient approach to the problem. Motivated by these results, we provide an exhaustive experimental evaluation of fixed-parameter and branching algorithms for Feedback Vertex Set.
title: Feedback Vertex Set
subtitle: PACE 2016 track B entry
author: Marcin Pilipczuk
An entry by the PI for the track B of the first PACE Challenge: a solver for the classic Feedback Vertex Set problem. The entry has been ranked second, giving ground only to the winning solution of Kensuke and Iwata. It includes a mix of a number of classic parameterized approaches to Feedback Vertex Set: branching on high-degree vertices, suppressing low-degree vertices, solving cubic instances with matroid tools, and an algorithm for bounded treewidth graphs. Please find a number of small test instances in our datasets section.