Capas Triângulo Mínimo

8

Dado um gráfico , qual é o número mínimo de arestas de G que precisamos excluir para tornar o triângulo livre? Para meus olhos destreinados, isso parece ser um problema difícil.GG

Esse problema é conhecido como NP-complete? E o analógico para gráficos orientados (isto é, dígrafos sem arestas paralelas) e 3 ciclos direcionados? As referências serão muito apreciadas!

EDIT: David respondeu muito útil à minha pergunta, no caso não direcionado, abaixo. Qualquer informação sobre a versão direcionada / orientada seria muito apreciada.

BPN
fonte

Respostas:

12

A versão não direcionada é NP-hard. Mais especificamente, o seguinte problema, conhecido como Conjunto de  arestas com feedback parcial, é NP-completo: dado um gráfico não direcionado  e números inteiros positivos K e L , existe um conjunto de no máximo K arestas que contém pelo menos uma aresta de cada ciclo de comprimento no máximo  L em  L . Isso ainda é NP-completo para qualquer L fixo 3 e se G  é restrito a ser bipartido (nesse caso, L  também pode ser fixo a qualquer valor de pelo menos  4 ).GKLKLGL3GL4

4k4

Fontes: A versão não direcionada é o problema GT9 de Garey e Johnson, Computers and Intratability (Freeman, Nova York, 1979). O artigo original era Yannakakis, problemas de NP com exclusão de nó e borda (Procedimentos de STOC 1978), mas não parece conter uma prova. A prova de Feedback Arc Set de Karp está na página do artigo "21 problemas": Redutibilidade entre problemas combinatórios (Anais do simpósio sobre Complexidade das Computações, 1972).

David Richerby
fonte
Muito Obrigado! (Quando eu pesquisei este problema, eu não tinha ideia do que para se qualificar "set borda de feedback" com para encontrar este.)
BPN