David Eppstein - Publications

Publications with Bálint Tillman

• The computational hardness of dK-series.
  W. E. Devanny, D. Eppstein, and B. Tillman.
  NetSci2016 poster session, Seoul, Korea.

  The dK-series is an extension of the degree sequence of a graph to a d-dimensional tensor, describing the number of d-tuples of vertices with each possible combination of degrees and adjacencies. As we show, it is NP-hard to determine whether such a tensor represents a valid graph, for any d ≥ 3, or for d = 2 if the number of triangles in the graph is also specified (or constrained to be zero).