Atingindo ciclos ímpares

14

Existe algo conhecido sobre o seguinte problema? Faz algum sentido? Como isso é chamado? É trivialmente equivalente a algum outro problema? Qual é a complexidade do tempo?

Dado um gráfico não direcionado (geral / plano / grau delimitado / etc.) G = (V, E), encontre um subconjunto máximo de arestas E ', de modo que G' = (V, E-E ') esteja conectado e toda aresta e em E 'existe um ciclo de comprimento ímpar em G contendo e, que não contém outra aresta em E'. (Considero apenas ciclos simples, ou seja, nenhum vértice aparece duas vezes)

Isso parece semelhante à bipartização, mas os resultados que eu vi são sobre o número mínimo de vértices / arestas que precisam ser removidos, enquanto eu quero o número máximo de arestas que podem ser removidas.

Por exemplo, o seguinte gráfico:

  * - * - * 
 /         \
* - * - * - *
 \         /
  * - * - *

Poderíamos cortar uma das arestas no caminho no meio, removendo todos os ciclos ímpares. No entanto, podemos fazer melhor removendo duas arestas, uma na ramificação superior e outra na inferior.

László Kozma
fonte
Uma questão relacionada - se tivermos uma aresta definida E 'e outra aresta e, podemos decidir rapidamente se todo ciclo ímpar que contém e evita E'?
Domotorp 14/05

Respostas:

7

|E|EE

David Eppstein
fonte