Finding d-Cuts in Probe H-Free Graphs

For an integer d ≥ 1, the d-Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most d vertices on the opposite side of the cut. The 1-Cut problem is the well-known Matching Cut problem. The d-Cut problem has been extensively studied for H-free graphs. We extend these results to the probe graph model, where we do not know all the edges of the input graph. For a graph H, a partitioned probe H-free graph (G, P, N ) consists of a graph G = (V, E), together with a set P ⊆ V of probes and an independent set N = V \ P of non-probes such that we can change G into an H-free graph by adding zero or more edges between vertices in N . For every graph H and every integer d ≥ 1, we completely determine the complexity of d-Cut on partitioned probe H-free graphs.