Jacob Focke

According to our database, Jacob Focke authored at least 17 papers between 2019 and 2024.

Collaborative distances:

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

2024

Counting Small Induced Subgraphs with Hereditary Properties.

Jacob Focke, Marc Roth

SIAM J. Comput., 2024

Hitting Meets Packing: How Hard Can it Be?

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

CoRR, 2024

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

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

CoRR, 2024

2023

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

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

CoRR, 2023

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

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

CoRR, 2023

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

CoRR, 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

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

CoRR, 2022

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs.

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

CoRR, 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

2020

The Complexity of Approximately Counting Retractions.

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný

ACM Trans. Comput. Theory, 2020

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments.

Jacob Focke, Nicole Megow, Julie Meißner

ACM J. Exp. Algorithmics, 2020

2019

The Complexity of Counting Surjective Homomorphisms and Compactions.

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný

SIAM J. Discret. Math., 2019