Parameterized Leaf Power Recognition via Embedding into Graph Products
Halls department, Hall 3
Thursday, 27 December 2018
11:30 - 12:30
The k-leaf power graph G of a tree T is a graph whose vertices are the leaves of T and whose edges connect pairs of leaves at unweighted distance at most k in T. Recognition of the k-leaf power graphs for k < 7 is still an open problem. In this talk, we provide an algorithm for this problem for sparse leaf power graphs. Our result shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by k and by the degeneracy of the given graph. To prove this, we describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of k and the degeneracy of G. As a result, we can use methods based on monadic second-order logic (MSO_2) to recognize the existence of a leaf power as a subgraph of the product graph.
Elham Havvaei is a PhD candidate at the Department of Computer Science in University of California, Irvine, advised by Professor David Eppstein. She received her Master degree in Computer Science from University of Central Florida in 2016. Her research interest includes the broad area of Theoretical Computer Science and more specifically Graph and Geometric Algorithms and Data Structures.