Una pregunta sobre extensiones lineales de órdenes parciales

Si le dan una colección de órdenes parciales, la clasificación topológica le dirá si hay una extensión de la colección a una orden total (una extensión en este caso es una orden total consistente con cada una de las órdenes parciales).

Me he encontrado con una variación:

Fijar un conjunto . Te dan secuencias de elementos extraídos de sin repetición (las secuencias tienen una longitud entre 1 y ). $V$ $\sigma_1, \ldots \sigma_k$ $V$ $|V|$

¿Hay alguna manera de arreglar las orientaciones para cada una de las secuencias (ya sea hacia adelante o hacia atrás) de modo que la colección resultante de cadenas (vista como un orden parcial) admita una extensión?

¿Es bien conocido este problema?

Nota: La orientación se elige para una secuencia completa. Entonces, si la secuencia es , puede mantenerla de esa manera o a , pero no puede hacer nada más. $1-2-4-5$ $5-4-2-1$

ds.algorithms reference-request order-theory Suresh Venkat
fuente

Si cada una de las secuencias tiene una longitud , se puede pensar en cada secuencia como un borde no dirigido y estamos preguntando si un gráfico no dirigido puede orientarse para ser un DAG, si no hay un ciclo. Pero un algoritmo codicioso también funciona. Comience con un borde y oriéntelo arbitrariamente y continúe todo el tiempo que pueda y si se atasca, sabe que no es posible. ¿Intentaste eso para tu variación? Parece que puede funcionar.

2

$2$

Chandra Chekuri

Er, cada gráfico no dirigido puede orientarse para ser un DAG. Simplemente elija un orden de los vértices y use ese orden para orientar los bordes.

David Eppstein

Tienes razón, por supuesto, no estoy pensando con claridad.

Chandra Chekuri

En mi variación, cada subsecuencia tiene una longitud exactamente 4, por lo que la respuesta de Yury entra en juego. Mi única esperanza en este punto es que las subsecuencias tengan una estructura muy especial y estén relacionadas entre sí, por lo que tal vez algo específico para el problema ayudaría. Pero no hay un martillo general.

Suresh Venkat

Respuestas:

Si cada secuencia tiene una longitud 3, el problema se conoce como intermediación . Incluso el problema de intermediación es NP-duro. En este problema, se nos da un conjunto de vértices y un conjunto de restricciones de la forma encuentra entre y . Nuestro objetivo es ordenar todos los vértices para maximizar el número de restricciones satisfechas. Opantry [1] demostró que la versión de decisión de este problema es NP-hard. Chor y Sudán [2] demostraron que es SNP-hard. $u$ $v$ $w$

El algoritmo de aproximación más conocido para el problema, por Chor y Sudán, satisface la mitad de todas las restricciones si la instancia es completamente satisfactoria.

[1] J. Opantry. Problema de pedido total, SIAM Journal on Computing , 8 (1): 111-114, febrero de 1979.

[2] B. Chor y M. Sudán. Un enfoque geométrico para la intermediación , SIAM Journal on Discrete Mathematics, 11 (4): 511-523, noviembre de 1998.

Ediciones: aclaró que la versión de decisión del problema es NP-hard.

Yury
fuente

Yury, ¿eso significa que el problema de decisión de si se pueden satisfacer todas las restricciones también es difícil?

Chandra Chekuri

Sí, el problema de decisión es NP-duro. Además, para algunos es NP-difícil satisfacer incluso una fracción de de todas las restricciones (es decir, el problema de promesa correspondiente es NP-duro).

ϵ > 0

$\epsilon > 0$

1 - ϵ

$1-\epsilon$

Yury

Si la instancia no es completamente satisfactoria , el problema es muy difícil: por supuesto, puede satisfacer de todas las restricciones tomando un orden aleatorio; pero es difícil UGC satisfacer de todas las restricciones si para cada constante [Charikar, Guruswami, Manokaran - CCC 2009].

1 / 3

$1/3$

1 / 3 + ε

$1/3+ \varepsilon$

O P T = 1 - ε

$OPT = 1 -\varepsilon$

ε > 0

$\varepsilon > 0$

Yury

Mi pregunta puede ser estúpida. pero, ¿la dureza 3-regular ( para todo ) se extiende naturalmente a 4-regular?

| σ_{i} | = 3

$|\sigma_i| =3$

i

$i$

Yixin Cao

Sí, aquí hay una reducción. Considere una instancia de 3 regulares . Introduzca una nueva variable para cada secuencia . Sea una secuencia obtenida agregando al final de . Obtenemos una instancia de 4 regulares en vértices con secuencias . Es fácil ver que es satisfactoria si era satisfactoria: tome la solución para , coloque cada antes de todos los vértices en o después de todos los vértices en

I

${\cal I}$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

σ_{i}^{'}

$\sigma_i'$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

I^{'}

${\cal I}'$

V \cup {y_{i}}

$V \cup\{y_i\}$

{σ_{i}^{'}}

$\{\sigma_i'\}$

I^{'}

${\cal I}'$

I

${\cal I}$

I

${\cal I}$

y_{i}

$y_i$

V

$V$

V

$V$ dependiendo de la orientación de (el orden relativo de es irrelevante).

σ_{i}

$\sigma_i$

{y_{i}}

$\{y_i\}$

Yury