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.
cc.complexity-theory
graph-theory
Florent Foucaud
fonte
fonte
Respostas:
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′= ( V∪ U, E′) G | U | = 3 | E |você | você| =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 ′G′ G G′
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 | =D′ G′ ( 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′ . Portanto, wlog, temos.|D′∩U|=|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=D′∩V x∈V x∉D′ a∈D′ (x,a)∈E′ (x,y)∈E (x,a,b,c,y) G′ a,b,c∈U a∈D′ C y ∈ D ' G y x y ∈ D D Lb,c∉D′ c y∈D′ G y x y∈D D é 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 ′D G 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′ é 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 ′ xG′ U x∈V∖D′ y∈V (x,y)∈E (x,a,b,c,y) a∈D′ x
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 kG k G′ k+|E| G′ k+|E| G k
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 ′G G′ G′
fonte