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\).