David Eppstein - Publications

Exponential-time algorithmics

• 3-Coloring in time O(1.3446ⁿ): a no-MIS algorithm.
  R. Beigel and D. Eppstein.
  Tech. Rep. 95-033, Electronic Coll. Computational Complexity, 1995.
  36th IEEE Symp. Foundations of Comp. Sci., 1995, pp. 444–453.
  DIMACS Worksh. Faster Exact Solutions for NP-Hard Problems, 2000.

  Speeds up 3-coloring by solving a harder problem: constraint satisfaction in which each variable can take on one of three values and each constraint forbids a pair of variable assignments. The detailed solution involves several long hairy case analyses. Similar methods apply also to 3-list-coloring, 3-edge-coloring, and 3-SAT. The 3-SAT algorithm is fixed-parameter tractible in that it is polynomial time when the number of 3-variable clauses is O(log n). Merged into 3-coloring in time O(1.3289^n) for the journal version.

  (DIMACS abstract and slides)

• 3-coloring in time O(1.3289^n).
  R. Beigel and D. Eppstein.
  arXiv:cs.DS/0006046.
  J. Algorithms 54:2 (2005) 168-204.

  Journal paper combining 3-coloring algorithms from our FOCS '95 paper with improved bounds from our SODA '01 paper.

• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
  D. Eppstein.
  arXiv:cs.DS/0009006.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 329–337.

  Summarizes recent improvements to "3-Coloring in time O(1.3446ⁿ): a no-MIS algorithm". Merged with that paper for the journal version.

  (SODA talk slides – SODA paper)

• Small maximal independent sets and faster exact graph coloring.
  D. Eppstein.
  arXiv:cs.DS/0011009.
  7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
  Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 462–470.
  J. Graph Algorithms and Applications (special issue for WADS'01) 7 (2): 131–140, 2003.

  We show that any graph can be colored in time O(2.415ⁿ), by a dynamic programming procedure in which we extend partial colorings on subsets of the vertices by adding one more color for a maximal independent set. The time bound follows from limiting our attention to maximal independent subsets that are small relative to the previously colored subset, and from bounding the number of small maximal independent subsets that can occur in any graph.

  (WADS talk slides)

• The traveling salesman problem for cubic graphs.
  D. Eppstein.
  arXiv:cs.DS/0302030.
  8th Worksh. Algorithms and Data Structures, Ottawa, 2003.
  Springer, Lecture Notes in Comp. Sci. 2748, 2003, pp. 307–318.
  J. Graph Algorithms and Applications 11 (1): 61–81, 2007.

  We find improved exponential-time algorithms for exact solution of the traveling salesman problem on graphs of maximum degree three and four. We also consider related problems including counting the number of Hamiltonian cycles in such graphs.

  (WADS talk slides)

• Quasiconvex analysis of backtracking algorithms.
  D. Eppstein.
  arXiv:cs.DS/0304018.
  15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 781–790.
  ACM Trans. Algorithms 2 (4): 492–509 (special issue for SODA 2004), 2006.

  We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.

  The journal version uses the longer title "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms".

  (SODA talk slides)

• Quasiconvex programming.
  D. Eppstein.
  Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick, NJ, 2003.
  Plenary talk at ALGO 2004, Bergen, Norway, 2004.
  arXiv:cs.CG/0412046.
  Combinatorial and Computational Geometry, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2005, pp. 287–331.

  Defines quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. Surveys algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.

  (DIMACS talk slides – ALGO talk slides)

• All maximal independent sets and dynamic dominance for sparse graphs.
  D. Eppstein.
  arXiv:cs.DS/0407036.
  16th ACM-SIAM Symp. Discrete Algorithms, Vancouver, 2005, pp. 451–459.
  ACM Trans. Algorithms 5(4):A38, 2009.

  We show how to apply reverse search to list all maximal independent sets in bounded-degree graphs in constant time per set, in graphs from minor closed families in linear time per set, and in sparse graphs in subquadratic time per set. The latter two results rely on new data structures for maintaining a dynamic vertex set in a graph and quickly testing whether the set dominates all other vertices.

  (SODA05 talk slides)

• Listing all maximal cliques in sparse graphs in near-optimal time.
  D. Eppstein, M. Löffler, and D. Strash.
  arXiv:1006.5440.
  Workshop on Exact Algorithms for NP-Hard Problems, Dagstuhl, Germany, 2010.
  Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, pp. 403–414.
  

  We describe an algorithm for finding all maximal cliques in a graph, in time O(dn3^d/3) where n is the number of vertices and d is the degeneracy of the graph, a standard measure of its sparsity. This time bound matches the worst-case output size for these parameters. The algorithm modifies the Bron-Kerbosch algorithm for maximal cliques by ordering the vertices by degree in the outer recursive call of the algorithm.

  For the journal version, see "Listing all maximal cliques in large sparse real-world graphs," which combines results from this and a different conference paper.

• Listing all maximal cliques in large sparse real-world graphs.
  D. Eppstein and D. Strash.
  10th Int. Symp. Experimental Algorithms, Crete, 2011.
  Springer, Lecture Notes in Comp. Sci. 6630, 2011, pp. 364–375.
  arXiv:1103.0318.

  We experiment with our degeneracy-based algorithm for listing maximal cliques in sparse graphs and show that it works well on large graphs drawn from several repositories of real-world social networks and bioinformatics networks.

  For the journal version, see "Listing all maximal cliques in large sparse real-world graphs", which combines results from this and a different conference paper.

• Solving single-digit Sudoku subproblems.
  D. Eppstein.
  arXiv:1202.5074.
  6th International Conference on Fun with Algorithms (FUN 2012), Venice, Italy, 2012.
  Springer, Lecture Notes in Comp. Sci. 7288, 2012, pp. 142–153.

  We find an algorithm for making all possible deductions based on the set of candidate locations for a single digit in a Sudoku puzzle; the problem is NP-hard, and our algorithm takes exponential time, but the mild form of the exponential allows it to be fast for practical problem sizes.

  (Slides)

• Listing all maximal cliques in large sparse real-world graphs.
  D. Eppstein, M. Löffler, and D. Strash.
  J. Experimental Algorithmics 18 (3): 3.1, 2013 (special issue for SEA).

  This paper combines our theoretical results on clique-finding algorithms from ISAAC 2010 with our experimental results on the same algorithms from SEA 2011. We show how to list all maximal cliques in graphs of bounded degeneracy in time that is linear in the size of the graph and near-optimal in the degeneracy, and we show that low degeneracy explains the good behavior of the algorithm in our experiments on large real-world social networks.

• Non-crossing Hamiltonian paths and cycles in output-polynomial time.
  D. Eppstein.
  arXiv:2303.00147.
  Proc. 39th International Symposium on Computational Geometry (SoCG 2023).
  Leibniz International Proceedings in Informatics (LIPIcs) 258, 2023, pp. 29:1–29:16.
  Algorithmica 86: 3027–3053, 2024.

  For any point set, the numbers of non-crossing paths, non-crossing Hamiltonian paths, non-crossing surrounding polygons, and non-crossing Hamiltonian cycles can be bounded above and below by functions of two simple parameters: the minimum number of points whose deletion leaves a collinear subset, and the number of points interior to the convex hull. Because their bounds have the same form, the numbers of the two types of paths are bounded by polynomials of each other, as are the numbers of the two types of polygons. We use these relations to list non-crossing Hamiltonian paths and polygonalizations in time polynomial in the number of outputs.

  (Talk slides)