Minimum 0-Extension Problems on Directed Metrics
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913184822067200 |
|---|---|
| author | Hirai, Hiroshi Mizutani, Ryuhei |
| author_facet | Hirai, Hiroshi Mizutani, Ryuhei |
| contents | For a metric $μ$ on a finite set $T$, the minimum 0-extension problem 0-Ext$[μ]$ is defined as follows: Given $V\supseteq T$ and $\ c:{V \choose 2}\rightarrow \mathbf{Q_+}$, minimize $\sum c(xy)μ(γ(x),γ(y))$ subject to $γ:V\rightarrow T,\ γ(t)=t\ (\forall t\in T)$, where the sum is taken over all unordered pairs in $V$. This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. Karzanov and Hirai established a complete classification of metrics $μ$ for which 0-Ext$[μ]$ is polynomial time solvable or NP-hard. This result can also be viewed as a sharpening of the general dichotomy theorem for finite-valued CSPs (Thapper and Živný 2016) specialized to 0-Ext$[μ]$.
In this paper, we consider a directed version $\overrightarrow{0}$-Ext$[μ]$ of the minimum 0-extension problem, where $μ$ and $c$ are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext$[μ]$ to $\overrightarrow{0}$-Ext$[μ]$: If $μ$ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant ``directed'' edge-length, then $\overrightarrow{0}$-Ext$[μ]$ is NP-hard. We also show a partial converse: If $μ$ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then $\overrightarrow{0}$-Ext$[μ]$ is tractable. We further provide a new NP-hardness condition characteristic of $\overrightarrow{0}$-Ext$[μ]$, and establish a dichotomy for the case where $μ$ is a directed metric of a star. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_00153 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Minimum 0-Extension Problems on Directed Metrics Hirai, Hiroshi Mizutani, Ryuhei Discrete Mathematics Optimization and Control For a metric $μ$ on a finite set $T$, the minimum 0-extension problem 0-Ext$[μ]$ is defined as follows: Given $V\supseteq T$ and $\ c:{V \choose 2}\rightarrow \mathbf{Q_+}$, minimize $\sum c(xy)μ(γ(x),γ(y))$ subject to $γ:V\rightarrow T,\ γ(t)=t\ (\forall t\in T)$, where the sum is taken over all unordered pairs in $V$. This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. Karzanov and Hirai established a complete classification of metrics $μ$ for which 0-Ext$[μ]$ is polynomial time solvable or NP-hard. This result can also be viewed as a sharpening of the general dichotomy theorem for finite-valued CSPs (Thapper and Živný 2016) specialized to 0-Ext$[μ]$. In this paper, we consider a directed version $\overrightarrow{0}$-Ext$[μ]$ of the minimum 0-extension problem, where $μ$ and $c$ are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext$[μ]$ to $\overrightarrow{0}$-Ext$[μ]$: If $μ$ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant ``directed'' edge-length, then $\overrightarrow{0}$-Ext$[μ]$ is NP-hard. We also show a partial converse: If $μ$ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then $\overrightarrow{0}$-Ext$[μ]$ is tractable. We further provide a new NP-hardness condition characteristic of $\overrightarrow{0}$-Ext$[μ]$, and establish a dichotomy for the case where $μ$ is a directed metric of a star. |
| title | Minimum 0-Extension Problems on Directed Metrics |
| topic | Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2006.00153 |