Title: The quadratic M-convexity testing problem,
Abstract: 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 quadratic M-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(n^2)$-time algorithm for solving QMCTP in the polynomial-time solvable
case.