Isomorphism of (mis)labeled graphs

Pascal Schweitzer*

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    7 Citations (Scopus)

    Abstract

    For similarity measures of labeled and unlabeled graphs, we study the complexity of the graph isomorphism problem for pairs of input graphs which are close with respect to the measure. More precisely, we show that for every fixed integer k we can decide in quadratic time whether a labeled graph G can be obtained from another labeled graph H by relabeling at most k vertices. We extend the algorithm solving this problem to an algorithm determining the number ℓ of vertices that must be deleted and the number k of vertices that must be relabeled in order to make the graphs equivalent. The algorithm is fixed-parameter tractable in k+ℓ Contrasting these tractability results, we also show that for those similarity measures that change only by finite amount d whenever one edge is relocated, the problem of deciding isomorphism of input pairs of bounded distance d is equivalent to solving graph isomorphism in general.

    Original languageEnglish
    Title of host publicationAlgorithms, ESA 2011 - 19th Annual European Symposium, Proceedings
    Pages370-381
    Number of pages12
    DOIs
    Publication statusPublished - 2011
    Event19th Annual European Symposium on Algorithms, ESA 2011 - Saarbrucken, Germany
    Duration: 5 Sept 20119 Sept 2011

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume6942 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference19th Annual European Symposium on Algorithms, ESA 2011
    Country/TerritoryGermany
    CitySaarbrucken
    Period5/09/119/09/11

    Fingerprint

    Dive into the research topics of 'Isomorphism of (mis)labeled graphs'. Together they form a unique fingerprint.

    Cite this