La reducción de ciclo hamiltoniano dirigido a la coloración gráfico

Question

El problema 3-SAT puede reducirse a tanto el colorante gráfico y el problema ciclo hamiltoniano dirigido, pero ¿hay alguna cadena de reducciones que reducen dirigida ciclo de Hamilton a gráfico colorear en tiempo polinómico?

Answer 1

Vamos a $ Q \ en \ sf {NP} $ y $ Q' \ in \ {sf texto NP \ {-}} $ dura. Entonces, por definición, $ Q $ es (mucho-uno) reducible a $ Q '$ en tiempo polinómico.

La cadena exacta de la reducción dependerá de la SF $ \ {NP \ text {-}} $ dura prueba dad de $ $ Q '. Por lo general, se demuestra por una cadena de reducciones a partir de $ \ mathrm {SAT} $ y terminando con $ Q '$ y presionando el Cook-Levin teorema. Por lo que la cadena de la reducción será una reducción de $ Q $ y $ \ mathrm {SAT} $, seguido de la cadena de las reducciones de $ \ mathrm {SAT} $ a $ $ Q '.

Por lo general hay una reducción más directa para los problemas específicos (sin utilizar Cook-Levin), ya que por lo general es fácil encontrar una fórmula proposicional que expresa la propiedad requerida (sin referencia a TMS) directamente. Por ejemplo, en el caso de Directed Hamiltionian Path ($ \ mathrm {} $ DHP) y Gráfico para colorear ($ \ mathrm {CS} $), se puede reducir:

• $ \ mathrm {DHP} $ a $ \ mathrm {SAT} $,
• $ \ mathrm {SAT} $ a $ \ mathrm {3SAT} $,
• $ \ mathrm {3SAT} $ a $ \ mathrm {CS} $.