1 citations · 2 across the 6 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.CC2024
From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
Simon Döring, Dániel Marx, Philip Wellnitz
A graph property is a function that maps every graph to {0, 1} and is invariant under isomorphism. In the problem, given a graph and an integer , the task…
cs.DS2024
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…
cs.CC2024
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…