Qual é a complexidade desse problema de subgráfico de borda máxima?

8

Ao discutir a pergunta que fiz aqui , @NealYoung e eu encontramos outro problema, que é julgar a complexidade do problema abaixo:

Dado um gráfico não direcionado conectado, localize um subconjunto de tamanho máximo das arestas, de modo que todo vértice tenha grau no máximo dois.

Eu encontrei algum artigo sobre a complexidade de problemas relativos. A maioria deles adicionou mais restrições ao original. O FOS03 adicionou "sem ciclos ímpares" e provou que é NP-difícil. CTW07 implicava que a variante adicionada "sem 3 ciclos" é P, referindo-se a outro artigo (que não encontrei). Mas não consegui julgar a complexidade do problema original. Então, como julgar? Obrigado.

RIC_Eien
fonte

Respostas:

14

O problema generalizado (de modo que cada vértice tenha grau no máximo b v ) é chamado de problema de correspondência b . O capítulo 31 do livro de Schrijver é dedicado ao assunto. Ele pode ser resolvido em tempo polinomial fortemente.vbvb

O caso em que para cada vértice v foi estudado, principalmente para fornecer limites mais baixos para o problema do vendedor ambulante .bv=2v

Austin Buchanan
fonte
Sim entendo. Obrigado pela sua resposta! Talvez você também possa dar alguma sugestão sobre a pergunta anterior vinculada no topo?
RIC_Eien
9
@RIC_Eien: Meu comentário não é muito sério, mas parece que você está muito feliz com a resposta. Se sim, por que você não pode aceitá-lo?
precisa saber é o seguinte