4 papers
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…
Weighted Treedepth is NP-complete on Graphs of Bounded Degree
Jona Dirks, Nicole Schirrmacher, Sebastian Siebertz +1
A treedepth decomposition of an undirected graph is a rooted forest on the vertex set of such that every edge is in ancestor-descendant relationship in …
Lower bounds for dominating set reconfiguration on sparse (directed) graphs
Jona Dirks, Alexandre Vigny
In a graph, a vertex dominates itself and its neighbors, and a dominating set is a set of vertices that together dominate the entire graph. Given a graph and two dominating sets of…
Token Sliding Reconfiguration on DAGs
Jona Dirks, Alexandre Vigny
Given a graph and two independent sets of same size, the Independent Set Reconfiguration Problem under token sliding ask whether one can, in a step by step manner, transform th…