TY - GEN
T1 - Isomorphism of (mis)labeled graphs
AU - Schweitzer, Pascal
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80052785238&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-23719-5_32
DO - 10.1007/978-3-642-23719-5_32
M3 - Conference contribution
SN - 9783642237188
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 370
EP - 381
BT - Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings
T2 - 19th Annual European Symposium on Algorithms, ESA 2011
Y2 - 5 September 2011 through 9 September 2011
ER -