3 citations · 7 across the 10 of their papers we have counts for
14 papers
Hitting Meets Packing: How Hard Can it Be?
Jacob Focke, Fabian Frei, Shaohua Li +4
We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of X-HitP…
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
Barış Can Esmer, Jacob Focke, Dániel Marx +1
It is known for many algorithmic problems that if a tree decomposition of width is given in the input, then the problem can be solved with exponential dependence on . A line…
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
Jacob Focke, Florian Hörsch, Shaohua Li +1
The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph and demand graph on a set of terminals, the task…
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem…
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets of non-negative…
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets of non-negative integers, a -set o…
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
Barış Can Esmer, Jacob Focke, Dániel Marx +1
The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict t…
Counting Small Induced Subgraphs with Hereditary Properties
Jacob Focke, Marc Roth
We study the computational complexity of the problem of counting -vertex induced subgraphs of a graph that satisfy a graph property . Our main result…
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
Jacob Focke, Dániel Marx, Paweł Rzążewski
The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given grap…
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the complexity of approximating the number of answers to a small query in a large database . We establish an exhaustive classification into tractable and…
Counting Homomorphisms to -minor-free Graphs, modulo 2
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the problem of computing the parity of the number of homomorphisms from an input graph to a fixed graph . Faben and Jerrum [ToC'15] introduced an explicit criterion…
The Complexity of Approximately Counting Retractions to Square-Free Graphs
Jacob Focke, Leslie Ann Goldberg, Stanislav Živný
A retraction is a homomorphism from a graph to an induced subgraph of that is the identity on . In a long line of research, retractions have been studied under vario…
The Complexity of Approximately Counting Retractions
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny
Let be a graph that contains an induced subgraph . A retraction from to is a homomorphism from to that is the identity function on . Retractions are very…
The Complexity of Counting Surjective Homomorphisms and Compactions
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny
A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertic…