5 citations · 17 across the 20 of their papers we have counts for
6 papers · 1 filter
FPT=PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns
Matthias Lanzinger
Assuming the Exponential Time Hypothesis (ETH), fixed-parameter tractability and polynomial-time solvability coincide for homomorphism problems specified by classes of pattern hype…
From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
Markus Hecher, Matthias Lanzinger
Counting problems are fundamental across mathematics and computer science. Among the most subtle are those whose associated decision problem is solvable in polynomial time, yet who…
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, Marc Roth
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs and , count the number of copies of in .…
On the Complexity of Inductively Learning Guarded Rules
Andrei Draghici, Georg Gottlob, Matthias Lanzinger
We investigate the computational complexity of mining guarded clauses from clausal datasets through the framework of inductive logic programming (ILP). We show that learning guarde…
Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems
Hubie Chen, Georg Gottlob, Matthias Lanzinger +1
Constraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e.g., coloring or scheduling problems. Solving CS…
Complexity Analysis of Generalized and Fractional Hypertree Decompositions
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler +1
Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hy…