Detecting induced subgraphs

An s-graph is a graph with two kinds of edges: subdivisible edges and real edges. A realisation   of an s-graph BB is any graph obtained by subdividing subdivisible edges of BB into paths of arbitrary length (at least one). Given an s-graph BB, we study the decision problem ΠBΠB whose instance is a graph GG and question is “Does GG contain a realisation of BB as an induced subgraph?”. For several BB’s, the complexity of ΠBΠB is known and here we give the complexity for several more.Our NP-completeness proofs for ΠBΠB’s rely on the NP-completeness proof of the following problem. Let SS be a set of graphs and dd be an integer. Let ΓSd be the problem whose instance is (G,x,y)(G,x,y) where GG is a graph whose maximum degree is at most dd, with no induced subgraph in SS and x,y∈V(G)x,y∈V(G) are two non-adjacent vertices of degree 2. The question is “Does GG contain an induced cycle passing through x,yx,y?”. Among several results, we prove that Γ0̸3 is NP-complete. We give a simple criterion on a connected graph HH to decide whether Γ{H}+∞ is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour.