On the forbidden induced subgraph probe and sandwich problems

In this work we compare the complexities of graph sandwich problems, partitioned and unpartitioned probe problems. Particularly, we consider the problem of recognizing probe graphs with respect to a class of graphs defined by excluding induced subgraphs. Our main result is: for F-free graphs, where F is a 3-connected, non complete graph, we prove that if F-free graph sandwich problem is NP-complete, then partitioned probeF-free problem and probeF-free problem are NP-complete. We also compare partitioned and unpartitioned versions of probe problems dealing with 2-connected graphs. Besides that, we consider Ck-free and (C4,…,C∣N∣)-free graphs and we prove that both problems in both versions of probe problems are NP-complete. In contrast, we prove that probe (Kr∖e)-free is polynomially solvable, where Kr∖e means a complete graph of size r without one edge. Finally, motivated by probeC4-free, we analyze the complexity of finding a stable set that touches every even cycle of size 2k exactly k times, which we call k-stableC2ktransversal. We prove that finding a k-stable C2k transversal can be done in polynomial time.