Qual é a complexidade desse problema de caminho?

12

Instância: Um gráfico não direcionado com dois vértices distintos s t e um número inteiro k 2 .Gstk2

Pergunta: Existe um caminho em G , de modo que o caminho toque no máximo k vértices? (Um vértice é tocado pelo caminho se o vértice estiver no caminho ou tiver um vizinho no caminho.)stGk

Andras Farago
fonte
1
Isso soa como uma minimização submodular restrita. Infelizmente, não está claro que o conjunto de restrições admita uma solução eficiente.
Suresh Venkat 16/02
Minha resposta de provavelmente estava incorreta! Depois de verificar com mais cuidado, a heurística não parece monótona. A
usul
1
Seguindo o comentário de Suresh, vale a pena conferir o artigo "Aproximabilidade de problemas combinatórios com funções de custo submodular de múltiplos agentes", que mostra que o caminho mais curto do custo submodular é difícil. Talvez existam idéias que demonstrem dureza. computer.org/csdl/proceedings/focs/2009/3850/00/…
Chandra Chekuri 17/02/02
1
Esse problema pode ser reformulado ao encontrar um subgrafo da lagarta com no máximo vértices que inclui s e t em seu caminho mais longo. kst
Obinna Okechukwu
@Obinna o sub-grico lagarta é necessário para ser mima num sentido, porque deve incluir todos os vizinhos do caminho mais longo
SAMM

Respostas:

14

Este problema foi estudado em:

Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg: Problemas de conectividade isolados. SEC 2013: 301-312.

http://arxiv.org/pdf/1212.6176v1.pdf

Eles chamaram isso de problema de caminho isolado. É realmente NP-difícil, e a versão de otimização não tem aproximação de fator constante.

A motivação que os autores fornecem é uma configuração em que as informações são enviadas pelo caminho, e somente os vizinhos e os nós no caminho podem vê-las. O objetivo é minimizar a exposição.

user20655
fonte
10

Editar: Consulte a resposta do usuário20655 abaixo para obter uma referência a um artigo que já comprove a dureza desse problema. Deixarei minha postagem original, caso alguém queira ver essa prova alternativa.

===============

X={x1,x2,xn}C={c1,c2,c3,}

xicim=2n+|C|mp1,p2,,pm

stxixi¯cjpicj

xicjxixi¯cjxi¯xixi¯xi+1xi+1¯sx1x1¯txnxn¯cipj

Construção da instância difícil

{Pi}cjcj

Q+2n+2Q

  1. styi{xi,xi¯}yi+1{xi+1,xi+1¯}xixi¯i1,,n(isso é intuitivo, pois excluir uma das duas opções de qualquer variável escolhida duas vezes gera um caminho válido com custo não maior do que mantivemos os dois).
  2. m+2s,x1,x2,,xn,tst{xi}{xi¯}{ci} ststcixixj{p}m+5
  3. stcjcjQQcj
  4. xixi¯st2n+2ciQ

kk+2n+2

Yonatan N
fonte