Bipartite Graph에서의 변형된 Vertex cover문제

  • Agidari
    Agidari

    사실 '변형된 vertex cover 문제'란건 제 맘대로 이름 붙인거구요 ㅎ

    오랫동안 생각을 하다 적절한 사이트를 찾아 질문을 올립니다 -_-;

    아마 알고리즘 공부를 하다 보면 한번쯤은 생각해보신 문제일거라 생각합니다..

    Bipartite Graph G(P, Q, E)가 있습니다. P와 Q는 각각 노드 집합이며 E는 P -> Q인 (뭐 undirectional이라도 상관없지만..) edge 집합입니다.

    이 때, P에서 최소 갯수의 노드를 골라 Q가 모두 선택되도록 하고 싶습니다.

    Vertex cover를 찾아보았으나 그 알고리즘은 노드를 P와 Q 모두에서 찾더군요..

    좋은 방법이 없을까요?ㅎ


    13년 전
5개의 댓글이 있습니다.
  • Being
    Being

    P의 각 정점이 만족시킬 수 있는 Q의 부분집합을 가질 텐데, 이 관점에서 생각하면 set cover 문제이므로 NP-complete로 보입니다.


    13년 전 link
  • Agidari
    Agidari

    허나 이 경우엔 bipartite graph라는 제약조건이 있지 않나요?

    bipartite graph에서의 vertex cover는 일반적인 vertex cover와는 달리 koenig algorithm에 의해 polynomial하게 풀리는 것 처럼, bipartite graph에서 돌아가는 알고리즘은 없을까요?


    13년 전 link
  • pinetree
    pinetree

    생각해보면 모든 Set cover문제를 Agidari님이 말씀하신 문제로 바꿀 수 있을거 같습니다.
    NPC에 한표.


    13년 전 link
  • Being
    Being

    네, pinetree님 말씀대로 그냥 완전히 같은 문제죠.


    13년 전 link
  • Being
    Being

    정정하자면 NP-complete가 아니라 NP-hard같군요. 그거나 그거나 지금 맥락에선 상관은 없지만요..


    13년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.