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.

13 pages

References in corpus (2)

• Hybrid tractability of soft constraint problems
• Discrete Convexity in Joint Winner Property

Cited by in corpus (2)

• Point-width and Max-CSPs
• A tractable class of binary VCSPs via M-convex intersection