Bài toán đồ thị con đẳng cấu

Bách khoa toàn thư mở Wikipedia

Trong lý thuyết độ phức tạp tính toán (Computational complexity theory), Đồ thị con đẳng cấu là một bài toán quyết định (decision problem) thuộc loại NP-đầy đủ (NP-complete). Phát biểu của bài toán quyết định như sau:

Đẳng cấu đồ thị con(G₁, G₂)
Đầu vào: hai đồ thị G₁ và G₂.
Câu hỏi: G₁ có đẳng cấu với một đồ thị con của G₂ hay không?

Đôi khi bài toán này còn nhấn mạnh vào việc tìm đồ thị con đẳng cấu, thay vì chỉ xác định xem có tồn tại đồ thị con đó hay không (như trường hợp bài toán quyết định cơ bản).

Đồ thị con đẳng cấu là suy rộng của một bài toán có thể dễ hơn: bài toán đồ thị đẳng cấu; nếu bài toán này thuộc loại NP-đầy đủ thì polynomial hierarchy (cây phả hệ đa thức???) sẽ sụp đổ. Vậy có lẽ không phải như vậy.

[sửa] Tham khảo

• Jeffrey D. Ullman: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0716710455. A1.4: GT48, pg.202.