Detecting and counting small patterns in planar graphs in subexponential parameterized time

We resolve the fine-grained parameterized complexity of detecting and counting small patterns in planar graphs, assuming the Exponential Time Hypothesis. Given an n -vertex planar graph G and a k -vertex pattern graph P , we compute the number of (induced) copies of P in G in time

Authors

• Jesper Nederlof

Keywords

• Subgraph Isomorphism
• Parameterized Complexity