Juho Lauri

Juho Lauri

I am interested in graph theory (e.g., coloring), algorithms (e.g., parameterization), and complexity (e.g., lower bounds).

I successfully defended my doctoral thesis on 3rd of November, 2016. My opponent was Pinar Heggernes (University of Bergen). I was supported by the Emil Aaltonen Foundation from May 2015 to May 2017.

In May 2017, I joined Bell Labs in Dublin, Ireland as a post-doctoral researcher.

Email juho.lauri@tut.fi


With Mikko Koivisto, Petteri Laakkonen

NP-completeness Results for Partitioning a Graph into Total Dominating Sets

Accepted to COCOON 2017

With N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare

Algorithms and Hardness Results for Happy Coloring Problems


The Square of the 9-hypercube is 14-colorable


With Marzio De Biasi

On the Complexity of Restoring Corrupted Colorings


With Henri Riihimäki

A Tight Upper Bound on the Rainbow Connection Number of Chordal Diametral Path Graphs


With Łukasz Kowalik, Arkadiusz Socała

On the Fine-grained Complexity of Rainbow Coloring

Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark, August 22-24, pp. 58:1-58:16, 2016.

With Łukasz Kowalik

On Finding Rainbow and Colorful Paths

Theoretical Computer Science 628, 2016, pp. 110-114.

Complexity of Rainbow Vertex Connectivity Problems for Restricted Graph Classes

Discrete Applied Mathematics 219, 2017, pp. 132-146.

With Eduard Eiben, Robert Ganian

On the Complexity of Rainbow Coloring Problems

Proceedings of the 26th International Workshop on Combinatorial Algorithms, IWOCA 2015, Verona, Italy, October 5-7, pp. 209-220, 2015.

With Andreas Björklund, Petteri Kaski, Łukasz Kowalik

Engineering Motif Search For Large Graphs

Proceedings of the 17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, California, USA, January 5, pp. 104-118, 2015.

Further Hardness Results on Rainbow and Strong Rainbow Connectivity

Discrete Applied Mathematics 201, 2016, pp. 191-200.

With Melissa Keranen

Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs



Chasing the Rainbow Connection: Hardness, Algorithms, and Bounds

Doctoral thesis, Tampere University of Technology,
Approved with distinction

Rainbow Coloring and Connectivity Problems on Families of Perfect Graphs

Master's thesis, Tampere University of Technology,
Awarded 'Thesis of the Year' by the Finnish Society for Computer Science

Average-case Analysis of Comparison-based Sorting Algorithms Using the Incompressibility Method

Bachelor's thesis, Tampere University of Technology,


I am or have been a teaching assistant for the following courses.

At Tampere University of Technology:

At Michigan Technological University: