5 citations · 9 across the 6 of their papers we have counts for
11 papers
Residue Domination in Bounded-Treewidth Graphs
Jakob Greilhuber, Philipp Schepper, Philip Wellnitz
For the vertex selection problem -DomSet one is given two fixed sets and of integers and the task is to decide whether we can select vertices of the input graph such…
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…
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…
Computing Generalized Convolutions Faster Than Brute Force
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
In this paper, we consider a general notion of convolution. Let be a finite domain and let be the set of -length vectors (tuples) of . Let be…
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
Esther Galby, Daniel Marx, Philipp Schepper +2
The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameter…
Parameterized Complexity of Weighted Multicut in Trees
Esther Galby, Dániel Marx, Philipp Schepper +2
The Edge Multicut problem is a classical cut problem where given an undirected graph , a set of pairs of vertices , and a budget , the goal is to determine if th…
Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
Dániel Marx, Govind S. Sankar, Philipp Schepper
In the general AntiFactor problem, a graph is given with a set of forbidden degrees for every vertex and the task is to find a set of edges su…
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
Dániel Marx, Govind S. Sankar, Philipp Schepper
For the General Factor problem we are given an undirected graph and for each vertex a finite set of non-negative integers. The task is to decide if there is a…
Subcubic Certificates for CFL Reachability
Dmitry Chistikov, Rupak Majumdar, Philipp Schepper
Many problems in interprocedural program analysis can be modeled as the context-free language (CFL) reachability problem on graphs and can be solved in cubic time. Despite years of…
Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
Philipp Schepper
The currently fastest algorithm for regular expression pattern matching and membership improves the classical O(nm) time algorithm by a factor of about log^{3/2}n. Instead of focus…