레이블을 보존하는 최대 공통 서브 그래프

Question

동일한 노드 집합 V에서 두 그래프 G1과 G2가 주어지면 노드의 레이블을 보존하는 최대 공통 부분 그래프가 필요합니다.

일반 MCS 문제가 NP-Hard라는 것을 알고 있습니다. 여전히이 제한 사항이 있습니까? 해당 케이스에 대한 특정 알고리즘이 있습니까?

감사합니다.

Answer 1

정확히 어떤 문제인지는 분명하지 않습니다. 특히 "동일한 노드 집합"이 의미하는 것은 무엇입니까?

그러나 일반적인 문제가 NP-hard 인 경우 (문제가 정확히 무엇인지에 따라 다르거 나 그렇지 않을 수도 있음) 레이블을 포함하는 문제는 NP 하드가되어야합니다. G1과 G2의 모든 노드에 같은 레이블을 부여함으로써 원래의 문제 (레이블이 없음)를 레이블 문제에 적용 할 수 있습니다. 좀 더 명확한 대답을 원하는 경우

, 좀 더 정확하게 질문을 정의해야합니다 :

• 그래프가 무엇입니까? (지시 또는 무향, 멀티 그래프 또는 간단한 그래프 등) 그래프의 노드에 레이블을 지정하는 방법은 무엇입니까?
• MCS 문제의 버전은 무엇입니까? (문제의 일반적인 정의에서 동형이 포함된다)?
• "동일한 노드 집합"이란 무엇을 의미합니까? (두 그래프의 노드 수가 같거나 MCS가 두 그래프에서 동일한 노드를 사용한다는 의미입니까? 후자의 경우 문제는 NP 하드가 아닙니다.)