O problema do conjunto dominante está restrito a gráficos bipartidos planares de grau máximo 3 NP-completo?

18

Alguém sabe sobre um resultado de completude de NP para o problema DOMINATING SET em gráficos, restrito à classe de gráficos bipartidos planares de grau máximo 3?

Eu sei que é NP-completo para a classe de gráficos planares de grau máximo 3 (veja o livro de Garey e Johnson), bem como para gráficos bipartidos de grau máximo 3 (veja M. Chlebík e J. Chlebíková, "Dureza aproximada de problemas dominantes em gráficos de graus limitados "), mas não conseguiu encontrar a combinação dos dois na literatura.

Florent Foucaud
fonte
3
Na próxima vez, faça o link para a postagem original, se você fizer uma crosspost. mathoverflow.net/questions/43720/… . Veja também nossa entrada de perguntas frequentes sobre crossposting .
Tsuyoshi Ito
3
(1) Alguma coisa se sabe se você aumentar 3 para alguma outra constante? (2) Há algo conhecido sobre o caso especial em que o "grau máximo 3" é ainda mais restrito ao "3-regular"? (Sabe-se que está em P? Sabe-se que é equivalente ao caso do grau máximo 3?) (3) Por curiosidade, existe alguma aplicação disso ou você está interessado apenas por si mesmo? (Apenas no caso, eu não estou dizendo que um problema sem uma aplicação é ruim eu estou pedindo isso porque se você tem alguma aplicação, pode fazer a pergunta mais interessante..)
Tsuyoshi Ito
(1) Não é do meu conhecimento (2) Não. Mas espero que seja difícil (3) A única aplicação para mim seria obter a dureza NP de alguns outros problemas nessa mesma classe realmente restrita de gráficos
Florent Foucaud

Respostas:

24

E se você simplesmente fizer o seguinte: Dado um gráfico , construa outro gráfico subdividindo cada aresta de em 4 partes; aqui é o conjunto de novos nós que introduzimos e.G = ( V U , E ) GG=(V,E)G=(VU,E)G| U | = 3 | E |U|U|=3|E|

O gráfico é bipartido. Além disso, se é plano e tem max. grau 3, então também é plano e tem max. grau 3. G G GGG

Seja um conjunto dominante (mínimo) para . Considere uma aresta subdividida para formar um caminho em . Agora claramente pelo menos um de está em . Além disso, se tivermos mais de um de em , podemos modificar para que permaneça um conjunto dominante válido e seu tamanho não aumente. Por exemplo, se tivermos e , podemos igualmente remover de e adicionar aG ( x , y ) E ( x , a , b , c , y ) G a , b , c D a , b , c D D a D c D c D ' y D ' | D U | =DG(x,y)E(x,a,b,c,y)Ga,b,cDa,b,cDDaDcDcDyD. Portanto, wlog, temos.|DU|=|E|

Em seguida, considere . Suponha que e . Então devemos ter um nó tal que . Portanto, existe uma aresta tal que temos um caminho em . Como e , temos e, para dominar , devemos ter . Daí em nó é um vizinho de com . Ou seja,x V x D a D ( x , a ) E ( x , y ) E ( x , a , b , c , y ) G a , b , c U a D b , c DD=DVxVxDaD(x,a)E(x,y)E(x,a,b,c,y)Ga,b,cUaD C y D ' G y x y D D Lb,cDcyDGyxyDDé um conjunto dominando por .G

Por outro lado, considere um (mínimo) dominando conjunto para . Construa um conjunto dominante para para queda seguinte maneira: Para uma aresta subdividida para formar um caminho em , adicionamos a se e ; adicionamos a se e ; e, caso contrário, adicionamos a . Agora pode-se verificar queG D G | D ' | = | D | + | E | ( x , y ) E ( x , a , b , c , y ) G a D x D y D c D x D y D b D D DGDG|D|=|D|+|E|(x,y)E(x,a,b,c,y)GaDxDyDcDxDyDbDDé um conjunto dominante para : por construção, todos os nós em são dominados. Agora deixe . Então existe um tal que e, portanto, ao longo do caminho temos , que domina . U x V D y V ( x , y ) E ( x , a , b , c , y ) a D xGUxVDyV(x,y)E(x,a,b,c,y)aDx

Em resumo, se tem um conjunto dominante de tamanho , então tem um conjunto dominante de tamanho no máximoe se tiver um conjunto dominante de tamanho, então tem um conjunto de tamanho dominante no máximo .k G k + | E | G k + | E | G kGkGk+|E|Gk+|E|Gk

Edit: Adicionada uma ilustração. Superior: o gráfico original ; meio: gráfico com um conjunto dominante "normalizado"; embaixo: gráfico com um conjunto dominante arbitrário.G G GGG

Um exemplo

Jukka Suomela
fonte
1
Boa resposta.
Mohammad Al-Turkistany
Obrigado, isso responde muito bem à minha pergunta (mesmo sem as belas fotos;)) Alguém conhece alguma referência em que alguns outros problemas clássicos em gráficos NP-rígidos (por exemplo, Vertex Cover ou outros problemas de dominação) são estudados em gráficos planares bipartidos de grau limitado? Eu acho que isso deve ser interessante.
Florent Foucaud
2
Se responder à pergunta, talvez você deva aceitar a resposta ... :) Em relação a outros problemas, a cobertura de vértices é fácil em qualquer gráfico bipartido . Mas acho que conjuntos dominantes de borda podem ser um problema natural para estudar nesse cenário?
Jukka Suomela
Ok, obrigado por me lembrar o teorema de König e por marcar a caixa de seleção verde;)
Florent Foucaud
Resposta sólida Jukka!
Gabriel Fair