Current status

I’m Pål Grønås Drange, researcher in the the Algorithms group, Department of Informatics, University of Bergen, Norway.

I received my PhD from the University after defending my thesis “Parameterized Graph Modification Algorithms”, which was supervised by Professor Fedor V. Fomin. My scholarship during the PhD period came from Fomin’s ERC Advanced Grant Rigorous Theory of Preprocessing, ERC Advanced Investigator Grant 267959.

I was a PhD student from January 2012 until January 2016. October 5th I handed in my PhD thesis, Parameterized Graph Modification Algorithms and defended this thesis December 10, 2015. See the press release Kunsten å avdekke strukturer i komplekse nettverk (Norwegian) and the disputas announcement.

From February until May 2015, I visited Serge Gaspers at NICTA, Sydney and UNSW in Sydney, Australia. Research interest

My main interest is algorithmic graph theory, parameterized complexity, preprocessing (in the form of kernelization and width parameter analysis) and exact (sub-)exponential algorithms. Especially for graph modification problems.

A graph modification problem is a problem where you are given a graph G and a budget k and you are asked to transform G to some specific target class (usually a graph class characterized by either forbidden minors, or forbidden induced subgraphs), modifying at most k vertices or edges.

Graph classes of particular interest are graphs related to chordal graphs, or graphs omitting P4, C4, C5 or 2K2 as induced subgraphs. Graph classes of these types include (pseudo-)split, threshold and chain graphs, trivially perfect and cographs.

Of results, we have given subexponential exact algorithms for Trivially Perfect Completion, Threshold Completion, and Pseudosplit Completion. (STACS 2014)

We have shown that Trivially Perfect Editing is NP-hard and does not have a subexponential algorithm unless ETH fails, but that it, on the positive side, admits a polynomial kernel (preprint at arXiv).

We have shown that Threshold Editing and Chain Editing are NP-hard, but that on the positive side, they admit quadratic kernels and subexponential algorithms(to appear). The quadratic kernels also hold for the completion and deletion variants.

For a slightly different type of problem, in the area of graph vulnerability, we showed that Vertex Integrity is NP-complete, on cocomparability graphs (even on co-bipartite graphs), thereby refuting a twenty year old conjecture, and that Component Order Connectivity can be solved in lkn time, where l is the size of the largest connected component in the target graph and k is the budget. (ISAAC 2014)

Finally, we showed that there is a single-exponential linear time constant factor approximation for computing the treewidth of a graph, i.e., we can in time O(ctn) time obtain a 5-approximation of the treewidth of an input graph G. (FOCS 2013) Research resources

orcid
arxiv
dblp
cristin

My coauthors

Hans Bodlaender
Markus S. Dregi
Fedor V. Fomin
Stephan Kreutzer
Daniel Lokshtanov
Marcin Pilipczuk
Michał Pilipczuk
Felix Reidl
Saket Saurabh
Fernando Sánchez Villaamil
R. B. Sandeep
Somnath Sikdar
Jan Arne Telle
Pim van 't Hof
Yngve Villanger

Education

I have a PhD from the Algorithms group at the Department of Informatics, University of Bergen.

My bachelor and master degree both come from the University of Bergen, with a short stay at the ILLC at the University of Amsterdam. In 2009, I finished my bachelor degree in Cognitive science and in 2011, I completed my master thesis Epistemic Effectivity: Neighborhood Semantics for Coalitional Ability and Group Knowledge under the supervision of Professor Thomas Ågotnes.