Detecting induced subgraphs

Abstract

An \emph{s-graph} is a graph with two kinds of edges: \emph{subdivisible} edges and \emph{real} edges. A \emph{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 ${\Pi }_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 ${\Pi }_B$ is known and here we give the complexity for several more. Our NP-completeness proofs for ${\Pi }_B$'s rely on the NP-completeness proof of the following problem. Let $\mathcal{S}$ be a set of graphs and $d$ be an integer. Let ${\Gamma }_{\mathcal{S}}^d$ 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 $\mathcal{S}$ and $x,y\in V(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 ${\Gamma }_{\varnothing }^3$ is NP-complete. We give a simple criterion on a connected graph $H$ to decide whether ${\Gamma }_{\{H\}}^{+\infty }$ is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour.

arXiv admin note: text overlap with arXiv:1308.6678

References in corpus (3)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Algorithms for perfectly contractile graphs
• Algorithms for square-$3PC(\cdot ,\cdot )$-free Berge graphs

Cited by in corpus (9)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• On graphs with no induced subdivision of $K_4$
• Three-in-a-Tree in Near Linear Time
• The $k$-in-a-tree problem for graphs of girth at least~$k$
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• Treewidth versus clique number. I. Graph classes with a forbidden structure
• Finding an induced subdivision of a digraph
• Detecting an induced net subdivision
• The (theta, wheel)-free graphs Part IV: induced paths and cycles