For an integer \(d\ge 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\subseteq V\) of probes and an independent set \(N=V\setminus 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\ge 1\) , we completely determine the complexity of \(d\) -Cut on partitioned probe H-free graphs.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Finding d-Cuts in Probe H-Free Graphs

  • Konrad K. Dabrowski,
  • Tala Eagling-Vose,
  • Matthew Johnson,
  • Giacomo Paesani,
  • Daniël Paulusma

摘要

For an integer \(d\ge 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\subseteq V\) of probes and an independent set \(N=V\setminus 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\ge 1\) , we completely determine the complexity of \(d\) -Cut on partitioned probe H-free graphs.