Name
Abstract | ||
|---|---|---|
The complexity of graph isomorphism (GRAPHISO) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (LISTISO) is NP-complete: for each u is an element of V(G), we are given a list L(u) subset of V(H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GraphIso can be modified to solve ListIso. We prove: 1) Under certain conditions, GI-completeness of a class of graphs implies NP-completeness of ListIso. 2) Several combinatorial algorithms for GraphIso can be modified to solve ListIso: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, and bounded treewidth graphs. 3) ListIso is NP-complete for cubic colored graphs with sizes of color classes bounded by 8 with all lists of size at most 3. (C) 2021 The Author(s). Published by Elsevier B.V. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2021.01.027 | THEORETICAL COMPUTER SCIENCE |
Keywords | Field | DocType |
Graph isomorphism problem, Restricted computational problem, Polynomial-time algorithms, NP-completeness, Bounded treewidth, Bounded degree graphs | Graph automorphism,Discrete mathematics,Indifference graph,Combinatorics,Graph isomorphism,Partial k-tree,Graph homomorphism,Chordal graph,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | ISSN | Citations |
860 | 0304-3975 | 1 |
PageRank | References | Authors |
0.35 | 36 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pavel Klavík | 1 | 95 | 10.63 |
| Dusan Knop | 2 | 47 | 17.31 |
| Peter Zeman | 3 | 6 | 3.14 |