|
Title:
|
Counting list h-colorings and variants
|
|
Author:
|
Díaz Cort, Josep; Serna Iglesias, María José; Thilikos Touloupas, Dimitrios
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
|
Abstract:
|
We study the counting versions of several variants of the H-coloring
problem. The complexity of the H-coloring problem is described by
a dichotomy theorem that classifies the problem according to the
the topology of H as #P-complete or polynomial time solvable.
We first prove that the same dichotomy criterion holds also for its
list extension, the list #H-coloring problem. We further
investigate these problems by examining a parameterization imposing
restrictions on the number of preimages of certain vertices in H.
We prove a nearly dichotomy theorem on the complexity of counting such
restricted homomorphisms, as well as a dichotomy theorem on the
complexity of its list version. Finally, we give a condition that
makes the parameterizedd problems solvable in linear time. |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica
-Counting list
-H-coloring
-Complexity
-Homomorphism
-Dichotomy theorem |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Report |
|
Share:
|
|
