  This work presents a maximum entropy principle based algorithm for solving
minimum multiway $k$-cut problem defined over static and dynamic {\em
digraphs}. A multiway $k$-cut problem requires partitioning the set of nodes in
a graph into $k$ subsets, such that each subset contains one prespecified node,
and the corresponding total cut weight is minimized. These problems arise in
many applications and are computationally complex (NP-hard). In the static
setting this article presents an approach that uses a relaxed multiway $k$-cut
cost function; we show that the resulting algorithm converges to a local
minimum. This iterative algorithm is designed to avoid poor local minima with
its run-time complexity as $\sim O(kIN^3)$, where $N$ is the number of vertices
and $I$ is the number of iterations. In the dynamic setting, the edge-weight
matrix has an associated dynamics with some of the edges in the graph capable
of being influenced by an external input. The objective is to design the
dynamics of the controllable edges so that multiway $k$-cut value remains small
(or decreases) as the graph evolves under the dynamics. Also it is required to
determine the time-varying partition that defines the minimum multiway $k$-cut
value. Our approach is to choose a relaxation of multiway $k$-cut value,
derived using maximum entropy principle, and treat it as a control Lyapunov
function to design control laws that affect the weight dynamics. Simulations on
practical examples of interactive foreground-background segmentation, minimum
multiway $k$-cut optimization for non-planar graphs and dynamically evolving
graphs that demonstrate the efficacy of the algorithm, are presented.
