The quadratic M-convexity testing problem

M-convex functions, which are a generalization of valuated matroids, play a central role in discrete convex analysis. Quadratic M-convex functions constitute a basic and important subclass of M-convex functions, which has a close relationship with phylogenetics as well as valued constraint satisfaction problems. In this paper, we consider the quadraticM-convexity testing problem (QMCTP), which is the problem of deciding whether a given quadratic function on {0,1}n is M-convex. We show that QMCTP is co-NP-complete in general, but is polynomial-time solvable under a natural assumption. Furthermore, we propose an O(n2)-time algorithm for solving QMCTP in the polynomial-time solvable case.