트리 폭

그래프 이론에서, 비방향 그래프의 트리 너비는 비공식적으로 그래프가 트리로부터 얼마나 멀리 떨어져 있는지를 지정하는 정수다.가장 작은 나무 너비는 1이다; 나무 너비가 1인 그래프는 정확히 나무와 숲이다.트리 너비가 최대 2인 그래프는 시리즈-병렬 그래프입니다.나무 너비가 정확히 k인 최대 그래프를 k-tree라고 하며, 나무 너비가 최대 k인 그래프를 부분 k-tree라고 한다.많은 다른 잘 연구된 그래프 가족들 또한 나무 너비를 경계했다.

트리 너비는 몇 가지 동등한 방법으로 공식적으로 정의될 수 있다: 그래프의 트리 분해에 설정된 가장 큰 꼭지점 크기, 그래프의 화음 완성에서 가장 큰 클라이크의 크기, 그래프에 추적-피션 게임의 전략을 설명하는 안식처의 최대 순서 또는 코의 집합인 브램블의 최대 순서.서로 만지는 연결되지 않은 서브그래프들

트리 폭은 일반적으로 그래프 알고리즘의 파라미터화된 복잡도 분석에서 파라미터로 사용된다.일반 그래프의 경우 NP-hard인 많은 알고리즘은 트리 너비가 상수에 의해 제한될 때 더 쉬워진다.

나무폭의 개념은 원래 움베르토 베르텔레와 프란체스코 브리오스키(1972)가 치수라는 이름으로 도입했다.나중에 다른 그래프 매개변수인 하드와이거 번호와 공유하는 속성을 바탕으로 루돌프 할린(1976년)에 의해 재발견되었다.후에 그것은 다시 닐 로버트슨과 폴 시모어(1984)에 의해 재발견되었고 그 후 많은 다른 작가들에 의해 연구되었다.^[1]

정의

그래프 G = (V, E)의 트리 분해는 X₁, ..., X 노드가_n 있는 T 트리로, 여기서 각 X는_i V의 서브셋으로, 다음 특성을^[2] 만족한다(노드는 G의 정점과의 혼동을 피하기 위해 T의 정점을 가리키는 데 사용된다).

1. 모든 집합 X의_i 조합은 V와 같다.즉, 각 그래프 꼭지점이 적어도 하나의 트리 노드에 포함되어 있다.
2. X와_i X가_j 모두 정점 v를 포함하는 경우, X와_i X_j 사이의 (유일) 경로에 있는 T의 모든 노드 X도_k v를 포함한다.마찬가지로, 꼭지점 v를 포함하는 트리 노드는 T의 연결된 하위 트리를 형성한다.
3. 그래프의 모든 에지(v, w)에 대해 v와 w를 모두 포함하는 부분 집합 X가_i 있다.즉, 정점은 해당 하위 트리에 공통 노드가 있을 때만 그래프에서 인접한다.

나무 분해의 너비는 가장 큰 집합 X에서_i 1을 뺀 값이다.그래프 G의 트리 너비 tw(G)는 G의 가능한 모든 트리 분해 중 최소 너비다.이 정의에서 가장 큰 집합의 크기는 나무의 나무 너비를 1과 같게 만들기 위해 1로 줄어든다.

동등하게, G의 트리 너비는 가장 작은 클라이크 수를 가진 G를 포함하는 화음 그래프에서 가장 큰 클라이크 크기보다 한 개 적다.이 클라이크 크기를 가진 화음 그래프는 둘 다 세트_i X 중 적어도 하나에 속하는 두 꼭지점 사이의 가장자리를 G에 추가함으로써 얻을 수 있다.

트리 너비는 또한 그래프에 정의된 특정 추적-피로 게임에 대한 회피 전략을 설명하는 기능인 안식처 측면에서 특징지어질 수 있다.A graph G has treewidth k if and only if it has a haven of order k + 1 but of no higher order, where a haven of order k + 1 is a function β that maps each set X of at most k vertices in G into one of the connected components of G \ X and that obeys the monotonicity property that β(Y) ⊆ β(X) whenever X ⊆ Y.

유사한 특성화는 모두 서로 접촉하는 연결된 서브그래프의 패밀리인 브램블(정점을 공유하거나 가장자리로 연결된다는 의미)을 사용하여 만들 수도 있다.^[3]브램블 순서는 서브그래프 계열의 가장 작은 타격 집합이며, 그래프의 트리 너비는 브램블의 최대 순서보다 1이 적다.

예

모든 전체 그래프 K에는_n treewidth n - 1이 있다.이것은 화음 그래프의 관점에서 나무 너비의 정의를 사용하는 것을 가장 쉽게 볼 수 있다: 완전한 그래프는 이미 화음이고, 가장자리를 더 추가하면 가장 큰 패거리의 크기를 줄일 수 없다.

최소 두 개의 정점이 있는 연결된 그래프는 트리인 경우에만 트리 너비 1을 가진다.트리는 완전한 그래프에 대한 것과 같은 추리에 의해 각각 나무 너비가 하나씩 있다(명칭, 그것은 화음이며, 최대 클라이크 크기 2를 가진다.반대로, 그래프에 주기가 있으면, 그래프의 모든 화음 완성에는 주기의 3개의 연속 정점으로 구성된 적어도 하나의 삼각형이 포함되며, 여기서부터 트리 너비는 2개 이상이다.

경계 트리 폭

경계 트리 너비가 있는 그래프 패밀리

고정 상수 k의 경우, 최대 k의 트리 너비 그래프를 부분 k-tree라고 부른다.경계 트리 너비가 있는 다른 그래프 제품군에는 선인장 그래프, 사이비 포리스트, 직렬-병렬 그래프, 외부 평면 그래프, 할린 그래프, 아폴로니아 네트워크가 포함된다.^[4]구조화 프로그램의 편성에서 발생하는 제어 흐름 그래프에도 테두리 트리 너비가 있어 레지스터 할당과 같은 특정 작업을 효율적으로 수행할 수 있다.^[5]

n × n 격자 그래프는 나무 너비가 정확히 n인 평면 그래프이기 때문에 평면 그래프에는 경계 트리 너비가 없다.따라서 F가 경계 트리 너비를 가진 마이너 폐쇄 그래프 계열이라면 모든 평면 그래프를 포함할 수 없다.반대로 F 계열의 그래프의 경우 일부 평면 그래프가 마이너로서 발생할 수 없는 경우, F의 모든 그래프는 최대 k의 트리 너비를 가질 수 있는 상수 k가 있다.즉, 다음과 같은 세 가지 조건이 서로 동등하다.^[6]

1. F는 경계 트리 너비 그래프의 마이너 폐쇄 계열이다.
2. F의 특징을 나타내는 많은 금지된 미성년자 중 하나는 평면이다.
3. F는 일부 평면 그래프를 포함하지 않는 마이너 폐쇄 그래프 계열이다.

금단의 미성년자

k의 모든 유한 값에 대해, 최대 k의 나무 너비의 그래프는 금지된 미성년자의 유한 집합으로 특징지어질 수 있다. (즉, 나무 너비 >k의 모든 그래프는 단조로 집합의 그래프 중 하나를 포함한다.)이러한 금지된 미성년자 세트에는 각각 적어도 한 개의 평면 그래프가 포함되어 있다.

• k = 1의 경우, 금지된 고유한 부차 그래프는 3-Vertex 사이클 그래프다.^[7]
• k = 2의 경우, 금지된 고유한 부차는 4-Vertex 전체 그래프 K이다₄.^[7]
• k = 3의 경우 금지된 미성년자 4명이 있는데, K₅, 팔면체 그래프, 오각형 프리즘 그래프, 바그너 그래프 등이다.이 중 2개의 다면 그래프는 평면이다.^[8]

k의 큰 값의 경우, 금지된 미성년자의 수는 적어도 k의 제곱근의 지수만큼 빠르게 증가한다.^[9]그러나 금지된 미성년자의 수와 크기에 대한 알려진 상한이 이 하한보다 훨씬 높다.^[10]

알고리즘

트리 너비 계산

주어진 그래프 G에 최대 주어진 변수 k의 트리 너비가 있는지 여부를 결정하는 것은 NP-완전이다.^[11]그러나 k가 고정된 상수일 경우 트리 너비 k가 있는 그래프를 인식할 수 있으며, 이를 위해 구성된 너비 k 트리 분해도 선형 시간 내에 인식할 수 있다.^[12]k에 대한 이 알고리즘의 시간 의존도는 기하급수적이다.

나무 너비가 엄청난 수의 분야에서 하는 역할 때문에, 그래프의 나무 너비를 계산하는 서로 다른 실제적이고 이론적인 알고리즘이 개발되었다.응용 프로그램에 따라 입력 크기나 트리 너비에서 더 나은 근사 비율을 선호하거나 실행 시간의 의존도를 높일 수 있다.아래 표에는 트리 너비 알고리즘의 개요가 나와 있다.여기서 $k{\displaystyle }$ ${\displaystyle$ $k$$}$은$($는) 트리 $,$ n {\$displaystyle$ g}은$(는)$ $입력$ 그래프 G {\$displaystyle$ G$\}$의 정점 수입니다$$. 각 알고리즘은 근사치 열에 주어진 ${\displaystyle 폭}$의 분해 시간$$ $f{\displaystyle }$( $)$ g$(n)$로 출력한다.For example, the algorithm of Bodlaender (1996) in time ${\displaystyle O(k^{O(k^{3})})\cdot n}$ either constructs a tree decomposition of the input graph ${\displaystyle G}$ of width at most ${\displaystyle k}$ or reports that the treewidth of ${\displaystyle G}$ is more than ${$$\displaystyle k}$. Similarly, the algorithm of Bodlaender et al. (2016) in time ${\displaystyle 2^{O(k)}\cdot n}$ either constructs a tree decomposition of the input graph ${\displaystyle G}$ of width at most ${\displaystyle 5k+4}$ or reports that the treewidth of ${\displaystyle G}$ is mor$k{\displaystyle }$ ${\displaystyle k}$보다$.$ Korhonen(2021)은 이를 동일한 실행 시간 내에$$ ${\displaystyle \mathrm{2k}}$+ $[\displaystyle 2k+1}$로 개선했다.

근사치	f(k)	g(n)	참조
정확한	${\displaystyle O(1)}$	${\displaystyle O(n^{k+2})}$	Arnborg, Corneil & Proskurowski (1987년)
$(\디스플레이 스타일 4kstyle 4k+3}$	${\displaystyle O(3^{3k}})}$	${\displaystyle O(n^{2})}$	로버트슨 & 시모어(1995)
$(\displaystyle 8k+7}$	${\displaystyle 2^{O(k\log k)}}}$	${\displaystyle n\log ^{2}n}$	리드(1992)
$5k+4}$	${\displaystyle 2^{O(k\log k)}}}$	${\displaystyle n\log n}$	라게르그렌(1996)
정확한	${\displaystyle k^{O(k^{3}}})}}$	${\displaystyle O(n)}$	보드렌더(1996)
${\displaystyle O(k\cdot {\sqrt {\log k})}$	${\displaystyle O(1)}$	${\displaystyle n^{O(1)}}$	Feige, Hajiahayi & Lee(2008)
$4.5k+4}$	${\displaystyle 2^{3k}}$	${\displaystyle n^{2}}$	아미르 (2010)
${\displaystyle {\frac {11}{3}k+4}$	${\displaystyle 2^{3.6982k}}$	${\displaystyle n^{3}\log ^{4}n}$	아미르 (2010)
정확한	${\displaystyle O(1)}$	${\displaystyle O(1.7347^{n})}$	포민, 토딘카 & 빌레인저(2015년)
${\displaystyle 3k+2}$	${\displaystyle 2^{O(k)}}}$	${\displaystyle O(n\log n)}$	보들렌더 외 (2016년)
$5k+4}$	${\displaystyle 2^{O(k)}}}$	${\displaystyle O(n)}$	보들렌더 외 (2016년)
${\displaystyle k^{2}}$	${\displaystyle O(k^{7})}$	${\displaystyle O(n\log n)}$	포민 외 (2018)
$5k+4}$	${\displaystyle 2^{8.765k}}$	${\displaystyle O(n\log n)}$	벨바시 & 총통 (2021a)
${\displaystyle 2k+1}$	${\displaystyle 2^{O(k)}}}$	${\displaystyle O(n)}$	코로넨(2021년)
$5k+4}$	${\displaystyle 2^{6.755k}}$	${\displaystyle O(n\log n)}$	벨바시 & 총통 (2021b)

평면 그래프의 트리 너비를 결정하는 것이 NP-완료인지, 아니면 그 트리 너비를 다항식 시간에 계산할 수 있는지 알 수 없다.^[13]

실제로 쇼이케트&게이거(1997)의 알고리즘은 최대 100정점, 최대 11정점까지 그래프의 트리 너비를 결정할 수 있어 최적의 트리 너비로 이들 그래프의 화음 완성을 찾을 수 있다.

작은 트리 너비의 그래프에서 다른 문제 해결

1970년대 초에는 그래프에 정의된 많은 종류의 조합 최적화 문제가 Bodlaender(1998년)에 의한 나무 너비에 해당하는 매개변수인 ^[14]경계 치수를 갖는 한, 비 직렬 동적 프로그래밍에 의해 효율적으로 해결될 수 있다는 것이 관찰되었다.이후, 여러 저자들은 1980년대^[15] 말에 독립적으로 관찰한 결과, 임의 그래프에 대해 NP-완전한 많은 알고리즘 문제가 이러한 그래프의 트리 구성을 사용하여 경계 트리 너비의 그래프에 대한 동적 프로그래밍을 통해 효율적으로 해결될 수 있다.

예를 들어, 가로폭 k의 그래프를 색칠하는 문제는 그래프의 트리 분해에 대한 동적 프로그래밍 알고리즘을 사용하여 해결할 수 있다.트리 분해의 각 세트 X와 X_i 정점의_i 각 분할에 대해 알고리즘은 해당 노드에 계산하여 저장한 유사한 유형의 정보를 결합하여 해당 색상이 유효한지 여부를 판단하고 트리 분해의 모든 하위 노드로 확장할 수 있는지 여부를 결정한다.결과 알고리즘은 시간 O(kn^{k + O(1)})의 n-vertex 그래프의 최적 색상을 찾는데, 이는 이 문제를 고정 파라미터를 추적할 수 있게 하는 시간 한계다.

쿠르셀의 정리

큰 등급의 문제의 경우 일정한 경계 트리 폭을 가진 트리 디포메이션이 제공되면 클래스에서 문제를 해결하는 선형 시간 알고리즘이 있다.구체적으로 Courcelle의 정리는^[16] 단색 2차 순서 논리를 사용하여 그래프 논리로 그래프 문제를 표현할 수 있다면, 경계 트리 너비가 있는 그래프에서 선형 시간으로 해결할 수 있다고 기술하고 있다.Monadic second order logic is a language to describe graph properties that uses the following constructions: logic operations (${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$), membership tests (e.g., ${\displaystyle e\in E,v\in V}$), quantifications over vertices, edges, sets of vertices, sets of edges(e.g., ${\displaystyle \forall }$ ${\displaystyle v\in V}$, ${\displaystyle \exists }$ ${\displaystyle e\in E}$, ${\displaystyle \exists }$ ${\displaystyle I\subseteq V}$, ${\displaystyle \forall }$ ${\displaystyle F\subseteq E}$), adjacency tests (u is an endpoint ofe) 및 최적화 등의 작업을 허용하는 일부 확장 기능.

예를 들어 그래프에 대한 3-색상 문제를 생각해 보십시오.그래프 $G{\displaystyle }$=${\displaystyle }$( ${\displaystyle V}$, ${\displaystyle E}$) ${\displaystyle G=(V,E)}$의 경우$,$ 이 문제는 인접한 두 정점 중 동일한 색상이 할당되지 않는 3가지 색상 중 하나의$$ 정점 v${\displaystyle v}$ V ${\displaystyle v\in V}$을(를) 할당할 수 있는지 묻는다.이 문제는 다음과 같이 단차순차논리로 표현할 수 있다.

${\displaystyle \exists W_{1}\subseteq V:\exists W_{2}\subseteq V:\exists W_{3}\subseteq V:\forall v\in V:(v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge }$

${\displaystyle \forall v\in V:\forall w\in V:(v,w)\in E\Rightarrow (\neg (v\in W_{1}\wedge w\in W_{1})\wedge \neg (v\in W_{2}\wedge w\in W_{2})\wedge \neg (v\in W_{3}\wedge w\in W_{3}))}$,

여기서$$ $W{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}{W\mathrm{}}_{}}$ 3 ${\$는 각각 3가지 색상을 가진 정점의 하위 집합을 나타낸다.따라서 쿠르셀의 결과에 의해, 경계 상수 트리 폭의 트리-디포메이션이 주어진 그래프의 경우 3-컬러링 문제를 선형 시간 내에 해결할 수 있다.

관련 매개변수

경로폭

그래프의 경로 너비는 나무 분해를 통한 나무 너비와 매우 유사한 정의를 가지지만, 분해의 기본 트리가 경로 그래프인 나무 분해로 제한된다.또는 구간 그래프에서 코드 그래프에서 트리 너비의 정의와 유사하게 경로 너비를 정의할 수 있다.그 결과, 그래프의 경로 폭은 항상 최소한 나무 폭만큼 크지만, 로그 인자에 의해서만 커질 수 있다.^[4]다른 파라미터인 그래프 대역폭은 적절한 간격 그래프에서 나온 유사한 정의를 가지고 있으며, 최소한 경로 폭만큼 크다.그 밖의 관련 매개변수에는 트리 깊이, 패밀리가 경로를 제외할 경우에만 마이너 닫힌 그래프 패밀리에 대한 경계수, 최대 트리 너비와 동일한 그래프의 스패리티 측정값인 퇴행성이 포함된다.

격자 보조 크기

n × n 격자 그래프의 트리 폭은 n이기 때문에 그래프 G의 트리 폭은 항상 G의 가장 큰 사각 격자 크기보다 크거나 같다.다른 방향에서 로버슨과 시모어의 격자 부차 정리는 나무 너비가 최대 f(r)이며 r은 가장 큰 사각 격자 부차 크기인 함수 f가 존재함을 보여준다.^[17]f에서 알려진 가장 좋은 한계는 f가 일부 고정 상수 d>0에 대해 Ω(r^d) 이상이어야 하며, 최대 O((r/log r)여야 한다는 것이다.^[18]제한적인 그래프 패밀리에 대해 더 엄격한 한계가 알려져 있으며, 이러한 패밀리에 대한 많은 그래프 최적화 문제에 대한 효율적인 알고리즘을 유도할 수 있다.^[19]할린의 그리드 정리는 무한 그래프에 대한 트리 너비와 그리드 마이너 크기 사이의 관계를 아날로그로 제공한다.^[20]

직경 및 로컬 트리 너비

서브그래프를 찍으면서 닫힌 그래프의 F 계열은 패밀리 내 그래프의 트리 폭이 직경의 함수에 의해 상한인 경우 로컬 트리 너비, 즉 직경 트리 너비 속성에 경계를 두었다고 한다.미성년자 취학 시에도 휴강한다고 가정할 경우 F는 F에 대해 금지된 미성년자 중 한 명이 꼭지점 그래프일 경우에만 국부 트리 너비를 경계한 것이다.^[21]이 결과의 원본 증거는 정점 미만이 아닌 그래프 계열의 나무 너비가 직경의 함수로서 최대 두 배로 기하급수적으로 증가한다는 것을 보여주었다;^[22] 나중에 이것은 단일 지수적으로^[19] 감소했고 마침내 선형 경계로 축소되었다.^[23]경계 로컬 트리 너비는 비등장성의 알고리즘 이론과 밀접하게 관련되어 있으며,^[24] 첫 번째 순서 로직에서 정의할 수 있는 모든 그래프 속성은 약간 초선형일 뿐인 시간 내에 정점-소선형 그래프 계열에 대해 결정할 수 있다.^[25]

미성년자 아래에서 닫히지 않은 그래프 클래스가 로컬 트리 너비에 경계를 두는 것도 가능하다.특히, 경계 직경 하위 그래프에는 경계 크기가 있으므로 경계 도 그래프의 클래스에 대해서는 이는 사소한 사실이다.또 다른 예는 1-평면 그래프, 즉 가장자리당 하나의 교차점이 있는 평면에서 그릴 수 있는 그래프, 그리고 가장자리당 경계 교차 횟수가 있는 경계 속 표면에서 그릴 수 있는 그래프에 대해 더 일반적으로 제시된다.경계 로컬 트리 너비의 마이너 폐쇄 그래프 패밀리와 마찬가지로, 이 속성은 이러한 그래프에 대한 효율적인 근사 알고리즘으로 가는 길을 가리켰다.^[26]

Hadwiger 번호와 S-기능

할린(1976)은 그가 S-기능이라고 부르는 그래프 파라미터의 클래스를 정의하는데, 여기에는 트리 너비가 포함된다.그래프에서 정수에 이르는 이러한 함수는 가장자리가 없는 그래프에서 0이 되어야 하며, 마이너 모노톤(H가 G의 마이너일 때마다 f(H) f f(G)가 있으면 함수 f가 "minor-monotone"이라 한다)이 되어야 하며, 이전의 모든 정점에 인접한 새로운 꼭지점이 추가될 때 1이 증가하고, 두 개의 하위 정점으로부터 더 큰 값을 얻어야 한다.파벌 분리기의 양쪽에 있는 진딧물그러한 모든 기능 세트는 요소별 최소화와 최대화의 작동 하에서 완전한 격자를 형성한다.이 격자의 맨 위 원소는 나무 너비, 맨 아래 원소는 주어진 그래프에서 가장 큰 완전한 단위의 크기인 하드와이거 수이다.

메모들

참조