Detecting induced subgraphs |
| |
Authors: | Benjamin L vê que, David Y. Lin, Fr d ric Maffray,Nicolas Trotignon |
| |
Affiliation: | aCNRS, Laboratoire G-SCOP, 46 Avenue Félix Viallet, 38031 Grenoble Cedex, France;bPrinceton University, Princeton, NJ, 08544, United States;cCNRS, Université Paris 7, Paris Diderot, LIAFA, Case 7014, 75205 Paris Cedex 13, France |
| |
Abstract: | 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 be a set of graphs and d be an integer. Let 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 and x,yV(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 is NP-complete. We give a simple criterion on a connected graph H to decide whether is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour. |
| |
Keywords: | Detecting Induced Subgraphs |
本文献已被 ScienceDirect 等数据库收录! |
|