摘要: The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs $G$ and $H$, it asks whether they are the same up to relabeling vertices. In 1981, Lubiw proved that list restricted (ListIso) NP-complete: for each $u \in V(G)$, we given ${\mathfrak L}(u) \subseteq V(H)$ possible images $u$. After 35 years, revive study this consider which results GraphIso translate ListIso. We prove following: 1) When GI-complete class graphs, translates into NP-completeness 2) Combinatorial algorithms ListIso: trees, planar interval circle permutation bounded genus treewidth graphs. 3) Algorithms based on group theory do not translate: ListIso remains NP-complete cubic colored with sizes color classes by 8. Also, allows classify problem. Some robust A fundamental construct combinatorial polynomial-time algorithm isomorphism, avoiding theory. By 3rd result, NP-hard them, so no exists, unless P = NP.
arxiv.org
128.84.21.199参考文章(67)
Fedor V. Fomin, Jan Kratochvíl, Daniel Lokshtanov, Federico Mancini, Jan Arne Telle, On the complexity of reconstructing H-free graphs from their Star Systems Journal of Graph Theory. ,vol. 68, pp. 113- 124 ,(2011) , 10.1002/JGT.20544
Uwe Schöning, Graph isomorphism is in the low hierarchy Journal of Computer and System Sciences. ,vol. 37, pp. 312- 323 ,(1988) , 10.1016/0022-0000(88)90010-4
Miklós Biró, Mihály Hujter, Zs Tuza, Precoloring extension. I: Interval graphs Discrete Mathematics. ,vol. 100, pp. 267- 279 ,(1992) , 10.1016/0012-365X(92)90646-W
Jan Kratochvíl, Zsolt Tuza, Algorithmic complexity of list colorings Discrete Applied Mathematics. ,vol. 50, pp. 297- 302 ,(1994) , 10.1016/0166-218X(94)90150-3
Kellogg S. Booth, George S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms Journal of Computer and System Sciences. ,vol. 13, pp. 335- 379 ,(1976) , 10.1016/S0022-0000(76)80045-1
I. S. Filotti, Jack N. Mayer, A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus symposium on the theory of computing. pp. 236- 243 ,(1980) , 10.1145/800141.804671
D.G. Corneil, H. Lerchs, L.Stewart Burlingham, Complement reducible graphs Discrete Applied Mathematics. ,vol. 3, pp. 163- 174 ,(1981) , 10.1016/0166-218X(81)90013-5
Bengt Aspvall, Michael F. Plass, Robert Endre Tarjan, A linear-time algorithm for testing the truth of certain quantified boolean formulas☆ Information Processing Letters. ,vol. 8, pp. 121- 123 ,(1979) , 10.1016/0020-0190(79)90002-4
Neil Robertson, P.D Seymour, Graph minors. XVI. excluding a non-planar graph Journal of Combinatorial Theory, Series B. ,vol. 89, pp. 43- 76 ,(2003) , 10.1016/S0095-8956(03)00042-X
Sergei Evdokimov, Ilia Ponomarenko, Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks Combinatorica. ,vol. 19, pp. 321- 333 ,(1995) , 10.1007/S004930050059