Submodularity on a tree: Unifying $L^{♮}$-convex and bisubmodular functions

Abstract

We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions $f$ satisfying $f(x)+f(y)\ge f(x\sqcap y)+f(x\bigsqcup y)$ where the domain of each variable $x_i$ corresponds to nodes of a rooted binary tree, and operations $\sqcap ,\bigsqcup$ are defined with respect to this tree. Special cases include previously studied $L^{♮}$-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for $L^{♮}$-convex functions with bisubmodular minimization algorithms.

14 pages

References in corpus (5)

• The complexity of conservative finite-valued CSPs
• Min CSP on Four Elements: Moving Beyond Submodularity
• Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms
• A dichotomy theorem for conservative general-valued CSPs
• On the Complexity of Submodular Function Minimisation on Diamonds