반복 압축

Iterative compression

컴퓨터 과학에서 반복 압축은 고정 매개변수 추적 가능한 알고리즘의 설계를 위한 알고리즘 기법으로, 각 단계에서 한 요소(그래프의 꼭지점 등)가 문제에 추가되고, 추가 전 문제에 대한 작은 해결책이 단계 이후 문제에 대한 작은 해결책을 찾는 데 도움이 된다.

이 기법은 리드, 스미스, 베타가[1] 정점, m 엣지, 홀드 사이클 횡단 숫자 k를 가진 그래프에 대해 O(3kmnk) 시간 내에 홀수 사이클 횡단 문제가 해결 가능하다는 것을 보여주기 위해 발명했다.홀수 사이클 횡단이란 모든 홀수 사이클에서 적어도 하나의 꼭지점을 포함하는 그래프의 가장 작은 정점 집합을 찾는 문제인데, 그 매개변수화된 복잡성은 오랫동안 열려 있던 질문이었다.[2][3]이 기술은 나중에 고정 매개변수 추적성 결과를 보여주는데 매우 유용하다는 것이 입증되었다.현재는 파라미터화된 알고리즘의 영역에서 기초 기법 중 하나로 간주되고 있다.

반복 압축은 많은 문제에서 성공적으로 사용되었는데, 예를 들어 홀수 사이클 횡단(아래 참조), 에지 양당화, 피드백 정점 세트, 클러스터 정점 삭제 및 방향 피드백 정점 세트 등이 그것이다.[4]독립 집합에 대한 정확한 지수 시간 알고리즘에도 성공적으로 사용되어 왔다.[5]

테크닉

예를 들어, 반복 압축은 그래프 G = (V,E)와 자연수 k인 매개변수화된 그래프 문제, 그리고 ≤ k 크기의 솔루션(정점 집합)의 존재를 시험하는 문제가 있는 경우에 적용된다.문제가 유도 서브그래프(특정 그래프에 크기 k k의 솔루션이 존재한다면, 이 크기 또는 작은 솔루션이 모든 유도 서브그래프에도 존재함)에 따라 닫히고, 크기 k + 1의 솔루션 Y를 더 작은 크기의 솔루션으로 압축할 수 있는지 여부를 결정하는 효율적인 서브루틴이 존재한다고 가정하자.

이러한 가정이 충족되면 유도 서브그래프에 정점을 한 번에 하나씩 더하고, 유도 서브그래프에 대한 해결책을 찾아 다음과 같이 문제를 해결할 수 있다.

  1. size k의 꼭지점 집합 S에 의해 유도된 서브그래프와 S 그 자체와 같은 용액 X로 시작하라.
  2. S ≠ V 상태에서 다음 단계를 수행하십시오.
    • v를 V \ S의 꼭지점으로 설정하고 v를 S에 추가
    • (k + 1)-vertex 솔루션 Y = X ∪ {x} ~ S)를 k-vertex 솔루션으로 압축할 수 있는지 테스트하십시오.
    • 압축할 수 없는 경우 알고리즘을 중단하십시오. 입력 그래프에는 k-Vertex 솔루션이 없다.
    • 그렇지 않으면 X를 새로운 압축 용액으로 설정하고 루프를 계속한다.

이 알고리즘은 압축 서브루틴을 선형 횟수라고 부른다.따라서 압축변형이 고정 매개변수 추적 가능한 시간, 즉 일정 c에 대해 f(k) · n으로c 해결 가능한 경우 전체 문제를 해결하는 반복적 압축 절차는 f(k) · n 시간에서c+1 실행된다.(유도 서브그래프가 아닌) 하위그래프에서 닫힌 그래프 속성이나 그래프 이론을 벗어난 다른 속성에 대해서도 동일한 기법을 적용할 수 있다.매개변수 k의 값을 알 수 없는 경우, 동일한 반복 압축 알고리즘을 기반으로 한 검색의 각 단계에서 k의 최적 선택을 위한 외부 수준의 지수 검색이나 순차 검색을 이용하여 찾을 수 있다.

적용들

원래의 논문에서 리드 등은 시간 O(3kmnk)에서 대부분의 정점을 삭제하여 그래프를 초당적으로 만드는 방법을 보여주었다.나중에 롯슈스타노프, 사우라브, 시크다르에 의해 반복 압축을 사용한 보다 단순한 알고리즘이 주어졌다.[6]크기 k + 1의 삭제 집합 Y를 크기 k의 삭제 집합 X로 압축하기 위해 이들의 알고리즘은 Y의 세k+1 칸막이를 모두 세 개의 하위 집합으로 시험한다. 즉, 새로운 삭제 집합에 속하는 Y의 부분집합과 X를 삭제한 후에도 남아 있는 양분 그래프의 양쪽에 속하는 Y의 부분집합이다.이 세 세트를 선택한 후에는 최대 흐름 최소 절단 알고리즘을 적용하여 삭제 세트 X의 나머지 정점(있는 경우)을 찾을 수 있다.

정점 커버는 반복 압축을 사용할 수 있는 또 다른 예다.꼭지점 표지 문제에서 그래프 G = (V,E)와 자연수 k는 입력으로 간주되며 알고리즘은 모든 가장자리가 X의 꼭지점에 입사하도록 k 정점의 X가 설정되었는지 여부를 결정해야 한다.문제의 압축 변종에서 입력은 그래프의 모든 가장자리에 입사하는 k + 1 정점의 집합 Y이며 알고리즘은 존재하는 경우 동일한 속성의 k 크기의 집합 X를 찾아야 한다.이를 위한 한 가지 방법은 표지에서 Y의 부분 집합을 제거하고 그래프에 다시 삽입할 두 가지k + 1 선택 사항을 모두 테스트하는 것이다.그러한 선택은 제거된 두 정점이 인접하지 않은 경우에만 작동할 수 있으며, 그러한 선택 각각에 대해 서브루틴은 이 제거에 의해 덮개가 벗겨지는 가장자리로 입사되는 Y 바깥의 모든 정점을 커버에 포함해야 한다.반복 압축 알고리즘에서 이 서브루틴을 사용하면 정점 커버에 대한 간단한 O(2k n2) 알고리즘이 제공된다.

참고 항목

  • 고정 매개변수 추적 가능한 알고리즘에 대한 다른 설계 기법인 커널화

참조

  1. ^ Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals", Operations Research Letters, 32 (4): 299–301, doi:10.1016/j.orl.2003.10.009, MR 2057781.
  2. ^ Niedermeier, Rolf, Invitation to Fixed-Parameter Algorithms, Oxford University Press, p. 184, ISBN 9780198566076
  3. ^ Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015). Parameterized Algorithms. Springer. p. 555. ISBN 978-3-319-21274-6..
  4. ^ Guo, Jiong; Moser, Hannes; Niedermeier, Rolf (2009), "Iterative compression for exactly solving NP-hard minimization problems", Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, vol. 5515, Springer, pp. 65–80, doi:10.1007/978-3-642-02094-0_4, ISBN 978-3-642-02093-3.
  5. ^ Fomin, Fedor; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket (2010), "Iterative compression and exact algorithms", Theoretical Computer Science, 411 (7): 1045–1053, doi:10.1016/j.tcs.2009.11.012.
  6. ^ Lokshtanov, 다니엘;Saurabh, 사켓;Sikdar, 솜 나트(2009년),"10월에 Simpler parameterized 알고리즘", 20일 국제 워크숍이 Combinatorial알고리즘, IWOCA 2009년, Hradec nad Moravicí, 체코, 6월 28–July 2인 2009년에 5874, 스프링거,를 대신하여 서명함. 380–384, vol. 선택 기술, 강의 노트 컴퓨터 과학으로, 합치하도록 수정되었다. doi:10.1007/978-3-642-10217-2_37, 아이 에스비엔 978-3-642-10216-5.