Qual é a complexidade desse problema de coloração de bordas?

Recentemente, encontrei a seguinte variante de coloração de borda.

Dado um gráfico não direcionado conectado, encontre uma coloração das arestas que use o número máximo de cores, além de satisfazer a restrição de que, para cada vértice , as arestas incidentes em usem no máximo duas cores. $v$ $v$

Meu primeiro palpite é que o problema é NP-difícil. As provas clássicas de NP-hard para problemas de coloração de gráficos são principalmente por redução do 3SAT. Mas, na minha opinião, essas provas não são úteis para esse problema, porque as arestas incidentes em um vértice podem ser coloridas com a mesma cor; portanto, não podemos construir componentes lógicos no gráfico.

Esse problema pode ser difícil para o NP? Se sim, o que é uma prova? Se não podemos multar uma prova, existe algum método para determinar a complexidade desse problema?

Obrigado!

cc.complexity-theory np-hardness complexity-classes graph-colouring RIC_Eien
fonte

Talvez a Coloração hipergráfica mista ou com cores possa ser um começo? Por exemplo, dx.doi.org/10.1016/j.disc.2008.04.019

András Salamon

Parece que seu problema está em P, em duas etapas: (1) seu problema é equivalente a encontrar um subconjunto de tamanho máximo das arestas, de modo que todo vértice tenha grau no máximo dois e (2) o último problema parece estar em P, digamos, redução à correspondência. Em relação a (1), observe que qualquer solução para o seu problema com k cores fornece um subgrafo grau 2 do tamanho k (apenas retenha uma aresta de cada cor) e, inversamente, qualquer subgrafo grau 2 do tamanho k fornece uma solução com cores k (basta colorir cada aresta no subgráfico com sua própria cor, colorir o restante das arestas com qualquer uma das cores). o que estou perdendo?

Neal Young

Lamento que haja vários erros na sua resposta. A princípio, o problema "encontrar um subconjunto de tamanho máximo das arestas, de modo que todo vértice tenha um grau no máximo dois", é NP-difícil, redução para 3SAT (eu realmente não sei como isso poderia ter uma redução na correspondência). Além disso, "qualquer subgrafo de grau 2 do tamanho k" não fornece "uma solução com k cores", por exemplo, Gráfico completo. Obrigado a todos.

RIC_Eien

Sim, você está certo. Sobre (2), a etapa "colora as demais arestas com qualquer uma das cores" pode fornecer arestas de três vértices. Separadamente, Marek Chrobak sugeriu o seguinte algoritmo para mim. Eu acho que dá uma aproximação de 3: (i) encontre um M máximo correspondente; (ii) colorir cada aresta em M com sua própria cor; (iii) colorir as bordas restantes de branco.

Neal Young

@RIC_Eien: Correndo o risco de mais vergonha. Você tem certeza de que "o problema 'de encontrar um subconjunto de tamanho máximo das arestas, de modo que todo vértice tenha grau no máximo dois', é NP-difícil"? Dado G = (V, E), crie bipartido G2 = (U, W, E2), onde para cada vértice v em V há v 'em U e v' 'em W, e E2 = {(u', w ''): (u, w) em E}. Então as correspondências em G2 correspondem aos conjuntos de arestas do grau 2 em G, e a correspondência preserva o tamanho? (Como cada ciclo k C em G corresponde em G2 a um ciclo 2k (se k ímpar) ou a dois ciclos k (se k par).) Portanto, a correspondência máxima em G2 a resolve. O que estou perdendo desta vez?

Neal Young

Qual é a complexidade desse problema de coloração de bordas?

Respostas: