About Me

My name is Philipp Kuinke and I am currently pursuing my PhD at the Theory Group under advisement of Peter Rossmanith. My research areas include Parameterized Complexity, especially fixed parameter tractability and kernelization, Graph Theory, and exact algorithms for NP-hard problems.

I started my studies of Computer Science at the RWTH Aachen University in 2009, where I got my Bachelor and finally my Master degree in 2016. During that time I worked at various student positions, including first semester mentoring, tutor (Computability and Complexity, Computer Science for Mechanical Engineering), student researcher, and web development for e-learning platforms.

One of my greatest passions is music and in my free time I am member of the University Choir. Another project I am involved in is the Dragon Legion Ev., which tries to establish an international for role-playing network wich focuses on cultural exchange. We are funded by the ERASMUS+ program of the European Union.

Contact Details

Philipp Kuinke



Local Structure Theorems for Erdős-Rényi Graphs and Their Algorithmic Applications.

SOFSEM Jan Dreier, Philipp Kuinke, Ba Le Xuan, Peter Rossmanith2018

We analyze local properties of sparse Erdős–Rényi graphs, where d(n)/n is the edge probability. In particular we study the behavior of very short paths. For d(n)=o(1) we show that G(n,d(n)/n) has asymptotically almost surely (a.a.s.) bounded local treewidth and therefore is a.a.s. nowhere dense. We also discover a new and simpler proof that G(n,d/n) has a.a.s. bounded expansion for constant d. The local structure of sparse Erdős–Rényi graphs is very special, which implies efficient algorithms for subgraph isomorphism, in particular for finding subgraphs with small diameter.

A practical fpt algorithm for Flow Decomposition and transcript assembly

ALENEX Kyle Kloster, Philipp Kuinke, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan, Andrew van der Poel2018

The Flow Decomposition problem, which asks for the smallest set of weighted paths that "covers" a flow on a DAG, has recently been used as an important computational step in transcript assembly. We prove the problem is in FPT when parameterized by the number of paths by giving a practical linear fpt algorithm. Further, we implement and engineer a Flow Decomposition solver based on this algorithm, and evaluate its performance on RNA-sequence data.

Structural Parameterization Beyond Vertex Cover Number

Master Thesis 2016

A polynomial Kernel for Independent Set parameterized by the size of a modulator to bounded components by adapting the framework of Bodlaender and Jansen.