비차단기

흰색 꼭지점 집합은 최대 비차단자임

그래프 이론에서, 비차단기는 방향을 잡지 않은 그래프에서 정점의 부분집합이며, 모두 부분집합 바깥의 정점에 인접해 있다.마찬가지로, 비차단기는 지배적인 집합의 보완물이다.^[1]

그래프에서 가장 큰 비차단기를 찾는 연산 문제는 파파디미트리오 & 얀나카키스(1991)가 맥스SNP에 속한다고 관찰한 것에 의해 공식화되었다.^[2]지배적인 집합의 계산은 표준 가정 하에서 고정 매개변수를 추적할 수 있는 것은 아니지만, 주어진 크기의 비차단기를 찾는 보완적 문제는 고정 매개변수를 추적할 수 있다.^[1]

분리된 정점이 없는 그래프에서, 모든 최대 비차단기(정점이 더 이상 추가되지 않는 경우)는 그 자체가 지배적인 집합이다.^[3]

커널화

비차단기 문제에 대해 고정 매개변수 추적 가능한 알고리즘을 구성하는 한 가지 방법은 커널라이제이션(cernelization), 즉 다항식 시간 알고리즘을 사용하여 더 큰 문제 인스턴스를 매개변수의 함수에 의해 경계되는 동등한 인스턴스로 축소하는 알고리즘 설계 원리를 사용하는 것이다.비차단기 문제의 경우 문제에 대한 입력은 $그래프{\displaystyle }$ G ${\displaystyle G}$과$($와) 매개 변수 $k{\displaystyle }$ ${\displaystyle k$$}$로 구성되며, $목표$는 G ${\$$displaystyle$ $G$$}$에 $k{\displaystyle }$ {\$displaystyle$ k} 이상의$$ 정점이 있는 비차단기가 있는지$$ 확인하는 것이다.^[1]

이 문제는 커널라이제이션이 ${\displaystyle \mathrm{쉬워}}$ 최대 $(\displaystyle 2k}$정점까지$$ 동일한 문제로 축소된다.먼저 $G{\displaystyle }$ ${\displaystyle G}$에서 모든 분리된 정점을 제거하십시오$.$ 정점은 비차단기의 일부가 될 수 없기 때문이다.일단 이 작업이 완료되면, 나머지 그래프에는 정점의 절반 이상을 포함하는 비차단기가 있어야 한다. 예를 들어, 한 개의 색상이 그래프의 스패닝 트리를 2개 색상으로 표시할 경우 각 색 등급은 비차단이고 두 가지 색상 클래스 중 하나는 정점의 절반 이상을 포함한다.따라서 분리된 정점이 제거된 그래프가 ${\displaystyle \mathrm{여전히}}$ 2k ${\displaystyle$ 2k$}$개 이상의$$ 정점이 있으면 즉시 문제를 해결할 수 있다.그렇지 않으면 나머지 그래프는 정점이$$ ${\displaystyle \mathrm{최대}}$ $2k{\displaystyle \mathrm{}}$ ${\displaystyle 2k}$인 커널이다.^[1]

Dehne 등은 이것을 최대 5 ${\displaystyle 3}$ ${\displaystyle \frac{\mathrm{k}}{}}$+ ${\displaystyle 3}$ ${\displaystyle {\tfrac {5}{3}}k+3}$ 크기의 커널로 개선했다$.$그들의 방법은 모든 정점이 하나의 이웃을 가질 때까지 정점 1개의 이웃 쌍을 합병하고, 정점 1개를 제외한 모든 정점 1개를 제거하여 등가 인스턴스가 1도 1정점만 남도록 한다.그런 다음 (별도로 처리할 수 있는 $k{\displaystyle }$ ${\displaystyle k}$의 작은 값을 제외하고$)$ 이 인스턴스는 커널 크기 바운드보다 작거나 $k{\displaystyle }$ ${\displaystyle k}$ -vertex$$ 차단기를 포함해야 함을 보여준다.^[1]

일단 작은 커널을 얻으면, 비차단기 문제의 한 예는 커널에 대한 맹목적인 힘 검색 알고리즘을 적용하여 고정 매개변수 추적 가능한 시간에 해결될 수 있다.$더{\displaystyle }$ 빠른 시간 범위(${\displaystyle {}^{}}$ 여전히 ${\displaystyle {지수적}^{}}$인)를${\displaystyle \mathrm{적용}}$하면$$O(2.$5154$ k + n )${\displaystyle$O(2.5154^{k}+$n)}$ 형식의 비차단기 문제에 대한 시간 $바인딩$으로 이어진다$.$특정 등급의 그래프를 위해 더 빠른 알고리즘이 가능하다.^[1]

참조