Jacob Focke

Publication Activity (10 Years)

Years Active: 2017-2024
Publications (10 Years): 32

Top Topics

Tight Complexity Bounds

Conjunctive Queries

Bounded Treewidth

Top Venues

SIAM J. Discret. Math.

ACM Trans. Algorithms

Publications

Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness. ICALP (2024)
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)
Jacob Focke, Dániel Marx, Pawel Rzazewski
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds. ACM Trans. Algorithms 20 (2) (2024)
Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness. CoRR (2024)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity. Proc. ACM Manag. Data 2 (2) (2024)
Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, Karol Wegrzycki
Hitting Meets Packing: How Hard Can it Be? CoRR (2024)
Jacob Focke, Marc Roth
Counting Small Induced Subgraphs with Hereditary Properties. SIAM J. Comput. 53 (2) (2024)
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. SODA (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 Part II: Hardness Results. CoRR (2023)
Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern. CoRR (2023)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity. CoRR (2023)
Jacob Focke, Marc Roth
Counting small induced subgraphs with hereditary properties. STOC (2022)
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. CoRR (2022)
Jacob Focke, Dániel Marx, Pawel Rzazewski
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. SODA (2022)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. PODS (2022)
Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs. CoRR (2022)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. CoRR (2021)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions to Square-free Graphs. ACM Trans. Algorithms 17 (3) (2021)
Jacob Focke, Dániel Marx, Pawel Rzazewski
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. CoRR (2021)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
-minor-free Graphs, modulo 2. SODA (2021)
Jacob Focke, Marc Roth
Counting Small Induced Subgraphs with Hereditary Properties. CoRR (2021)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
-Minor-Free Graphs, Modulo 2. SIAM J. Discret. Math. 35 (4) (2021)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions. ACM Trans. Comput. Theory 12 (3) (2020)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
-minor-free Graphs, modulo 2. CoRR (2020)
Jacob Focke, Nicole Megow, Julie Meißner
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. ACM J. Exp. Algorithmics 25 (2020)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions. SODA (2019)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Counting Surjective Homomorphisms and Compactions. SIAM J. Discret. Math. 33 (2) (2019)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions to Square-Free Graphs. CoRR (2019)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions. CoRR (2018)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Counting Surjective Homomorphisms and Compactions. SODA (2018)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Counting Surjective Homomorphisms and Compactions. CoRR (2017)
Jacob Focke, Nicole Megow, Julie Meißner
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. SEA (2017)