Generating All Maximal Induced Subgraphs for Hereditary, Connected-Hereditary and Rooted-Hereditary Properties
<|reference_start|>Generating All Maximal Induced Subgraphs for Hereditary, Connected-Hereditary and Rooted-Hereditary Properties: The problem of computing all maximal induced subgraphs of a graph G that have a graph property P, also called the maximal P-subgraphs problem, is considered. This problem is studied for hereditary, connected-hereditary and rooted-hereditary graph properties. The maximal P-subgraphs problem is reduced to restricted versions of this problem by providing algorithms that solve the general problem, assuming that an algorithm for a restricted version is given. The complexity of the algorithms are analyzed in terms of total polynomial time, incremental polynomial time and the complexity class P-enumerable. The general results presented allow simple proofs that the maximal P-subgraphs problem can be solved efficiently (in terms of the input and output) for many different properties.<|reference_end|>
@article{cohen2004generating,
    title={Generating All Maximal Induced Subgraphs for Hereditary,
  Connected-Hereditary and Rooted-Hereditary Properties},
    author={Sara Cohen and Yehoshua Sagiv},
    journal={arXiv preprint arXiv:cs/0410039},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0410039},
    primaryClass={cs.DS cs.DM}
}