가중 된 채색을 계산하여 다음과 같이 적절한 채색을 계산하는 문제를 완화한다고 가정합니다. 모든 적절한 채색은 가중치 1이되고 모든 부적절한 채색은 가중치 여기서 는 일정하고 는 끝 점이있는 가장자리의 수는 동일하게 표시됩니다. 마찬가지로 0으로 진행하고,이 그래프의 많은 어려운 적절한 착색제를 계수로 감소시킨다. c가 1이면 모든 채색의 무게가 같고 문제는 사소합니다. 그래프의 인접 행렬에 를 곱한 경우 스펙트럼 반경이 미만인 경우cv

$c^v$c

$c$v

$v$c

$c$−log(c)/2

$-\log(c)/2$1−ϵ

$1-\epsilon$,이 합계는 수렴 보장을 통한 신념 전파에 의해 근사 될 수 있으므로 실제로는 쉽습니다. 이론적으로는 특정 계산 트리가 상관 관계의 붕괴를 나타내므로 근사를 보장하기위한 다항식 시간 알고리즘을 허용하기 때문에 이론적으로도 쉽다 -Tetali, (2007)

내 질문은-로컬 알고리즘 에서이 문제를 어렵게하는 그래프의 다른 속성은 무엇입니까? 작은 범위의 만이 다루어 질 수 있다는 점에서 어렵다 .c

$c$

편집 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에 가까워 질수록 장거리 상관 관계가 나타나기 때문에 관련이있는 것 같습니다.

답변