info.info-cc
Julio Araujo 
email: juliocesar@lia.ufc.br
  
Manoel Campêlo 
email: mcampelo@lia.ufc.br
  
Phablo Moura 
email: phablofsm@lia.ufc.br
  
Sobre 
  
J Úlio César 
  
Ara Újo 
  
A, E), onde G M = (v 
  
  
  
  
  
  
  
  
  
  
  
Sobre a complexidade de coloração mista

 

Introduc ¸ão

O problema de colorac ¸ão de grafos [START_REF] De Bruijn | A colour problem for infinite graphs and a problem in the theory of relations[END_REF] é certamente um dos mais estudados na área de Teoria de Grafos devido às suas várias aplicac ¸ões, principalmente em problemas de escalonamento, como, por exemplo, nos problemas de atribuic ¸ão de freqüências a antenas de rádio ou telefonia, de alocac ¸ão de produtos químicos em armazéns e de alocac ¸ão de registros em compiladores.

Dado um grafo G = (V, E), uma colorac ¸ão é uma func ¸ão c : V -→ Z que associa a cada vértice do grafo um número inteiro representativo de uma cor. Dizemos que uma colorac ¸ão é própria se, para cada par de vértices adjacentes u e v, i.e., [u, v] ∈ E(G), temos c(u) = c(v). Uma colorac ¸ão (própria) de um grafo G com k cores é comumente chamada de uma k-colorac ¸ão de G.

No problema clássico de Colorac ¸ão de Vértices, busca-se determinar a menor quantidade de cores para a qual o grafo admite uma colorac ¸ão própria. Essa quantidade é chamada número cromático, ou χ(G).

Determinar o número cromático de um grafo qualquer é um problema NP -Difícil [START_REF] Karp | Reducibility among combinatorial problems[END_REF], mas em várias classes de grafos a determinac ¸ão desse parâmetro pode ser feita em tempo polinomial. Existem diversas variac ¸ões deste problema. Aqui, estudamos uma generalizac ¸ão do mesmo para grafos mistos, ou seja, grafos que podem ter simultaneamente arestas não-orientadas e orientadas (estas últimas chamadas de arcos). Sendo assim, um grafo misto pode ser definido por uma tripla G M = (V, A, E), onde V , A e E denotam o conjunto de vértices, arcos e arestas de G M , respectivamente. Dado um grafo misto G M = (V, A, E), uma k-colorac ¸ão mista é uma func ¸ão c : V → {0, . . . , k -1} com as seguintes restric ¸ões:

1. c(v i ) < c(v j ), se (v i , v j ) ∈ A. 2. c(v i ) = c(v j ), se [v i , v j ] ∈ E.
Em outras palavras, uma colorac ¸ão mista forte é uma colorac ¸ão própria com uma restric ¸ão de ordem sobre as cores das extremidades de cada arco. Em alguns trabahos, esta colorac ¸ão é chamada de mista forte em contra-ponto à colorac ¸ão mista fraca, onde se permite uma desiguldade não-estrita (≤) na condic ¸ão (1) acima.

No problema de Colorac ¸ão Mista, dado um grafo misto G M = (V, A, E), desejamos encontrar o número cromático misto de G M , denotado por χ M (G M ), que é o menor inteiro k tal que G M admite uma k-colorac ¸ão mista. Observe que o problema é inviável se G M possui um ciclo orientado. Ao longo de todo o texto, vamos assumir então que tal não ocorre. Uma das motivac ¸ões para a definic ¸ão de Colorac ¸ão Mista encontra-se no estudo de problemas de escalonamento de tarefas com restric ¸ão de precedência e compartilhamento de recursos, em particular o problema de Job-Shop.

Uma instância do problema de Job-Shop é composta por um conjunto de tarefas J = {J 1 , J 2 , . . . , J n }, onde cada tarefa J k , para todo 1 ≤ k ≤ n, possui um conjunto de operac ¸ões que devem ser processadas em uma certa ordem, definindo, assim, relac ¸ões de precedência. Cada operac ¸ão deve ser executada em uma máquina do conjunto M = {M 1 , M 2 , . . . , M m } e toma uma unidade de tempo para sua execuc ¸ão. Como cada máquina só pode executar uma operac ¸ão por vez, surgem assim restric ¸ões de compartilhamento de recursos. Em Job-Shop busca-se determinar a menor quantidade de tempo para se processar todas as tarefas do conjunto J.

Uma instância desse problema pode ser modelada com um grafo misto G M = (V, A, E), onde V é o conjunto de operac ¸ões, A descreve as relac ¸ões de precedência, e uma aresta [u, v] ∈ E é definida se as operac ¸ões u e v compartilham uma máquina. Toda colorac ¸ão mista de G M descreve um escalonamento viável, onde a cor de um vértice representa o tempo de execuc ¸ão da operac ¸ão correspondente. O número cromático misto expressa o tempo mínimo necessário para a execuc ¸ão de todas as tarefas.

Neste trabalho, estudamos a complexidade do problema de Colorac ¸ão Mista em três classes de grafos: cordais, linha de bipartidos e linha de periplanares. Os resultados obtidos são apresentados na Sec ¸ão 3. Antes, porém, realizamos uma breve revisão bibliográfica sobre o problema. Na Sec ¸ão 4 comentamos os nossos resultados e suas implicac ¸ões.

Resultados Conhecidos

Nesta sec ¸ão, revisamos alguns resultados da literatura que avaliam a complexidade do problema de colorac ¸ão mista e destacamos relac ¸ões deste com outros problemas em grafos. Chamamos de grafo subjacente a G M o grafo G = (V, Ā ∪ E), onde uma aresta [u, v] ∈ Ā se, e somente se, o arco (u, v) ∈ A. Em outras palavras, G é o grafo obtido de G M retirando-se as orientac ¸ões de seus arcos.

Alguns resultados sobre complexidade

Colorac ¸ão Mista generaliza o tradicional problema de Colorac ¸ão de Vértices, que equivale ao caso onde o conjunto de arcos é vazio. Por outro lado, quando o conjunto de arestas é vazio, Colorac ¸ão Mista equivale ao problema de encontrar o maior caminho em um grafo direcionado acíclico.

Por generalizar o problema de colorac ¸ão de vértices, Colorac ¸ão Mista é claramente um problema NP -Difícil. Outros resultados de complexidade para classes específicas de grafos também são conhecidos, conforme abaixo. Sem perda de entendimento, vamos dizer que G M pertence a uma certa classe, quando a rigor deveríamos nos referir ao seu grafo subjacente.

A versão de decisão do problema de colorac ¸ão mista classifica-se como um problema NPcompleto, mesmo se o grafo for planar, bipartido, com grau máximo 4 e cada vértice incidente a um arco com grau máximo 2. Isto é demonstrado a partir de uma reduc ¸ão do problema de Colorac ¸ão por Listas [START_REF] Ries | On two coloring problems in mixed graphs[END_REF].

Por outro lado, para as classes de grafos série-paralelos e árvores, são conhecidos algoritmos com tempo de execuc ¸ão polinomial que determinam uma soluc ¸ão exata. No caso das árvores, o primeiro algoritmo encontrado na literatura [START_REF] Hansen | Mixed graph colorings[END_REF] tem complexidade O(n 2 ) enquanto que o algoritmo descrito em [START_REF] Furmanczyk | A note on mixed tree coloring[END_REF] tem complexidade linear. Para grafos série-paralelos, é conhecido um algoritmo com complexidade O(n 3.376 log n) que fornece uma soluc ¸ão ótima [START_REF] Furmanczyk | Scheduling with precedence constraints: Mixed graph coloring in series-parallel graphs[END_REF]. Adicionalmente, é conhecido que a versão de decisão do problema de colorac ¸ão mista tem complexidade polinomial se o grafo misto dado como entrada é uma k-árvore parcial, para um k fixo [START_REF] Ries | On two coloring problems in mixed graphs[END_REF].

Limites para o n úmero cromático misto

Em [START_REF] Hansen | Mixed graph colorings[END_REF] foram demonstrados dois limites superiores para o número cromático misto, relacionandoo ao número cromático de subgrafos do grafo subjacente. Para apresentarmos tais resultados, considere as definic ¸ões a seguir.

Dado um subconjunto V ′ do conjunto de vértices de um grafo G = (V, E), dizemos que o

subgrafo induzido (em vértices) por V ′ ⊆ V , denotado por G[V ′ ], é o subgrafo G ′ = (V ′ , E ′ ) de G tal que se [u, v] ∈ E e u, v ∈ V ′ então [u, v] ∈ E ′ . Seja X M o conjunto dos vértices de G M = (V, A, E) que são extremidades de algum arco de A. Seja G o grafo subjacente de G M . Então: Proposic ¸ão 2.1 χ M (G M ) ≤ χ(G) + |X M | -χ(G[X M ]) Além disso, defina o grafo misto G * = (X M , A * , ∅), onde A * = {(v i , v j ) ∈ A : v i , v j ∈ X M }. Então: Proposic ¸ão 2.2 χ M (G M ) ≤ χ M (G * )(χ(G) -1) + 1
Vale ressaltar que ambos os limites são atingidos por algumas instâncias do problema. Observe que a Proposic ¸ão 2.1 apresenta um limite que relaciona número cromático misto, número cromático do grafo subjacente e parâmetros que só dependem das orientac ¸ões de G M . Por outro lado, é interessante observar que a Proposic ¸ão 2.2 relaciona também o χ M (G M ) com χ(G), mas, nesse caso, o limite envolve parâmetros que dependem do conjunto de arestas de G M .

Com relac ¸ão a limites inferiores, é fácil observar que χ M (G M ) é pelo menos o tamanho do maior caminho direcionado em G M , denotado por n(G M ). Além disso, toda colorac ¸ão mista de G M é, por sua vez, uma colorac ¸ão própria do grafo subjacente de G M . Logo, o número cromático do grafo subjacente também define um limite inferior para χ M (G M ). Outros limites inferiores baseados em estruturas do grafo subjacente (como cliques) podem ser encontrados em [START_REF] Lima | Limites para a altura mínima de extensões induzidas de posets[END_REF]. 

Complexidade

Problemas de decisão

Grafos cordais

Um grafo G é dito cordal se ele não possui buracos como subgrafo induzido. Um buraco é um ciclo de tamanho pelo menos 4 sem uma aresta ligando um par de vértices não consecutivos no ciclo.

Proposic ¸ão 3.1 Seja

G M um grafo misto e k ≥ n(G M ). Então, CM(G M , k) é NP-Completo,
mesmo se o grafo subjacente de G M é um grafo cordal.

Prova: A reduc ¸ão segue do problema P reCol(G, V ′ , k, c ′ ) que é NP -Completo para grafos de intervalos unitários que é uma subclasse dos grafos cordais [START_REF] Marx | Precoloring extension on unit interval graphs[END_REF].

Seja I = (G, V ′ , k, c ′ ) uma instância para esse problema. Defina a instância (G M , k) para o problema CM(G M , k), onde G M é o grafo misto obtido a partir de G quando, para cada vértice v i ∈ V ′ , adicionamos a G o caminho direcionado P i = (x 0 i , . . . , x j-1 i , v i , x j+1 i , . . . , x k-1 i ), onde j = c ′ (v i ) (ver Figura 1). Em outras palavras, sendo G = (V, E), então G M = (V \V ′ ∪ v i ∈V ′ V i , v i ∈V ′ A i , E), onde V i e
A i são os conjuntos de vértices e arcos de P i , respectivamente.

vi c'(v)=j i (a) P reCol(G, V ′ , k, c ′ )
... 

x i 0 ... x i k-1 x i j+1 vi x i j-1 (b) CM (G M , k)

Grafo linha de bipartido

Dado um grafo não direcionado G, seu grafo linha, denotado por L(G), é tal que cada vértice de L(G) representa uma aresta de G e dois vértices de L(G) são adjacentes se, e somente se, suas arestas correspondentes tem uma extremidade em comum. Note que uma colorac ¸ão própria das arestas de G corresponde a uma colorac ¸ão própria dos vértices de L(G). Para mostrarmos que CM(G M , k) é NP -completo em grafos linha de bipartidos, vamos usar uma transformac ¸ão definida a seguir.

Seja (G, E ′ , k, c ′ ) uma instância do problema P reColA. Defina outra instância (G, E ′ , k, c ′ ) de tal modo que G = (V , E) é o grafo obtido de G = (V, E) da seguinte forma: para cada aresta e i = [v 1 i , v 2 i ] ∈ E ′ , remova e i , adicione dois vértices u 1 i , u 2 i e duas novas arestas e ′ i = [v 1 i , u 2 i ] e e ′′ i = [u 1 i , v 2 i ] que são pré-coloridas com a mesma cor c ′ (e i ). Logo, V = V ∪ |E ′ | i=1 {u 1 i , u 2 i }, E ′ = |E ′ | i=1 {e ′ i , e ′′ i }, E = (E\E ′ ) ∪ E ′ e c ′ (e ′ i ) = c ′ (e ′′ i ) = c ′ (e i ).
A construc ¸ão dessa outra instância está ilustrada pela Figura 2.

Lema 3.1 G admite uma extensão da pré-colorac ¸ão c ′ para uma colorac ¸ão com no máximo k cores se, e somente se, G admite uma extensão da pré-colorac ¸ão c ′ para uma colorac ¸ão com no máximo k cores. Prova: Fazemos a reduc ¸ão a partir do problema de Extensão de Pré-colorac ¸ão em arestas que é NP-Completo em grafos bipartidos [START_REF] Marx | NP -completeness of list coloring and precoloring extension on the edges of planar graphs[END_REF]. Seja (G, E ′ , k, c ′ ) uma instância de P reColA, sendo G = (V, E) um grafo bipartido, e seja (G = (V , E), E ′ , k, c ′ ) uma outra instância para o mesmo problema obtida pelo procedimento descrito anteriormente. Pela construc ¸ão de G, nenhum ciclo ímpar é criado. Logo, G também é bipartido. Seja (G M , k) uma instância para o problema CM, sendo G M o grafo gerado a partir de L(G) quando adicionamos, para cada vértice v i associado a uma aresta e i pré-colorida em G,

ei v i 1 v i 2 (a) P reColA(G, E ′ , k, c ′ ) e' i v i 1 v i 2 e'' i u i 1 u i 2 (b) P reColA(G, E ′ , k, c ′ )
um caminho direcionado P i = (x 0 i , . . . , x j-1 i , v i , x j+1 i , . . . , x k-1 i ) e um arco (x j-1 i , x j+1 i ), onde j = c ′ (e i ). A Figura 3 ilustra esta reduc ¸ão. ei c'(e)=j i (a) P reColA(G, E ′ , k, c ′ ) vi (b) L(G)
... Observe que G admite uma extensão de sua pré-colorac ¸ão em arestas para uma colorac ¸ão com k cores se, e somente se, G M admite uma colorac ¸ão mista com k cores, uma vez que os caminhos direcionados forc ¸am que cada vértice de G M que está relacionado a uma aresta précolorida de G receba a mesma cor desta. Logo, uma k-colorac ¸ão nos vértices de G M determina uma k-colorac ¸ão nos vértices de L(G) e, portanto, uma k-colorac ¸ão nas arestas do grafo G.

x i 0 ... x i k-1 x i j+1 vi x i j-1 (c) CM (G M , k)
y i 0 y i j-1 ... y i k-1 y i j+1 (a) G * ... x i 0 ... x i k-1 x i j+1 vi x i j-1 (b) L(G * )
Pelo lema anterior, temos uma k-colorac ¸ão para o grafo G.

Grafo linha de periplanar

Um grafo é dito planar se admite uma representac ¸ão no plano sem cruzamento de suas arestas. Nessa representac ¸ão, cada região limitada pelas arestas, incluindo a região ilimitada, é chamada face. A face externa é exatamente a região ilimitada. Um grafo planar é dito periplanar se possui uma representac ¸ão no plano onde todo vértice pertence à face externa, ou seja, é extremidade de alguma aresta limitando esta face. Proposic ¸ão 3.3 Seja G M um grafo misto e k ≥ n(G M ). Então, CM(G M , k) é NP-Completo, mesmo se o grafo subjacente de G M é um grafo linha de um grafo periplanar.

Prova: A demonstrac ¸ão é análoga àquela da Proposic ¸ão 3.2. Novamente fazemos a reduc ¸ão a partir do problema de Extensão de Pré-colorac ¸ão em arestas que é NP-Completo em grafos periplanares [START_REF] Marx | NP -completeness of list coloring and precoloring extension on the edges of planar graphs[END_REF]. Seja (G, E ′ , k, c ′ ) uma instância de P reColA, sendo G = (V, E) um grafo periplanar, e seja (G = (V , E), E ′ , k, c ′ ) uma outra instância para o mesmo problema obtida conforme Subsec ¸ão 3. 

Conclusão

Neste trabalho, apresentamos resultados de complexidade para o problema de Colorac ¸ão Mista, mostrando que o mesmo é NP -difícil para as classes de grafos cordais, grafos linha de bipartidos e grafos linha de periplanares. Vale lembrar que, como consequência, Colorac ¸ão Mista também é NP -difícil para todas as classes de grafos que contêm essas classes estudadas, como, por exemplo, grafos livres de C 4 ou C 5 , grafos livres de garra, grafos-aranha, grafos perfeitos. Estendemos, assim, resultado similar existente na literatura, que mostra a mesma complexidade para a classe dos grafos bipartidos planares. Adicionalmente, identificamos também outras classes de grafos onde o problema clássico de colorac ¸ão é polinomial, mas passa a ser NP -difícil na versão mista.

Um ponto importante a ser observado encontra-se no fato de que, como acontece em outros trabalhos relacionados, a complexidade é estudada considerando o grafo subjacente. Isto significa que relac ¸ões entre os conjuntos de arcos e de arestas não são exploradas. A influência desse fator na complexidade do problema é uma questão que merece ser melhor estudada.

  Consideramos a seguinte versão de decisão de Colorac ¸ão Mista: Problema 1 (CM(G M , k) -Colorac ¸ão Mista)Entrada: Um grafo misto G M = (V, A, E) com E = ∅, e um inteiro k ≥ n(G M ). Questão: G M admite uma k-colorac ¸ão mista?É fácil ver que CM(G M , p) está na classe NP . Nas subsec ¸ões seguintes, vamos mostrar que CM(G M , p) é NP -completo em algumas classes de grafos. Em todos os casos fazemos reduc ¸ões a partir de problemas de Extensão de Pré-colorac ¸ão a seguir definidos:Problema 2 (P reCol(G, V ′ , k, c ′ ) -Extensão de Pré-colorac ¸ão de Vértices) Entrada: Um grafo G = (V, E), um subconjunto V ′ ⊂ V , um inteiro k e uma colorac ¸ão c ′ : V ′ → {0, . . . , k -1}. Questão: Existe uma k-colorac ¸ão própria c de G que estenda a colorac ¸ão c ′ (i.e., c(v) = c ′ (v) ∀v ∈ V ′ )?Uma k-colorac ¸ão (própria) em arestas de um grafo G = (V, E) é uma func ¸ão c : E → {0, . . . , k -1} de tal modo que se duas arestas a e b possuem uma extremidade em comum, então c(a) = c(b). Problema 3 (P reColA(G, E ′ , k, c ′ ) -Extensão de Pré-colorac ¸ão de Arestas) Entrada: Um grafo G = (V, E), um subconjunto E ′ ⊂ E, um inteiro k e uma colorac ¸ão c ′ : E ′ → {0, . . . , k -1}. Questão: Existe uma k-colorac ¸ão própria c das arestas de G que estenda a colorac ¸ão c ′ (i.e., c(e) = c ′ (e), para toda aresta e ∈ E ′ )?

Figura 1 :

 1 Figura 1: Reduc ¸ão para grafos cordais

Figura 2 :

 2 Figura 2: Instâncias equivalentes de P reColA

Figura 3 :

 3 Figura 3: Reduc ¸ão para grafos linha de bipartidos Vamos mostrar que o grafo subjacente de G M é linha do grafo bipartido G * obtido a partir de G da seguinte maneira. Para cada aresta e i ∈ E ′ , seja u i o vértice de grau 1 (isto ocorre devido a construc ¸ão de G). Adicione um caminho T i = (y 0 i , . . . , y j-1 i , u i , y j+1 i , . . . , y k-1 i ), onde

Figura 4 :

 4 Figura 4: Construc ¸ão de G * e seu grafo linha

3 . 1 i 1 i).

 311 Pela construc ¸ão de G, é fácil observar que G ainda é periplanar. De fato, dada uma representac ¸ão planar de G onde todos os vértices pertencem à face externa, é possível adicionar os vértices de V \V a essa representac ¸ão de tal modo que todos os vértices ainda pertencem à face externa. Para tanto, basta representar no plano os novos caminhos na face externa. Veja que essa representac ¸ão não adiciona novas faces e todos os vértices continuam pertencendo à face externa. Seguindo os mesmos passos da demonstrac ¸ão anterior, seja (G M , k) uma instância para o problema CM, onde G M o grafo gerado a partir de L(G) quando adicionamos um caminho direcionado P i = (x 0 i , . . . , x j-cada vértice v i associado a uma aresta pré-colorida por c ′ , digamos com a cor j. Vamos mostrar que o grafo subjacente de G M é linha do grafo periplanar G * , obtido a partir de G da seguinte maneira: para cada aresta e i ∈ E ′ , se j = c ′ (e i ) e u i é o vértice de grau 1 de e i , adicione um caminho T i = (y 0 i , . . . , y j-1 i , u i , y j+1 i , . . . , y k-Note que G * é claramente periplanar, pelo mesmo argumento apresentado para demonstrar que G é periplanar. Por último, veja que L(G * ) é exatamente o grafo subjacente de G M . Novamente, podemos afirmar que G admite uma extensão de sua pré-colorac ¸ão em arestas para uma colorac ¸ão com k cores se, e somente se, G M admite uma colorac ¸ão mista com k cores, uma vez que os caminhos direcionados forc ¸am que cada vértice de G M que está relacionado a uma aresta pré-colorida de G receba a mesma cor desta. Logo, uma k-colorac ¸ão nos vértices de G M determina uma k-colorac ¸ão nos vértices de L(G) e, portanto, uma k-colorac ¸ão nas arestas do grafo G. Pelo lema anterior, temos uma k-colorac ¸ão para o grafo G.