About Me

Currently, I am a postdoc in the group of Dániel Marx at CISPA in Saarbrücken, Germany.
I am a researcher in theoretical computer science, where my main work is in graph algorithms at the intersection of parameterized complexity and counting complexity.

I received my DPhil (PhD) in Computer Science from the University of Oxford in November 2020, where I was very fortunate to be supervised by Leslie Ann Goldberg and Standa Živný. Previously, I received an M.Sc. and a B.Sc. in Mathematics from TU Berlin and TU Dresden, respectively.

Some keywords that fit the scope of my research: Graph Theory, Computational Counting Problems, Parameterized Algorithms and Complexity, Graph Homomorphisms, Multivariate Complexity.

I love to hike, boulder, climb, run, backpack, kayak, ski, and be out in nature in general. There is a lot of music that I passionately listen to, and you can always tempt me with a board game evening with friends.

News

08/2024 TALG paper about approximately counting answers to conjunctive queries (with some extensions, like disequalities), and how tractability relates to the decision problem, to treewidth, and even to fractional hypertreewidth. With Leslie Goldberg, Marc Roth and Standa Živný.
06/2024 Two papers accepted for ESA: One about tight complexity classifications for List Homomorphism Deletion problems; and the other investigating problems that form a common generalization of both classical hitting and packing problems.
04/2024 ICALP accept for our paper on the real source of hardness of fundamental problems on bounded-treewidth graphs. I will present it in Estonia in July.
03/2024 SICOMP paper on counting induced subgraphs together with Marc Roth!
03/2024 PODS accept for our paper on counting answers to unions of conjunctive queries. I will present it in Chile in June.
02/2024 SoCG accept for our paper on Multicut problems in embedded graphs. Florian Hörsch will present it in Athens. We are also happy that this work was invited for the special issue of DCG.
03/2024 New website! ;)
02/2024 Glad to be on the program committee for IPEC 2024, chaired by Édouard Bonnet and Pawel Rzążewski. This means loads of reviewing in July...
01/2024 TALG paper about counting list homomorphisms on graphs with bounded treewidth together with Dániel Marx and Pawel Rzążewski.

Publications

Peer-reviewed

Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, Karol Węgrzycki
Hitting Meets Packing: How Hard Can it Be?
ESA 2024 (to appear) arXiv 2024

Barış Can Esmer, Jacob Focke, Dániel Marx, Paweł Rzążewski
List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs
ESA 2024 (to appear) arXiv 2022

Barış Can Esmer, Jacob Focke, Dániel Marx, Paweł Rzążewski
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
ICALP 2024 (to appear) arXiv 2023

Jacob Focke, Leslie Ann Goldberg, Marc Roth and Stanislav Živný
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
PODS 2024 (to appear) arXiv 2023

Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
SOCG 2024 (to appear) arXiv 2023

Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations

Jacob Focke, Dániel Marx, Pawel Rzazewski
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds

Jacob Focke, Marc Roth
Counting Small Induced Subgraphs with Hereditary Properties

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Counting Homomorphisms to K4-minor-free Graphs, modulo 2

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions to Square-Free Graphs

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Counting Surjective Homomorphisms and Compactions

Jacob Focke, Nicole Megow, Julie Meißner
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments

Thesis

Jacob Focke
On the complexity of counting homomorphisms under surjectivity constraints

Academic Service

I am on the program committee for IPEC 2024.

In summer 2023 I was a lecturer for the Advanced Course Techniques for Counting Problems
(co-organized with Philip Wellnitz).

I reviewed manuscripts for STACS2025, SODA2025, IPEC2024 (PC), ESA2024, WG2024, ICALP2024, STOC2024, SODA2024, ESA2023, WG2023, ICALP2023, STOC2023, SODA2023, SICOMP2023, IPL2023, STOC2022, MFCS2022, TCS2022, Inf&Comp2022, STACS2021, ICALP2021, DM2021, TCS2021, STACS2020, SODA2020, ITCS2020, TCS2020, STACS2019.

Contact

Office

Room 3.02
Kaiserstraße 21
66386 St. Ingbert
Germany

Get in touch at jacobfocke @ cispade