가중 된 채색을 계산하여 다음과 같이 적절한 채색을 계산하는 문제를 완화한다고 가정합니다. 모든 적절한 채색은 가중치 1이되고 모든 부적절한 채색은 가중치 여기서 는 일정하고 는 끝 점이있는 가장자리의 수는 동일하게 표시됩니다. 마찬가지로 0으로 진행하고,이 그래프의 많은 어려운 적절한 착색제를 계수로 감소시킨다. c가 1이면 모든 채색의 무게가 같고 문제는 사소합니다. 그래프의 인접 행렬에 를 곱한 경우 스펙트럼 반경이 미만인 경우
cvc
v
c
−log(c)/2
1−ϵ
,이 합계는 수렴 보장을 통한 신념 전파에 의해 근사 될 수 있으므로 실제로는 쉽습니다. 이론적으로는 특정 계산 트리가 상관 관계의 붕괴를 나타내므로 근사를 보장하기위한 다항식 시간 알고리즘을 허용하기 때문에 이론적으로도 쉽다 -Tetali, (2007)
내 질문은-로컬 알고리즘 에서이 문제를 어렵게하는 그래프의 다른 속성은 무엇입니까? 작은 범위의 만이 다루어 질 수 있다는 점에서 어렵다 .
기음편집 09/23 : 지금까지 나는이 클래스의 문제에 대한 두 가지 결정적 다항식 근사 알고리즘 (Weitz의 STOC2006 논문의 파생물과 대략적인 계산에 대한 Gamarnik의 “캐비티 확장”접근법)을 발견했으며 두 가지 접근 방식은 모두 그래프 위를 걷는 것을 피하십시오. 분광 계수의 상한이기 때문에 스펙트럼 반경이 나타납니다. 그렇다면 문제는 좋은 추정입니까? 정기적 인 보행의 분기 계수가 제한없이 증가하는 반면에 자기 회피 보행의 분기 계수가 제한되는 일련의 그래프를 가질 수 있습니까?
편집 10/06 : Allan Sly (FOCS 2010) 의이 논문 은 관련이있는 것으로 보인다 … 결과는 무한 자기 회피 보행의 트리의 분기 계수가 계산이 어려워지는 지점을 정확하게 포착한다고 제안합니다.
편집 10/31 : Alan Sokal 추측 ( “다변량 Tutte polynomia”의 p.42 ) maxmaxflow (최대 st flow over 모든 쌍 s, t). 이것은 적절한 채색의 수가 0에 가까워 질수록 장거리 상관 관계가 나타나기 때문에 관련이있는 것 같습니다.
답변
이것은 최소한 6 가지 이상의 색상의 평면 그래프에는 어렵다. Goldberg와 Jerrum의 “평면 그래프의 Tutte 다항식의 근사 성” 참조
답변
더 많은 의견 :
계산을위한 로컬 알고리즘은 각 통계가 노드의 일부 그래프 이웃의 함수 인 노드 별 통계 세트에서 카운트를 계산합니다. 채색의 경우, 이러한 통계는 “색상 c 발생 가능성 한계”와 관련이 있습니다. 다음 은 간단한 그래프에 대한 축소 의 예 입니다.
Alan Sly의 최근 논문에 따르면 로컬 알고리즘을 사용하여 독립 집합을 계산하는 것은 알고리즘을 사용하여 독립 집합을 계산하는 것만 큼 어렵습니다. 이것이 그래프를 일반적으로 계산할 때 사실이라고 의심합니다.
로컬 알고리즘의 경우 경도는 노드 간 거리와 관련하여 노드 간 상관 관계가 작동하는 방식에 따라 다릅니다. 충분히 큰 거리의 경우이 상관 관계는 본질적으로 그래프 거리에서 기하 급수적으로 감쇠하거나 전혀 감쇠하지 않는 두 가지 동작 만 갖습니다.
지수 붕괴가있는 경우 로컬 통계는 크기가 그래프 크기에서 다항식 인 이웃에 따라 달라 지므로 계산 문제가 쉽습니다.
통계 물리 모델에서, 자기 회피 보행, 상관 붕괴 및 위상 전이 사이에 관련이 있다는 것이 주목되었다 (즉, De Gennes, Emery). 격자에서 자기 회피 보행을위한 생성 기능이 무한 해지는 지점은 모델에서 장거리 상관이 나타나는 온도에 해당합니다.
Weitz의 자기 회피형 보행로 구성에서 자기 회피형 보행이 상관 관계 붕괴로 나타나는 이유를 볼 수 있습니다. 한계는 자기 회피형 보행 수의 근으로 정확하게 표현 될 수 있습니다. 따라서이 나무의 분기 요인이 충분히 작 으면 나무의 잎은 결국 무의미해진다.
“국소 경도”가 경도를 의미하는 경우, 자기 회피 보행의 성장 속도를 결정하는 특성을 정량화하는 것으로 충분합니다. 자기 회피 보행을위한 생성 기능에서 정확한 성장률을 추출 할 수 있지만 계산하기는 어렵습니다. 스펙트럼 반경은 계산하기 쉽고 하한을 제공합니다.
답변
일부 의견 : 대답이 아닙니다.
c
c
c∈[0,ϵ)
ϵ>0
c
c
c
그래프 클래스의 구조적 속성을 요구하여 문제를 계속 해결할 수 있습니다. 내가 알 수있는 한 거의 항상 힘들 것입니다. 그러나 이것은 매우 스케치적이고 더 많은 작업이 필요합니다.