Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs - Computer Science > Discrete Mathematics

Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs - Computer Science > Discrete Mathematics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: For digraphs $G$ and $H$, a homomorphism of $G$ to $H$ is a mapping $f:\VG\dom VH$ such that $uv\in AG$ implies $fufv\in AH$. If, moreover,each vertex $u \in VG$ is associated with costs $c iu, i \in VH$, thenthe cost of a homomorphism $f$ is $\sum {u\in VG}c {fu}u$. For each fixeddigraph $H$, the minimum cost homomorphism problem for $H$, denotedMinHOM$H$, can be formulated as follows: Given an input digraph $G$, togetherwith costs $c iu$, $u\in VG$, $i\in VH$, decide whether there exists ahomomorphism of $G$ to $H$ and, if one exists, to find one of minimum cost.Minimum cost homomorphism problems encompass or are related to many wellstudied optimization problems such as the minimum cost chromatic partition andrepair analysis problems. We focus on the minimum cost homomorphism problem forlocally semicomplete digraphs and quasi-transitive digraphs which are twowell-known generalizations of tournaments. Using graph-theoreticcharacterization results for the two digraph classes, we obtain a fulldichotomy classification of the complexity of minimum cost homomorphismproblems for both classes.

Autor: A. Gupta, G. Gutin, M. Karimi, E.J. Kim, A. Rafiey

Fuente: https://arxiv.org/