{
  "id": "2106.08854",
  "version": "v1",
  "published": "2021-06-16T15:22:53.000Z",
  "updated": "2021-06-16T15:22:53.000Z",
  "title": "A polynomial Time Algorithm to Solve The Max-atom Problem",
  "authors": [
    "Chams Lahlou",
    "Laurent Truffet"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper we consider $m$ ($m \\geq 1$)conjunctions of Max-atoms that is atoms of the form $\\max(z,y) + r \\geq x$, where the offset $r$ is a real constant and $x,y,z$ are variables. We show that the Max-atom problem (MAP) belongs to $\\textsf{P}$. Indeed, we provide an algorithm which solves the MAP in $O(n^{6} m^{2} + n^{4} m^{3} + n^{2} m^{4})$ operations, where $n$ is the number of variables which compose the max-atoms. As a by-product other problems also known to be in $\\textsf{NP} \\cap \\textsf{co-NP}$ are in $\\textsf{P}$. P1: the problem to know if a tropical cone is trivial or not. P2: problem of tropical rank of a tropical matrix. P3: parity game problem. P4: scheduling problem with AND/OR precedence constraints. P5: problem on hypergraph (shortest path). P6: problem in model checking and $\\mu$-calculus.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-16T15:22:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q15",
      "68Q25"
    ],
    "keywords": [
      "polynomial time algorithm",
      "max-atom problem",
      "parity game problem",
      "shortest path",
      "precedence constraints"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}