s Journal publications

An O(ck n) 5-Approximation Algorithm for Treewidth (SIAM Journal on Computing, TA) — Hans L. Bodlaender, Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk
Exploring the Subexponential Complexity of Completion Problems, ACM Transactions on Computation Theory (TOCT) — Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger
On the Computational Complexity of Vertex Integrity and Component Order Connectivity, (Algorithmica, TA) — Pål Grønås Drange, Markus Dregi, Pim van't Hof

Conference proceedings

Kernelization and Sparseness: the case of Dominating Set (STACS 2016, TA) (arXiv preprint) — Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Saket Saurabh, Fernando Sánchez Villaamil, and Somnath Sikdar
Compressing bounded degree graphs (LATIN 2016, TA) (preprint) — Pål Grønås Drange, Markus Dregi, and R. B. Sandeep
Fast Biclustering by Dual Parameterization (IPEC 2015) — Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, Somnath Sikdar
A Polynomial Kernel for Trivially Perfect Editing (ESA 2015) (arxiv preprint) — Pål Grønås Drange and Michał Pilipczuk
On the Threshold of Intractability (ESA 2015) (arxiv preprint) — Pål Grønås Drange, Markus Dregi, Daniel Lokshtanov, and Blair D. Sullivan
On the Computational Complexity of Vertex Integrity and Component Order Connectivity (ISAAC 2014) (arxiv preprint) — Pål Grønås Drange, Markus Dregi, and Pim van't Hof
Exploring Subexponential Parameterized Complexity of Completion Problems (STACS 2014) (arxiv preprint) — Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger
An O(ck n) 5-Approximation Algorithm for Treewidth (FOCS 2013) (arxiv preprint) — Hans L. Bodlaender, Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk

Popular scientific

Intervjuet i Teknisk Ukeblad
Er du venn med en robot? — Appeared in Morgenbladet, co-authored with Professor Jan Arne Telle
Sådde frøene til datarevolusjonen — Bergens Tidende, 22. juni 2012, co-authored with Professor Jan Arne Telle

Reviewing duty

SIAM Journal on Discrete Mathematics
CSR 2014: subreviewer
ESA 2015: subreviewer
ESA 2015: subreviewer
FSTTCS 2014: subreviewer
FUN 2014: subreviewer
ICALP 2012: subreviewer
IPEC 2015: subreviewer
ISAAC 2013: subreviewer
ISAAC 2015: subreviewer
MFCS 2012: subreviewer
MFCS 2014: subreviewer
WG 2014: subreviewer

PhD thesis

Parameterized Graph Modification Algorithms Abstract:

Graph modification problems form an important class of algorithmic problems in computer science. In this thesis, we study edge modification problems towards classes related to chordal graphs, with the main focus on trivially perfect graphs and threshold graphs. We provide several new results in classical complexity, kernelization complexity, and subexponential parameterized complexity. In all cases we give positive and negative results—giving polynomial time algorithms as well as NP-hardness results, polynomial kernels as well as polynomial kernel impossibility results, and we give subexponential time algorithms, and show that many problems do not admit such algorithms unless the exponential time hypothesis fails.

Our main focus is on the subexponential time complexity of edge modification problems. For that to make sense, we first need to figure out whether or not we actually need super-polynomial time. We show that editing towards trivially perfect graphs, threshold graphs, and chain graphs are all NP-complete, resolving 15 year old open questions. When a problem is shown to be NP-complete, we study exactly how much exponential time is needed for an algorithm to solve it. We provide several subexponential time algorithms, for, e.g., editing towards chain graphs and threshold graphs, as well as completing towards trivially perfect graphs. We complement our results by showing that small alterations in the target graph classes yields much harder problems: Editing towards trivially perfect graphs and cographs is not possible in subexponential time unless the exponential time hypothesis fails.

A first step in our subexponential time algorithms, and an otherwise natural first step in dealing with NP-hard problems is offered by the toolbox of polynomial kernelization. In polynomial kernelizations, we are asked to design polynomial time compression algorithms that shrink the input instances to output instances bounded polynomially in a yes-solution. We provide polynomial kernels for all edge modification problems towards trivially perfect graphs, threshold graphs and chain graphs. In addition, we show that on bounded degree input graphs, we obtain polynomial kernels for any editing or deletion problem towards graph classes characterizable by a finite set of forbidden induced subgraphs. Finally, we show that we should not expect the same result for completion problems by proving that such a compression algorithm would imply the collapse of the polynomial hierarchy.

Cite as Pål Grønås Drange. Parameterized Graph Modification Algorithms. PhD dissertation, University of Bergen, 2015. BibTeX

@phdthesis{drange2015parameterized,
  type = {{PhD} Dissertation},
  title = {Parameterized Graph Modification Algorithms},
  timestamp = {2015-12-10T15:00:00Z},
  school = {University of Bergen},
  author = {Drange, P{\aa}l Gr{\o}n{\aa}s},
  year = {2015}
}

Master thesis

Epistemic Effectivity: Neighbourhood Semantics for Coalitional Ability and Group Knowledge (PDF) Abstract:

In this thesis, we investigate coalitional ability under imperfect knowledge. Coalitional ability is a measure of how powerful a group of agents are, in terms of which outcomes they can achieve in some game. This has been studied using effectivity functions, which has a very natural interpretation in neighbourhood semantics in modal logic. On the other hand, coalitional ability under imperfect knowledge has been studied in great details recently in a variety of papers, but not in the context of effectivity functions and neighbourhood semantics.

A very natural question to ask is “what is a coalition effective for under imperfect knowledge?”. In this thesis we study that question and analyse the problem using effectivity functions, named epistemic effectivity functions. The main result is a representation theorem, completely characterising the effectivity functions corresponding to epistemic game structures under a variant of α-effectivity that uses distributed knowledge. Along the way, we also give a new neighbourhood semantics for standard epistemic logic with different variants of group knowledge which turns out to be very natural and intuitive.

Talks

Empirical Hardness Models, Department seminar, trial lecture. Bergen, Norway (October 2015)
Fast Biclustering, Algorithm Seminar Series. Bergen, Norway (October 2015)
Fast Biclustering by Dual Parameterization, ESA 2015. Patras, Greece (September 2015)
A polynomial kernel for Trivially Perfect Editing, ESA 2015. Patras, Greece (September 2015)
On the square root phenomenon of chordal graphs, NICTA Algorithm series. Sydney, Australia (March 2015)
The computational complexity of Threshold Editing, Workshop on Graph Decomposition, CIRM. Marseilles, France (January 2015)
Computational Complexity of Component Order Connectivity, ISAAC. Jeonju, South-Korea (December 2014) (slides)
Parameterized Complexity – A Primer (slides), Workshop in Honour of Hans Birger Drange on His 70th Birthday. Bergen, Norway (April 2014)
Subexponential Parameterized Complexity of Completion Problems, STACS. Lyon, France (March 2014)
Subexponential Graph Modification, Algorithms seminar series, University of Bergen. Bergen, Norway (February 2014)
What is Algorithm Research, talk for the new bachelor students at the Department of Informatics, University of Bergen. Bergen, Norway (August 2013)
A randomized polynomial kernel for Odd Cycle Transversal, Algorithms seminar series, University of Bergen. Bergen, Norway (February 2012)
Three representation theorems for S5[E,D,C], Logic group. Bergen, Norway (June 2011)
Completeness of S5 with common knowledge, Logic group. Bergen, Norway (September 2010)
Complexity of Cooperative Solution Concepts, ILLC. Amsterdam, the Netherlands (May 2010)