Jacob Focke

38 papers A* 9A 2B 1Journal 26
YearRankTypeTitle / Venue / Authors
2026 J jnl
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern.
Discret. Comput. Geom.
Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx
2025 J jnl
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.
ACM Trans. Algorithms
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
2025 J jnl
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs - Part I: Algorithmic Results.
ACM Trans. Algorithms
Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz
2025 J jnl
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results.
ACM Trans. Comput. Theory
Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz
2024 J jnl
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity.
Proc. ACM Manag. Data
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
2024 J jnl
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds.
ACM Trans. Algorithms
Jacob Focke, Dániel Marx, Pawel Rzazewski
2024 J jnl
Counting Small Induced Subgraphs with Hereditary Properties.
SIAM J. Comput.
Jacob Focke, Marc Roth
2024 A* conf
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness.
ICALP
Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski
2024 J jnl
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness.
CoRR
Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski
2024 A conf
Hitting Meets Packing: How Hard Can It Be?
ESA
Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, Karol Wegrzycki
2024 J jnl
Hitting Meets Packing: How Hard Can it Be?
CoRR
Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, Karol Wegrzycki
2024 A conf
List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs.
ESA
Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski
2024 A* conf
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern.
SoCG
Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx
2023 J jnl
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity.
CoRR
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
2023 J jnl
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern.
CoRR
Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx
2023 J jnl
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results.
CoRR
Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz
2023 A* conf
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs.
SODA
Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz
2022 A* conf
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.
PODS
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
2022 A* conf
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds.
SODA
Jacob Focke, Dániel Marx, Pawel Rzazewski
2022 A* conf
Counting small induced subgraphs with hereditary properties.
STOC
Jacob Focke, Marc Roth
2022 J jnl
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs.
CoRR
Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski
2022 J jnl
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results.
CoRR
Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz
2021 J jnl
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.
CoRR
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
2021 A* conf
Counting Homomorphisms to
SODA
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
2021 J jnl
Counting Homomorphisms to K
SIAM J. Discret. Math.
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
2021 J jnl
Counting Small Induced Subgraphs with Hereditary Properties.
CoRR
Jacob Focke, Marc Roth
2021 J jnl
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds.
CoRR
Jacob Focke, Dániel Marx, Pawel Rzazewski
2021 J jnl
The Complexity of Approximately Counting Retractions to Square-free Graphs.
ACM Trans. Algorithms
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
2020 J jnl
Counting Homomorphisms to K
CoRR
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
2020 J jnl
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments.
ACM J. Exp. Algorithmics
Jacob Focke, Nicole Megow, Julie Meißner
2020 J jnl
The Complexity of Approximately Counting Retractions.
ACM Trans. Comput. Theory
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
2019 J jnl
The Complexity of Approximately Counting Retractions to Square-Free Graphs.
CoRR
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
2019 A* conf
The Complexity of Approximately Counting Retractions.
SODA
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
2019 J jnl
The Complexity of Counting Surjective Homomorphisms and Compactions.
SIAM J. Discret. Math.
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
2018 J jnl
The Complexity of Approximately Counting Retractions.
CoRR
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
2018 A* conf
The Complexity of Counting Surjective Homomorphisms and Compactions.
SODA
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
2017 B conf
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments.
SEA
Jacob Focke, Nicole Megow, Julie Meißner
2017 J jnl
The Complexity of Counting Surjective Homomorphisms and Compactions.
CoRR
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný