We consider directed graphs in which nodes are labeled and
may have self-loops.
Let 
be such a directed graph.
An edge of may be colored or left blank
(i.e., uncolored). A spot
in a colored digraph is a 3-node subgraph with induced
colored edges (including self-loops if there are any)
and the nodes unlabeled. We only use a constant
number of colors.
So it is easy to see that there are only constant number of different
spots.
The coloration 
of consists of the set of all spots induced
from the colored graph ,
and the number of blank edges. We will also specify a set 
of constraints
that specify what edges may be colored blank. For instance,
one may specify that ``only
edges on a Hamiltonian path may be colored blank."
DISTRIBUTIONAL GRAPH EDGE COLORING PROBLEM
Instance. A directed graph of 
nodes, a set 
of spots, a positive integer 
specifying the number of blank edges,
and a set of constraints specifying what edges may be colored blank.
The size of the instance is plus the size of plus the size of
plus the size of , where is encoded as a binary string.
Question. Can be colored, under the constraints in ,
such that 
and
?
(If so, we then say that is colorable.)
Distribution. First choose a positive integer with respect
to the default uniform distribution. Then randomly and
independently choose a directed graph of
nodes with uniform probability 
,
a set of spots with probability 
, the number of
blank edges with probability 
, and
the constraints with probability 
.
Hence, the probability distribution is proportional to
.
The distributional graph edge coloring problem was shown to
be average-case NP-complete by Venkatesan and Levin [VL88]
(see also [Ven91])
using a randomized reduction.
