  $k$-submodular functions, introduced by Huber and Kolmogorov, are functions
defined on $\{0, 1, 2, \dots, k\}^n$ satisfying certain submodular-type
inequalities. $k$-submodular functions typically arise as relaxations of
NP-hard problems, and the relaxations by $k$-submodular functions play key
roles in design of efficient, approximation, or fixed-parameter tractable
algorithms. Motivated by this, we consider the following problem: Given a
function $f : \{1, 2, \dots, k\}^n \rightarrow \mathbb{R} \cup \{\infty\}$,
determine whether $f$ is extended to a $k$-submodular function $g : \{0, 1, 2,
\dots, k\}^n \rightarrow \mathbb{R} \cup \{\infty\}$, where $g$ is called a
$k$-submodular relaxation of $f$.
  We give a polymorphic characterization of those functions which admit a
$k$-submodular relaxation, and also give a combinatorial $O((k^n)^2)$-time
algorithm to find a $k$-submodular relaxation or establish that a
$k$-submodular relaxation does not exist. Our algorithm has interesting
properties: (1) If the input function is integer valued, then our algorithm
outputs a half-integral relaxation, and (2) if the input function is binary,
then our algorithm outputs the unique optimal relaxation. We present
applications of our algorithm to valued constraint satisfaction problems.
