David Eppstein - Publications

Publications with Elham Havvaei

• Parameterized leaf power recognition via embedding into graph products.
  D. Eppstein and E. Havvaei.
  arXiv:1810.02452.
  Proc. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2018.
  Leibniz International Proceedings in Informatics (LIPIcs) 115, 2018, pp. 16:1–16:14.
  Algorithmica 82 (8): 2337–2359, 2020 (special issue for IPEC 2018).

  A leaf power graph is the graph formed from the leaves of a tree by making two leaves adjacent when their tree distance is at most k. We show that recognizing these graphs is fixed-parameter tractable in a combination of two parameters: k and the degeneracy of the graph.

  (James Nastos has pointed out a minor error in our statement of known prior results: the figure depicting chordal graphs that are not 4-leaf powers is labeled as a complete set of forbidden subgraphs, but it is only the complete set among graphs without true twin vertices.)

• Simplifying activity-on-edge graphs.
  D. Eppstein, D. Frishberg, and E. Havvaei.
  arXiv:2002.01610.
  Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
  Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 24:1–24:14.

  Given a partially ordered set of activities, we find in polynomial time a directed acyclic graph and a mapping from activities to its edges, such that the sequences of activities along paths in the graph are exactly the totally ordered subsets of activities in the input.

• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes.
  D. Eppstein, E. Havvaei, and S. Gupta.
  arXiv:2101.09918.
  Proc. 23rd International Symposium on Fundamentals of Computation Theory, 2021.
  Springer, Lecture Notes in Comp. Sci. 12867 (2021), pp. 217–229.
  

  We provide a partial classification of the complexity of parameterized graph problems of the form "find a \(k\)-vertex induced subgraph with property \(X\) in a larger subgraph with property \(Y\)", in terms of the existence of large cliques and large independent sets in the graphs with properties \(X\) and \(Y\).