Back to Search
Start Over
Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Source :
-
Journal of Computer & System Sciences . Nov2008, Vol. 74 Issue 7, p1147-1159. 13p. - Publication Year :
- 2008
-
Abstract
- Abstract: This paper investigates a graph enumeration problem, called the maximal -subgraphs problem, where is a hereditary or connected-hereditary graph property. Formally, given a graph G, the maximal -subgraphs problem is to generate all maximal induced subgraphs of G that satisfy . This problem differs from the well-known node-deletion problem, studied by Yannakakis and Lewis [J. Lewis, On the complexity of the maximum subgraph problem, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 265–274; M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 253–264; J. Lewis, M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (2) (1980) 219–230]. In the maximal -subgraphs problem, the goal is to produce all (locally) maximal subgraphs of a graph that have property , whereas in the node-deletion problem, the goal is to find a single (globally) maximum size subgraph with property . Algorithms are presented that reduce the maximal -subgraphs problem to an input-restricted version of this problem. These algorithms imply that when attempting to efficiently solve the maximal -subgraphs problem for a specific , it is sufficient to solve the restricted case. The main contributions of this paper are characterizations of when the maximal -subgraphs problem is in a complexity class C (e.g., polynomial delay, total polynomial time). [Copyright &y& Elsevier]
- Subjects :
- *ALGORITHMS
*COMPUTATIONAL complexity
*NP-complete problems
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 74
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 34656936
- Full Text :
- https://doi.org/10.1016/j.jcss.2008.04.003