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

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(G1, G2)
Đầu vào: hai đồ thị G1 và G2.
Câu hỏi: G1 có đẳng cấu với một đồ thị con của G2 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.

Tham khảo

 Jeffrey D. Ullman: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
  A1.4: GT48, p. 202.

Thể loại:Các bài toán NP-đầy đủ
Thể loại:Lý thuyết đồ thị
Thể loại:Giải thuật lý thuyết đồ thị
Thể loại:Lý thuyết đồ thị trong các bài toán tính toán
Thể loại:Bài toán NP-đủ