Résumé
An s-graph is a graph with two kinds of edges: subdivisible edges and real edges. A realisation of an s-graph B is any graph obtained by subdividing subdivisible edges of B into paths of arbitrary length (at least one). Given an s-graph B, we study the decision problem ΠB whose instance is a graph G and question is "Does G contain a realisation of B as an induced subgraph?". For several B's, the complexity of ΠB is known and here we give the complexity for several more. Our NP-completeness proofs for ΠB's rely on the NP-completeness proof of the following problem. Let View the MathML source be a set of graphs and d be an integer. Let View the MathML source be the problem whose instance is (G,x,y) where G is a graph whose maximum degree is at most d, with no induced subgraph in View the MathML source and x,yset membership, variantV(G) are two non-adjacent vertices of degree 2. The question is "Does G contain an induced cycle passing through x,y?". Among several results, we prove that View the MathML source is NP-complete. We give a simple criterion on a connected graph H to decide whether View the MathML source is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour.