All normalized anti-monotonic overlap graph measures are bounded

T.G.K. Calders, J. Ramon, D. Van Dyck

    Research output: Contribution to journalArticleAcademicpeer-review

    14 Citations (Scopus)

    Abstract

    The Induced Subgraph Isomorphism problem on two input graphs G and H is to decide whether G has an induced subgraph isomorphic to H. Already for the restricted case where H is a complete graph the problem is NP-complete, as it is then equivalent to the Clique problem. In a recent paper [7] Marx and Schlotter show that Induced Subgraph Isomorphism is NP-complete when G and H are restricted to be interval graphs. They also show that the problem is W[1]-hard with this restriction when parametrised by the number of vertices in H. In this paper we show that when G is an interval graph and H is a connected proper interval graph, the problem is solvable in polynomial time. As a more general result, we show that when G is an interval graph and H is an arbitrary proper interval graph, the problem is fixed parameter tractable when parametrised by the number of connected components of H. To complement our results, we prove that the problem remains NP-complete when G and H are both proper interval graphs and H is disconnected.
    Original languageEnglish
    Pages (from-to)503-548
    JournalData Mining and Knowledge Discovery
    Volume23
    Issue number3
    DOIs
    Publication statusPublished - 2011

    Fingerprint

    Dive into the research topics of 'All normalized anti-monotonic overlap graph measures are bounded'. Together they form a unique fingerprint.

    Cite this