Induced subgraph isomorphism: Are some patterns substantially easier than others?
(2015) In Theoretical Computer Science 605. p.119128 Abstract
 The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size. We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on 2k1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2k vertices is... (More)
 The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size. We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on 2k1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2k vertices is not easier to detect than an independent set on k vertices. In view of linear time upper bounds on the detection of induced path of length two and three, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and an induced paw and its generalizations. We show also that for an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H, resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively. Next, we show that the socalled diamond and its generalizations on k vertices are not easier to detect as induced subgraphs than an independent set on three vertices or an independent set on k vertices, respectively. For C4, we give a weaker evidence of its hardness in terms of an independent set on three vertices. Finally, we derive several results relating the complexity of the edgecolored variant of induced subgraph isomorphism to that of the standard variant. (C) 2015 Elsevier B.V. All rights reserved. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/8539569
 author
 Floderus, Peter ^{LU} ; Kowaluk, Miroslaw; Lingas, Andrzej ^{LU} and Lundell, EvaMarta ^{LU}
 organization
 publishing date
 2015
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Induced subgraph isomorphism, Detecting subgraphs, Counting subgraphs, Time complexity
 in
 Theoretical Computer Science
 volume
 605
 pages
 119  128
 publisher
 Elsevier
 external identifiers

 wos:000365059800009
 scopus:84944441809
 ISSN
 03043975
 DOI
 10.1016/j.tcs.2015.09.001
 language
 English
 LU publication?
 yes
 id
 f454a6e2d6eb477783d0c4d739ac38b3 (old id 8539569)
 date added to LUP
 20160120 13:03:28
 date last changed
 20181003 12:08:19
@article{f454a6e2d6eb477783d0c4d739ac38b3, abstract = {The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size. We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on 2k1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2k vertices is not easier to detect than an independent set on k vertices. In view of linear time upper bounds on the detection of induced path of length two and three, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and an induced paw and its generalizations. We show also that for an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H, resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively. Next, we show that the socalled diamond and its generalizations on k vertices are not easier to detect as induced subgraphs than an independent set on three vertices or an independent set on k vertices, respectively. For C4, we give a weaker evidence of its hardness in terms of an independent set on three vertices. Finally, we derive several results relating the complexity of the edgecolored variant of induced subgraph isomorphism to that of the standard variant. (C) 2015 Elsevier B.V. All rights reserved.}, author = {Floderus, Peter and Kowaluk, Miroslaw and Lingas, Andrzej and Lundell, EvaMarta}, issn = {03043975}, keyword = {Induced subgraph isomorphism,Detecting subgraphs,Counting subgraphs,Time complexity}, language = {eng}, pages = {119128}, publisher = {Elsevier}, series = {Theoretical Computer Science}, title = {Induced subgraph isomorphism: Are some patterns substantially easier than others?}, url = {http://dx.doi.org/10.1016/j.tcs.2015.09.001}, volume = {605}, year = {2015}, }