{
  "id": "1709.02475",
  "version": "v1",
  "published": "2017-09-07T22:30:01.000Z",
  "updated": "2017-09-07T22:30:01.000Z",
  "title": "Maximum independent sets near the upper bound",
  "authors": [
    "Ingo Schiermeyer"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The size of a largest independent set of vertices in a given graph $G$ is denoted by $\\alpha(G)$ and is called its independence number (or stability number). Given a graph $G$ and an integer $K,$ it is NP-complete to decide whether $\\alpha(G) \\geq K.$ An upper bound for the independence number $\\alpha(G)$ of a given graph $G$ with $n$ vertices and $m $ edges is given by $\\alpha(G) \\leq p:=\\lfloor\\frac{1}{2} + \\sqrt{\\frac{1}{4} + n^2 - n - 2m}\\rfloor.$ In this paper we will consider maximum independent sets near this upper bound. Our main result is the following: There exists an algorithm with time complexity $O(n^2)$ that, given as an input a graph $G$ with $n$ vertices, $m$ edges, $p:=\\lfloor\\frac{1}{2} + \\sqrt{\\frac{1}{4} + n^2 - n - 2m}\\rfloor,$ and an integer $k \\geq 0$ with $p \\geq 2k+1,$ returns an induced subgraph $G_{p,k}$ of $G$ with $n_0 \\leq p+2k+1$ vertices such that $\\alpha(G) \\leq p-k$ if and only if $\\alpha(G_{p,k}) \\leq p-k.$ Furthermore, we will show that we can decide in time $O(1.2738^{3k} + kn)$ whether $\\alpha(G_{p,k}) \\leq p-k.$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-07T22:30:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C85"
    ],
    "keywords": [
      "maximum independent sets",
      "upper bound",
      "independence number",
      "largest independent set",
      "stability number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}