Showing 2025Show all
2 papers · 1 filter
cs.DS2025
Testing H-freeness on sparse graphs, the case of bounded expansion
Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock +2
In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the gr…
cs.DS2025
Solving Partial Dominating Set and Related Problems Using Twin-Width
Jakub Balabán, Daniel Mock, Peter Rossmanith
Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are -hard on general graphs, they have been shown to be fixed-…