이전에 NP 그래프 문제를 본 사람이 있습니까?

Question

그래프 기반 문제가 있습니다 :

1. 입력 : 양의 정수 k 및 l, himired graph g
2. 이 그래프에서 K 정점을 선택해야합니다
3. 선택한 K 꼭대기의 각 쌍 사이의 경로에 적어도 L 정점이 있어야합니다.이자형.적어도 L 정점으로 만들어진 선택한 정점 중 각 두 개를 "사이에 공백"이 있어야합니다.

위의 문제의 주어진 인스턴스가 가능하지 않을 수 있습니다. 그러면 문제를 확인해야합니다.나는이 문제가 NP 또는 심지어 NP가 완료되었는지, 길이 제약 조건이있는 경로와 관련이 있기 때문에 꽤 확신합니다.비슷한 문제를 만난 적이 있습니까?아마도 NP를 더 잘 알려진 문제로 줄이는 방법을 알 수 있습니까?지.정점 덮개 또는 그래프 색칠?

또한, 내 그래프는 "가득 찬"되지 않고 전체 직사각형 그리드의 서브 그래프가 아닌 그리드 그래프입니다.

Answer 1

이것은 거리 $ d $ 독립적 인 세트로 알려져 있습니다. 즉, 독립적 인 크기 세트 $ k $ 솔루션의 모든 두 요소 사이의 거리는 $ d $ 입니다.

[1]에 따라 평면 그래프에서도 문제가 있지만 부분 그리드의 복잡성을 모르지만

감축에 관해서는 $ d $ 'th 그래프의 힘 의 힘을 찾고 (거리 -1) 독립적으로 설정합니다. 주장은 여기의 모든 솔루션이 원본에서 $ d $ 독립적 인 세트가 있지만이를 확인해야합니다.

---

[1] Eto, 히로시, 펜 그루이 Guo 및 Eiji Miyano. "거리 - $ d $ 독립적 인 Bipartite 및 Chordal 그래프의 독립적 인 문제점" 조합 최적화 일지 27, 아니오. 1 (2014) : 88-99.

Answer 2

$ L= 1 $ 의 특별한 경우, 이것은 일반 그래프에서 np-hard 인 최대 독립적 인 세트 문제 . 따라서 문제는 일반 그래프에서도 NP-Hard뿐입니다.

당신이 가지고있는 그래프의 클래스와 관련된 알고리즘에 대해 희망하려고 할 수 있습니다 (나는 최대 독립적 인 세트 BipArtite 그래프에서 효율적으로 계산할 수 있으며 그리드 그래프는 BipArtite이므로 해당 알고리즘을 일반화하려고 할 수 있거나 최대 독립적 인 세트 / Clique를 위해 표준 알고리즘을 사용하여 시도 할 수 있습니다. 솔버. MAXSAT 인스턴스로 공식화하는 것은 쉽습니다. 거리 $ L + 1 $ (또는 그 이하)에있는 정점의 각 쌍에 대한 절이 있습니다. SAT Solver에 true로 설정된 변수 수를 최소화하도록 요청하십시오.

Answer 3

그래프 색소 문제의 규칙을 사용하여 G-vertices 하위 그래프가 있는지 확인하는 것과 같습니다.나는 모든 K 꼭대기가 같은 색으로 착색 된 것들이 ur 조건을 만족시키는 것을 의미합니다.

NP 완료에서의 그래프 착색은 다항식 시간에 주어진 솔루션을 검증 할 수 있습니다.

그래서 어쩌면이 일이 일어날 수도 있습니다.

1- UR 그래프가 l- colorable인지 확인

2-k vertices 세트가있는 색상 검색