Juho Lauri

Juho Lauri

My main focus areas are graph theory (e.g., coloring), algorithms (e.g., parameterization), and complexity (e.g., lower bounds). I also enjoy programming and solving computationally difficult problems in practice.

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

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

Email juho.lauri@nokia-bell-labs.com


With Sourav Dutta

Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems

Proceedings of 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1.

With Pinar Heggernes, Davis Issac, Paloma T. Lima, Erik Jan van Leeuwen

Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, United Kingdom, August 27-31, pp. 83:1-83:13, 2018.

With Petteri Kaski, Suhas Thejaswi

Engineering Motif Search for Large Motifs

Proceedings of the 17th International Symposium on Experimental Algorithms, SEA 2018, L'Aquila, Italy, June 27-29, pp. 28:1-28:19, 2018.

With Mikko Koivisto, Petteri Laakkonen

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

Proceedings of the 23rd Annual International Computing and Combinatorics Conference, COCOON 2017, Hong Kong, China, August 3-5, pp. 333-345, 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

Accepted to Journal of Combinatorial Optimization

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

Discrete Mathematics & Theoretical Computer Science 20(1), 2018.


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: