심어진 패거리

계산 복잡성 이론에서, 비방향 그래프에 심어진 클릭 또는 숨겨진 클릭은 정점의 부분 집합을 선택하고 부분 집합에 있는 각 쌍의 정점 사이에 가장자리를 추가함으로써 다른 그래프에서 형성된 클릭이다.심어진 패거리 문제는 무작위 그래프를 심은 패거리가 있는 그래프와 구별하는 알고리즘 문제다.이것은 clique 문제의 변형이다. 준-폴리놈 시간에는 해결될 수 있지만 clique 크기의 중간 값에 대해서는 다항 시간에는 해결할 수 없다고 추측된다.다항식 시간 해결책이 존재하지 않는다는 추측은 심어진 클라이크 추측이라고 불리며, 계산적 경도 가정으로 사용되어 왔다.

정의

그래프의 클라이크는 정점의 부분집합으로, 모두 서로 인접해 있다.심어진 클라이크는 정점의 선택한 부분 집합의 모든 쌍 사이에 가장자리를 추가하여 다른 그래프에서 생성된 클라이크다.

심어진 클라이크 문제는 n(정점수)과 k(클릭의 크기)의 두 숫자로 매개변수를 표시한 그래프에 랜덤한 분포에 대한 의사결정 문제로 공식화할 수 있다.이러한 매개변수는 다음과 같은 랜덤 프로세스에 의해 그래프를 생성하는 데 사용될 수 있다.^[1]

1. 각 쌍에 확률 1/2로 쌍을 연결하는 가장자리를 포함할지 여부를 각 꼭지점 쌍에 대해 독립적으로 선택하여 정점에 Erdds-Rényi 랜덤 그래프를 생성한다.
2. 확률 1/2로 그래프에 클라이크를 추가할지 여부를 결정하고, 그렇지 않으면 1단계에서 형성된 그래프를 반환하십시오.
3. n 정점의 k 부분 집합을 임의로 선택하고 선택한 정점의 각 쌍 사이에 에지(이미 없는 경우)를 추가한다.

문제는 이 과정에서 도출된 그래프 중 하나가 적어도 k 정점의 집단을 포함하는지를 알고리즘적으로 결정하는 것이다.

높은 확률로, n-Vertex 랜덤 그래프에서 가장 큰 클라이크의 크기는 2 log₂ n에 가깝다.그리고 k가 n의 제곱근보다 클 때, 심어진 패거리의 정점들은 유달리 큰 학위를 가진 것으로 인식될 수 있어 심어진 패거리를 쉽게 찾을 수 있다.따라서 매개변수 k에 대한 가장 흥미로운 값의 범위는 이 두 값 사이에 있다.^[1]

${\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}.}$

알고리즘

큰 패거리

매개변수 k의 충분한 큰 값에 대해, 심어진 clique 문제는 다항 시간 내에 (높은 확률로) 해결할 수 있다.^[1]

Kuchera(1995)는${\displaystyle \mathrm{k}}$ =${\displaystyle \Omega \sqrt{}}$ (${\displaystyle \sqrt{n}}$ ${\displaystyle \sqrt{\log })}$n$$){\$displaystyle$k=\$Oomega({\sqrt{n\log$ n$}})$가 되면 거의 확실히 심어진 클릭의 모든 정점이 클릭 외부의 모든 정점보다 높은 학위를 가지므로 클릭을 매우 쉽게 찾을 수 있다고 관찰한다.그는 k의 큰 값에도 정점도를 더 균일하게 만드는 심어진 클릭 인스턴스(instance)^[2]를 생성하기 위한 무작위 프로세스의 수정을 설명하지만, 이러한 수정에도 불구하고 심어진 클릭은 여전히 빨리 발견될 수 있다는 것을 보여준다.

알론, 크리벨레비치 & 수다코프(1998)는 > ${\$에 대해 다음과 같은 방법으로 식재된 클라이크를 높은 확률로 발견할 수 있다.

1. 인접 행렬의 고유값 두 번째로 높은 고유값에 해당하는 고유 벡터를 계산한다.
2. 이 고유 벡터의 좌표가 가장 큰 절대값을 갖는 k 정점을 선택하십시오.
3. 선택한 정점의 최소 3/4에 인접한 정점 집합을 반환하십시오.

그들은 k가 최소한 정점수의 제곱근의 일부 배수에 비례할 때마다 계속 작동하도록 이 기법을 수정하는 방법을 보여준다.^[3]대규모의 식재된 패거리도 세미데마인파 프로그래밍을 통해 찾을 수 있다.^[4]무작위 샘플링 정점을 기반으로 하는 조합 기법은 k에 대해 동일한 경계를 달성할 수 있고 선형 시간 내에 실행될 수 있다.^[5]

퀘이폴리놈 시간

k의 선택과 상관없이 심어진 패거리 문제를 준폴리놈 시간 내에 해결하는 것도 가능하다.^[6]랜덤 그래프에서 가장 큰 클릭은 일반적으로 2 로그₂ n에 가까운 크기를 가지기 때문에,^[7] 다음과 같은 방법으로 k 크기의 심어진 클릭(있는 경우)을 높은 확률로 발견할 수 있다.

1. ${\displaystyle 최소(k}$, ${\displaystyle 3}$ ${\displaystyle {\log }_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}n}$)$${\$displaystyle \min(k,3\log _{2}n)$ 정점의$$ 모든 세트 S를 반복하십시오.
2. S의 각 선택에 대해 S가 패거리인지 여부를 시험한다.${\displaystyle S}$ =${\displaystyle k}$ ${\displaystyle S =k}$인 경우 S를 반환하십시오$.$그렇지 않으면 S의 모든 정점에 인접한 정점의 설정 T를 찾으십시오. ${\displaystyle T}$ ${\displaystyle \ge }$ ${\displaystyle k}$ ${\displaystyle$T$\geq$ k$\},$ 반환

이 알고리즘의 실행 시간은 quasipolynomial이다. 왜냐하면 quasipolynomial은 quasipolynomial로 반복할 S의 많은 선택들이 있기 때문이다.이 방법은 식물의 일부인 집합 S를 시도할 것을 보장한다. 높은 확률로, 집합 T는 식물의 다른 구성원들로만 구성될 것이다.

경도 가정으로

심어진 패거리 추측이란, 심어진 패거리들이 만들어내는 입력 그래프로 받아들이고, 심어진 패거리들이 있는 것과 무작위적인 우연보다 확률을 상당히 높게 심지 않은 패거리들을 구별하는 다항 시간 알고리즘이 없다는 추측이다.^[8]

헤이산&크라우츠게머(2011년)는 심어진 패거리의 발견은 계산적 경도 가정으로서 힘들다는 가정을 이용, 만약 그렇다면, 2인승 게임에서 최고의 내쉬 평형도 근사하기 어렵다는 것을 증명했다.^[6]심어진 패거리 추측도 무작위 분포의 k-독립성,^[9] 소셜 네트워크에서의 클러스터 찾기,^[10] 머신러닝의 난이도를 보여주는 경도 가정으로 사용되어 왔다.^[11]

참조