Jacob Focke

According to our database, Jacob Focke authored at least 17 papers between 2017 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs - Part I: Algorithmic Results.

Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz

ACM Trans. Algorithms, July, 2025

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results.

Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz

ACM Trans. Comput. Theory, June, 2025

2024

Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity.

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný

Proc. ACM Manag. Data, 2024

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness.

Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Hitting Meets Packing: How Hard Can It Be?

Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, Karol Wegrzycki

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs.

Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern.

Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs.

Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Counting small induced subgraphs with hereditary properties.

Jacob Focke, Marc Roth

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds.

Jacob Focke, Dániel Marx, Pawel Rzazewski

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

2021

The Complexity of Approximately Counting Retractions to Square-free Graphs.

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný

ACM Trans. Algorithms, 2021

Counting Homomorphisms to K₄-Minor-Free Graphs, Modulo 2.

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný

SIAM J. Discret. Math., 2021

Counting Homomorphisms to <i>K</i>₄-minor-free Graphs, modulo 2.

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2019

The Complexity of Approximately Counting Retractions.

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

The Complexity of Counting Surjective Homomorphisms and Compactions.

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments.

Jacob Focke, Nicole Megow, Julie Meißner

Proceedings of the 16th International Symposium on Experimental Algorithms, 2017