{
  "id": "math/0207020",
  "version": "v1",
  "published": "2002-07-02T17:15:11.000Z",
  "updated": "2002-07-02T17:15:11.000Z",
  "title": "Computing roots of directed graphs is graph isomorphism hard",
  "authors": [
    "Martin Kutz"
  ],
  "comment": "15 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The k-th power D^k of a directed graph D is defined to be the directed graph on the vertices of D with an arc from a to b in D^k iff one can get from a to b in D with exactly k steps. This notion is equivalent to the k-fold composition of binary relations or k-th powers of Boolean matrices. A k-th root of a directed graph D is another directed graph R with R^k = D. We show that for each k >= 2, computing a k-th root of a directed graph is at least as hard as the graph isomorphism problem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2002-07-02T17:15:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C20",
      "05C60",
      "68Q17",
      "05C50",
      "15A23",
      "06E99"
    ],
    "keywords": [
      "directed graph",
      "graph isomorphism hard",
      "computing roots",
      "k-th power",
      "k-th root"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2002math......7020K"
    }
  }
}