13th International Symposium on Parameterized and
Exact Computation. IPEC 2018, August 22-24, 2018,
Helsinki, Finland

Christophe Paul, Michal Pilipczuk

► To cite this version:

Christophe Paul, Michal Pilipczuk. 13th International Symposium on Parameterized and Exact Computation. IPEC 2018, August 22-24, 2018, Helsinki, Finland. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Leibniz International Proceedings in Informatics, 115, Schloss Dagstuhl-Libniz-Zentrum fuer Informatik, 2019, 978-3-95977-084-2. 10.4230/LIPIcs.IPEC.2018.0 . hal-02019803

HAL Id: hal-02019803

https://hal.science/hal-02019803

Submitted on 12 Apr 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
13th International Symposium on Parameterized and
Exact Computation. IPEC 2018, August 22-24, 2018,
Helsinki, Finland

Christophe Paul, Michal Pilipczuk

► To cite this version:

Christophe Paul, Michal Pilipczuk. 13th International Symposium on Parameterized and Exact Computation. IPEC 2018, August 22-24, 2018, Helsinki, Finland. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Leibniz International Proceedings in Informatics, 115, Schloss Dagstuhl-Libniz-Zentrum fuer Informatik, 2019, 978-3-95977-084-2. 10.4230/LIPIcs.IPEC.2018.0 . hal-02019803

HAL Id: hal-02019803

https://hal.science/hal-02019803v1

Submitted on 12 Apr 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
13th International Symposium
on Parameterized and Exact
Computation

IPEC 2018, August 22-24, 2018, Helsinki, Finland

Edited by

Christophe Paul

Michał Pilipczuk

<figure><img src="image_2.png" /></figure>

LIPICS

LIPICS - Vol. 115 - IPEC 2018

www.dagstuhl.de/lipics
13th International Symposium
on Parameterized and Exact
Computation

IPEC 2018, August 22-24, 2018, Helsinki, Finland

Edited by

Christophe Paul

Michał Pilipczuk

<figure><img src="image_2.png" /></figure>

LIPICS

LIPICS - Vol. 115 - IPEC 2018

www.dagstuhl.de/lipics
Editors

Christophe Paul

LIRMM

CNRS, Université de Montpellier

France

christophe.paul@lirmm.fr

Michał Pilipczuk

Institute of Informatics

Faculty of Mathematics, Informatics, and Mechanics

of the University of Warsaw, Poland

michal.pilipczuk@mimuw.edu.pl

ACM Classification 2012

Theory of computation → Complexity classes, Theory of computation → Design and analysis of algorithms,

Mathematics of computing → Discrete mathematics

ISBN 978-3-95977-084-2

Published online and open access by

Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany. Online available at http://www.dagstuhl.de/dagpub/978-3-95977-084-2.

Publication date

January, 2019

Bibliographic information published by the Deutsche Nationalbibliothek

The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available in the Internet at http://dnb.d-nb.de.

License

This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC-BY 3.0):
http://creativecommons.org/licenses/by/3.0/legalcode.

In brief, this license authorizes each and everybody to share (to copy, distribute and transmit) the work under the following conditions, without impairing or restricting the authors' moral rights:

Attribution: The work must be attributed to its authors.

The copyright is retained by the corresponding authors.

<figure><img src="image_3.png" /></figure>

Digital Object Identifier: 10.4230/LIPIcs.IPEC.2018.0

ISBN 978-3-95977-084-2

ISSN 1868-8969

http://www.dagstuhl.de/lipics
Editors

Christophe Paul

LIRMM

CNRS, Université de Montpellier

France

christophe.paul@lirmm.fr

Michał Pilipczuk

Institute of Informatics

Faculty of Mathematics, Informatics, and Mechanics

of the University of Warsaw, Poland

michal.pilipczuk@mimuw.edu.pl

ACM Classification 2012

Theory of computation → Complexity classes, Theory of computation → Design and analysis of algorithms,

Mathematics of computing → Discrete mathematics

ISBN 978-3-95977-084-2

Published online and open access by

Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany. Online available at http://www.dagstuhl.de/dagpub/978-3-95977-084-2.

Publication date

January, 2019

Bibliographic information published by the Deutsche Nationalbibliothek

The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available in the Internet at http://dnb.d-nb.de.

License

This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC-BY 3.0):
http://creativecommons.org/licenses/by/3.0/legalcode.

In brief, this license authorizes each and everybody to share (to copy, distribute and transmit) the work under the following conditions, without impairing or restricting the authors' moral rights:

Attribution: The work must be attributed to its authors.

The copyright is retained by the corresponding authors.

<figure><img src="image_3.png" /></figure>

Digital Object Identifier: 10.4230/LIPIcs.IPEC.2018.0

ISBN 978-3-95977-084-2

ISSN 1868-8969

http://www.dagstuhl.de/lipics
LIPIcs – Leibniz International Proceedings in Informatics

LIPIcs is a series of high-quality conference proceedings across all fields in informatics. LIPIcs volumes are published according to the principle of Open Access, i.e., they are available online and free of charge.

Editorial Board

- Luca Aceto (Chair, Gran Sasso Science Institute and Reykjavik University)

- Susanne Albers (TU München)

- Christel Baier (TU Dresden)

- Javier Esparza (TU München)

- Michael Mitzenmacher (Harvard University)

- Madhavan Mukund (Chennai Mathematical Institute)

- Anca Muscholl (University Bordeaux)

- Catuscia Palamidessi (INRIA)

- Raimund Seidel (Saarland University and Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

- Thomas Schwentick (TU Dortmund)

- Reinhard Wilhelm (Saarland University)

ISSN 1868-8969

http://www.dagstuhl.de/lipics
LIPIcs – Leibniz International Proceedings in Informatics

LIPIcs is a series of high-quality conference proceedings across all fields in informatics. LIPIcs volumes are published according to the principle of Open Access, i.e., they are available online and free of charge.

Editorial Board

■ Luca Aceto (Chair, Gran Sasso Science Institute and Reykjavik University)

■ Susanne Albers (TU München)

■ Christel Baier (TU Dresden)

■ Javier Esparza (TU München)

■ Michael Mitzenmacher (Harvard University)

■ Madhavan Mukund (Chennai Mathematical Institute)

■ Anca Muscholl (University Bordeaux)

■ Catuscia Palamidessi (INRIA)

■ Raimund Seidel (Saarland University and Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

■ Thomas Schwentick (TU Dortmund)

■ Reinhard Wilhelm (Saarland University)

ISSN 1868-8969

http://www.dagstuhl.de/lipics
<figure><img src="image_4.png" /></figure>
<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /></figure>

# Contents

Preface
Christophe Paul and Michał Pilipczuk 0:vii

Counting Problems in Parameterized Complexity
Radu Curticapean 1:1–1:18

A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth
Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos 2:1–2:13

Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel 3:1–3:14

Multivariate Analysis of Orthogonal Range Searching and Graph Distances
Karl Bringmann, Thore Husfeldt, and Måns Magnusson 4:1–4:13

A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
Kustaa Kangas, Mikko Koivisto, and Sami Salonen 5:1–5:13

Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width
Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle 6:1–6:14

A Parameterized Complexity View on Collapsing k-Cores
Junjie Luo, Hendrik Molter, and Ondřej Suchý 7:1–7:14

Parameterized Complexity of Multi-Node Hubs
Saket Saurabh and Meirav Zehavi 8:1–8:14

The Parameterised Complexity of Computing the Maximum Modularity of a Graph
Kitty Meeks and Fiona Skerman 9:1–9:14

On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut 10:1–10:14

The Parameterized Complexity of Finding Point Sets with Hereditary Properties
David Eppstein and Daniel Lokshtanov 11:1–11:14

Dual Parameterization of Weighted Coloring
Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva 12:1–12:14

Computing Kernels in Parallel: Lower and Upper Bounds
Max Bannach and Till Tantau 13:1–13:14

Exploring the Kernelization Borders for Hitting Cycles
Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra, and Saket Saurabh 14:1–14:14

<figure><img src="image_6.png" /></figure>
<figure><img src="image_5.png" /></figure>

# Contents

<table><tr><td>Preface<br>Christophe Paul and Michał Pilipczuk</td><td>0:vii</td></tr><tr><td>Counting Problems in Parameterized Complexity<br>Radu Curticapean</td><td>1:1–1:18</td></tr><tr><td>A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth<br>Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos</td><td>2:1–2:13</td></tr><tr><td>Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth<br>Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel</td><td>3:1–3:14</td></tr><tr><td>Multivariate Analysis of Orthogonal Range Searching and Graph Distances<br>Karl Bringmann, Thore Husfeldt, and Måns Magnusson</td><td>4:1–4:13</td></tr><tr><td>A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions<br>Kustaa Kangas, Mikko Koivisto, and Sami Salonen</td><td>5:1–5:13</td></tr><tr><td>Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width<br>Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle</td><td>6:1–6:14</td></tr><tr><td>A Parameterized Complexity View on Collapsing k-Cores<br>Junjie Luo, Hendrik Molter, and Ondřej Suchý</td><td>7:1–7:14</td></tr><tr><td>Parameterized Complexity of Multi-Node Hubs<br>Saket Saurabh and Meirav Zehavi</td><td>8:1–8:14</td></tr><tr><td>The Parameterised Complexity of Computing the Maximum Modularity of a Graph<br>Kitty Meeks and Fiona Skerman</td><td>9:1–9:14</td></tr><tr><td>On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs<br>Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut</td><td>10:1–10:14</td></tr><tr><td>The Parameterized Complexity of Finding Point Sets with Hereditary Properties<br>David Eppstein and Daniel Lokshtanov</td><td>11:1–11:14</td></tr><tr><td>Dual Parameterization of Weighted Coloring<br>Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva</td><td>12:1–12:14</td></tr><tr><td>Computing Kernels in Parallel: Lower and Upper Bounds<br>Max Bannach and Till Tantau</td><td>13:1–13:14</td></tr><tr><td>Exploring the Kernelization Borders for Hitting Cycles<br>Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra, and Saket Saurabh</td><td>14:1–14:14</td></tr></table>

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michał Pilipczuk

<figure><img src="image_6.png" /></figure>

Leibniz International Proceedings in Informatics

LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
<table>
  <tbody>
    <tr>
      <td>Best-Case and Worst-Case Sparsifiability of Boolean CSPs<br><i>Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse</i></td>
      <td>15:1–15:13</td>
    </tr>
    <tr>
      <td>Parameterized Leaf Power Recognition via Embedding into Graph Products<br><i>David Eppstein and Elham Havvaei</i></td>
      <td>16:1–16:14</td>
    </tr>
    <tr>
      <td>Parameterized Complexity of Independent Set in H-Free Graphs<br><i>Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant</i></td>
      <td>17:1–17:13</td>
    </tr>
    <tr>
      <td>Multi-Budgeted Directed Cuts<br><i>Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, and Magnus Wahlström</i></td>
      <td>18:1–18:14</td>
    </tr>
    <tr>
      <td>Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms<br><i>Christian Komusiewicz, Dieter Kratsch, and Van Bang Le</i></td>
      <td>19:1–19:13</td>
    </tr>
    <tr>
      <td>Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size<br><i>Charis Papadopoulos and Spyridon Tzimas</i></td>
      <td>20:1–20:14</td>
    </tr>
    <tr>
      <td>Integer Programming in Parameterized Complexity: Three Miniatures<br><i>Tomáš Gavenčiak, Dušan Knop, and Martin Koutecký</i></td>
      <td>21:1–21:16</td>
    </tr>
    <tr>
      <td>Solving Target Set Selection with Bounded Thresholds Faster than 2<sup>n</sup><br><i>Ivan Bliznets and Danil Sagunov</i></td>
      <td>22:1–22:14</td>
    </tr>
    <tr>
      <td>Resolving Conflicts for Lower-Bounded Clustering<br><i>Katrin Casel</i></td>
      <td>23:1–23:14</td>
    </tr>
    <tr>
      <td>Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness<br><i>Marc Roth and Johannes Schmitt</i></td>
      <td>24:1–24:14</td>
    </tr>
    <tr>
      <td>A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem<br><i>Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Saket Saurabh</i></td>
      <td>25:1–25:13</td>
    </tr>
    <tr>
      <td>The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration<br><i>Édouard Bonnet and Florian Sikora</i></td>
      <td>26:1–26:15</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>Best-Case and Worst-Case Sparsifiability of Boolean CSPs<br><i>Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse</i></td>
      <td>15:1–15:13</td>
    </tr>
    <tr>
      <td>Parameterized Leaf Power Recognition via Embedding into Graph Products<br><i>David Eppstein and Elham Havvaei</i></td>
      <td>16:1–16:14</td>
    </tr>
    <tr>
      <td>Parameterized Complexity of Independent Set in H-Free Graphs<br><i>Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant</i></td>
      <td>17:1–17:13</td>
    </tr>
    <tr>
      <td>Multi-Budgeted Directed Cuts<br><i>Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, and Magnus Wahlström</i></td>
      <td>18:1–18:14</td>
    </tr>
    <tr>
      <td>Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms<br><i>Christian Komusiewicz, Dieter Kratsch, and Van Bang Le</i></td>
      <td>19:1–19:13</td>
    </tr>
    <tr>
      <td>Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size<br><i>Charis Papadopoulos and Spyridon Tzimas</i></td>
      <td>20:1–20:14</td>
    </tr>
    <tr>
      <td>Integer Programming in Parameterized Complexity: Three Miniatures<br><i>Tomáš Gavenčiak, Dušan Knop, and Martin Koutecký</i></td>
      <td>21:1–21:16</td>
    </tr>
    <tr>
      <td>Solving Target Set Selection with Bounded Thresholds Faster than 2<sup>n</sup><br><i>Ivan Bliznets and Danil Sagunov</i></td>
      <td>22:1–22:14</td>
    </tr>
    <tr>
      <td>Resolving Conflicts for Lower-Bounded Clustering<br><i>Katrin Casel</i></td>
      <td>23:1–23:14</td>
    </tr>
    <tr>
      <td>Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness<br><i>Marc Roth and Johannes Schmitt</i></td>
      <td>24:1–24:14</td>
    </tr>
    <tr>
      <td>A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem<br><i>Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Saket Saurabh</i></td>
      <td>25:1–25:13</td>
    </tr>
    <tr>
      <td>The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration<br><i>Édouard Bonnet and Florian Sikora</i></td>
      <td>26:1–26:15</td>
    </tr>
  </tbody>
</table>
<figure><img src="image_7.png" /></figure>

# Preface

This volume contains the papers presented at IPEC 2018: the 13th International Symposium on Parameterized and Exact Computation, which took place on August 22-24 in Helsinki, Finland. IPEC was collocated with five other algorithms conferences as a part of the annual ALGO congress.

The International Symposium on Parameterized and Exact Computation (IPEC, formerly IWPEC) is a series of international symposia covering research in all aspects of parameterized and exact algorithms and complexity. Started in 2004 as a biennial workshop, it became an annual event in 2009.

In response to the call for papers, 48 papers were submitted. Each submission was reviewed by at least 3 reviewers. The reviews came from the 15 members of the program committee, and from 50 external reviewers contributing 145 external reviews. The program committee held electronic meetings through the EasyChair platform. The program committee felt that the median submission quality was very high, and in the end selected 24 of the submissions for presentation at the symposium and for inclusion in this proceedings volume. This year, both the

Best Paper Award and the Excellent Student Paper Award distinguish the paper *Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness* co-authored by Marc Roth and Johannes Schmitt.

IPEC invited one plenary speaker to the ALGO meeting, Magnus Wahlström, as part of the award ceremony for the 2017 EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics. The award was given by a committee consisting of Dániel Marx, Jianer Chen and Hans L. Bodlaender to Stefan Kratsch and Magnus Wahlström for their paper *Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal (ACM Transactions on Algorithms 10(4): 20:1-20:15 (2014))*. IPEC also invited Radu Curtipean to present a tutorial on *Counting Problems in Parameterized Complexity*. Finally, IPEC hosted the ceremony of the 2018 PACE awards. The Parameterized Algorithms and Computational Experiments Challenge (PACE) was conceived in Fall 2015 to deepen the relationship between parameterized algorithms and practice. This volume contains a report by Édouard Bonnet and Florian Sikora on the 2018 PACE challenge.

We would like to thank the program committee, together with the external reviewers, for their commitment in the difficult paper selection process. We also thank all the authors who submitted their work for consideration. Finally, we are grateful to the local organizers of ALGO, chaired by Parinya Chalermsook, Petteri Kaski and Jukka Suomela, for their efforts, which made chairing IPEC an enjoyable experience.

Christophe Paul and Michał Pilipczuk
Montpellier and Warsaw, November 2018

<table><thead><tr><th></th><th>Previous IPEC</th></tr></thead><tbody><tr><td>2004</td><td>Bergen, Norway</td></tr><tr><td>2006</td><td>Zürich, Switzerland</td></tr><tr><td>2008</td><td>Victoria, Canada</td></tr><tr><td>2009</td><td>Copenhagen, Denmark</td></tr><tr><td>2010</td><td>Chennai, India</td></tr><tr><td>2011</td><td>Saarbrücken, Germany</td></tr><tr><td>2012</td><td>Ljubljana, Slovenia</td></tr><tr><td>2013</td><td>Sophia Antipolis, France</td></tr><tr><td>2014</td><td>Wroclaw, Poland</td></tr><tr><td>2015</td><td>Patras, Greece</td></tr><tr><td>2016</td><td>Aarhus, Denmark</td></tr><tr><td>2017</td><td>Vienna, Austria</td></tr></tbody></table>

<figure><img src="image_8.png" /></figure>
<figure><img src="image_7.png" /></figure>

# Preface

This volume contains the papers presented at IPEC 2018: the 13th International Symposium on Parameterized and Exact Computation, which took place on August 22-24 in Helsinki, Finland. IPEC was collocated with five other algorithms conferences as a part of the annual ALGO congress.

The International Symposium on Parameterized and Exact Computation (IPEC, formerly IWPEC) is a series of international symposia covering research in all aspects of parameterized and exact algorithms and complexity. Started in 2004 as a biennial workshop, it became an annual event in 2009.

In response to the call for papers, 48 papers were submitted. Each submission was reviewed by at least 3 reviewers. The reviews came from the 15 members of the program committee, and from 50 external reviewers contributing 145 external reviews. The program committee held electronic meetings through the EasyChair platform. The program committee felt that the median submission quality was very high, and in the end selected 24 of the submissions for presentation at the symposium and for inclusion in this proceedings volume. This year, both the

Best Paper Award and the Excellent Student Paper Award distinguish the paper *Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness* co-authored by Marc Roth and Johannes Schmitt.

IPEC invited one plenary speaker to the ALGO meeting, Magnus Wahlström, as part of the award ceremony for the 2017 EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics. The award was given by a committee consisting of Dániel Marx, Jianer Chen and Hans L. Bodlaender to Stefan Kratsch and Magnus Wahlström for their paper *Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal* (ACM Transactions on Algorithms 10(4): 20:1-20:15 (2014)). IPEC also invited Radu Curtipean to present a tutorial on *Counting Problems in Parameterized Complexity*. Finally, IPEC hosted the ceremony of the 2018 PACE awards. The Parameterized Algorithms and Computational Experiments Challenge (PACE) was conceived in Fall 2015 to deepen the relationship between parameterized algorithms and practice. This volume contains a report by Édouard Bonnet and Florian Sikora on the 2018 PACE challenge.

We would like to thank the program committee, together with the external reviewers, for their commitment in the difficult paper selection process. We also thank all the authors who submitted their work for consideration. Finally, we are grateful to the local organizers of ALGO, chaired by Parinya Chalermsook, Petteri Kaski and Jukka Suomela, for their efforts, which made chairing IPEC an enjoyable experience.

Christophe Paul and Michał Pilipczuk
Montpellier and Warsaw, November 2018

<table><thead><tr><th></th><th>Previous IPEC</th></tr></thead><tbody><tr><td>2004</td><td>Bergen, Norway</td></tr><tr><td>2006</td><td>Zürich, Switzerland</td></tr><tr><td>2008</td><td>Victoria, Canada</td></tr><tr><td>2009</td><td>Copenhagen, Denmark</td></tr><tr><td>2010</td><td>Chennai, India</td></tr><tr><td>2011</td><td>Saarbrücken, Germany</td></tr><tr><td>2012</td><td>Ljubljana, Slovenia</td></tr><tr><td>2013</td><td>Sophia Antipolis, France</td></tr><tr><td>2014</td><td>Wrocław, Poland</td></tr><tr><td>2015</td><td>Patras, Greece</td></tr><tr><td>2016</td><td>Aarhus, Denmark</td></tr><tr><td>2017</td><td>Vienna, Austria</td></tr></tbody></table>

<figure><img src="image_8.png" /></figure>
<figure><img src="image_9.png" /></figure>
<figure><img src="image_9.png" /></figure>
<figure><img src="image_10.png" /></figure>

Programme Committee

David Coudert

Serge Gaspers

Fedor Fomin

Christian Knauer

Stephan Kreutzer

Michael Lampis

Sebastian Ordyniak

Sang-il Oum

Christophe Paul (co-chair)

Daniël Paulusma

Geevarghese Philip

Michał Pilipczuk (co-chair)

Hisao Tamaki

Till Tantau

Meirav Zehavi

Université Côte d'Azur, Inria, CNRS, I3S

UNSW Sydney and Data61, CSIRO

University of Bergen

Universität Bayreuth

TU Berlin

Lamsade, Université Paris Dauphine

TU Wien

KAIST

LIRMM, CNRS, Université de Montpellier

Durham University

Chennai Mathematical Institute

University of Warsaw

Meiji University

Universität zu Lübeck

Ben-Gurion University

France

Australia

Norway

Germany

Germany

France

Austria

South Korea

France

United Kingdom

India

Poland

Japan

Germany

Israel
<figure><img src="image_10.png" /></figure>

Programme Committee

David Coudert

Serge Gaspers

Fedor Fomin

Christian Knauer

Stephan Kreutzer

Michael Lampis

Sebastian Ordyniak

Sang-il Oum

Christophe Paul (co-chair)

Daniël Paulusma

Geevarghese Philip

Michał Pilipczuk (co-chair)

Hisao Tamaki

Till Tantau

Meirav Zehavi

Université Côte d'Azur, Inria, CNRS, I3S

UNSW Sydney and Data61, CSIRO

University of Bergen

Universität Bayreuth

TU Berlin

Lamsade, Université Paris Dauphine

TU Wien

KAIST

LIRMM, CNRS, Université de Montpellier

Durham University

Chennai Mathematical Institute

University of Warsaw

Meiji University

Universität zu Lübeck

Ben-Gurion University

France

Australia

Norway

Germany

Germany

France

Austria

South Korea

France

United Kingdom

India

Poland

Japan

Germany

Israel
<figure><img src="image_11.png" /></figure>
<figure><img src="image_11.png" /></figure>
List of External Reviewers

N.R. Aravind

Julien Baste

Max Bannach

Rémy Belmonte

Édouard Bonnet

Marin Bougeret

Nicolas Bousquet

Yijia Chen

Rajesh Chitnis

Radu Curticapean

Konrad Kazimierz Dabrowski

Eduard Eiben

Bruno Escoffier

Jakub Gajarský

Archontia Giannopoulou

Petr Golovach

Daniel Gonçalves

Lars Jaffke

Peter Jonsson

Ioannis Katsikarelis

Eun Jung Kim

Dušan Knop

Van Bang Le

Euiwoong Lee

Erik Jan van Leeuwen

Kitty Meeks

Tillmann Miltzow

Pranabendu Misra

Valia Mitsou

Kamran Najeebullah

Rolf Niedermeier

Yota Otachi

Fahad Panolan

Marcin Pilipczuk

Ashutosh Rai

Felix Reidl

Ignasi Sau

Saket Saurabh

Sebastian Siebertz

Malte Skambath

Ondřej Suchý

Prafullkumar Tale

Dimitrios Thilikos

Mathias Weller

Stanislav Živný
<figure><img src="image_12.png" /></figure>

List of External Reviewers

N.R. Aravind

Julien Baste

Max Bannach

Rémy Belmonte

Édouard Bonnet

Marin Bougeret

Nicolas Bousquet

Yijia Chen

Rajesh Chitnis

Radu Curticapean

Konrad Kazimierz Dabrowski

Eduard Eiben

Bruno Escoffier

Jakub Gajarský

Archontia Giannopoulou

Petr Golovach

Daniel Gonçalves

Lars Jaffke

Peter Jonsson

Ioannis Katsikarelis

Eun Jung Kim

Dušan Knop

Van Bang Le

Euiwoong Lee

Erik Jan van Leeuwen

Kitty Meeks

Tillmann Miltzow

Pranabendu Misra

Valia Mitsou

Kamran Najeebullah

Rolf Niedermeier

Yota Otachi

Fahad Panolan

Marcin Pilipczuk

Ashutosh Rai

Felix Reidl

Ignasi Sau

Saket Saurabh

Sebastian Siebertz

Malte Skambath

Ondřej Suchý

Prafullkumar Tale

Dimitrios Thilikos

Mathias Weller

Stanislav Živný
<figure><img src="image_12.png" /></figure>
<figure><img src="image_13.png" /></figure>
List of Authors

Akanksha Agrawal, Hungarian Academy of Sciences, Hungary

Ana Silva, Universidade Federal do Ceará, Fortaleza, Brazil

Arnoud A. W. M. de Kroon, University of Oxford, United Kingdom

Astrid Pieterse, Eindhoven University of Technology, Netherlands

Bart M. P. Jansen, University of Eindhoven, Netherlands

Bas A. M. van Geffen, University of Oxford, United Kingdom

Carlos Vinícius G. C. Lima, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

Charis Papadopoulos, University of Ioannina, Greece

Christian Komusiewicz, Philipps-Universität Marburg, Germany

Daniel Lokshtanov, University of Bergen, Norway

Dániel Marx, Hungarian Academy of Sciences, Hungary

Danil Sagunov, Saint Petersburg Academic University of the Russian Academy of Sciences, Russia

David Eppstein, University of California, Irvine, United States

Dieter Kratsch, Université de Lorraine - Metz, France

Dimitrios M. Thilikos, CNRS, Université de Montpellier, France

Dušan Knop, University of Bergen, Norway

Édouard Bonnet, Université de Lyon, France

Elham Havvaei, University of California, Irvine, United States

Fiona Skerman, Uppsala University, Sweden

Florian Barbero, Université de Montpellier, France

Hendrik Molter, TU Berlin, Germany

Hubie Chen, University of London, United Kingdom

Ignasi Sau, CNRS, Université de Montpellier, France

Ivan Bliznets, St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, Russia

Jan Arne Telle, University of Bergen, Norway

Jocelyn Thiebaut, Université de Montpellier, France

Johannes Schmitt, ETH Zurich, Switzerland

Juho-Kustaa Kangas, Aalto University, Finland

Julien Baste, Sorbonne Université, France

Júlio Araújo, Universidade Federal do Ceará, Fortaleza Brazil

Junjie Luo, TU Berlin, China

Karl Bringmann, Max-Planck-Institut für Informatik, Germany

Katrin Casel, University of Potsdam, Germany

Kitty Meeks, University of Glasgow, United Kingdom

Lars Jaffke, University of Bergen, Norway

Lawqueen Kanesh, The Institute of Mathematical Sciences, Chennai, India

Lucas Isenmann, Université de Montpellier, France

Magnus Wahlström, Royal Holloway, University of London, United Kingdom

Måns Magnusson, Lund University, Sweden

Marc Roth, Saarland University, Germany

<figure><img src="image_13.png" /></figure>
List of Authors

Akanksha Agrawal, Hungarian Academy of Sciences, Hungary

Ana Silva, Universidade Federal do Ceará, Fortaleza, Brazil

Arnoud A. W. M. de Kroon, University of Oxford, United Kingdom

Astrid Pieterse, Eindhoven University of Technology, Netherlands

Bart M. P. Jansen, University of Eindhoven, Netherlands

Bas A. M. van Geffen, University of Oxford, United Kingdom

Carlos Vinícius G. C. Lima, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

Charis Papadopoulos, University of Ioannina, Greece

Christian Komusiewicz, Philipps-Universität Marburg, Germany

Daniel Lokshtanov, University of Bergen, Norway

Dániel Marx, Hungarian Academy of Sciences, Hungary

Danil Sagunov, Saint Petersburg Academic University of the Russian Academy of Sciences, Russia

David Eppstein, University of California, Irvine, United States

Dieter Kratsch, Université de Lorraine - Metz, France

Dimitrios M. Thilikos, CNRS, Université de Montpellier, France

Dušan Knop, University of Bergen, Norway

Édouard Bonnet, Université de Lyon, France
Elham Havvaei, University of California, Irvine, United States

Fiona Skerman, Uppsala University, Sweden

Florian Barbero, Université de Montpellier, France

Hendrik Molter, TU Berlin, Germany

Hubie Chen, University of London, United Kingdom

Ignasi Sau, CNRS, Université de Montpellier, France

Ivan Bliznets, St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, Russia

Jan Arne Telle, University of Bergen, Norway

Jocelyn Thiebaut, Université de Montpellier, France

Johannes Schmitt, ETH Zurich, Switzerland

Juho-Kustaa Kangas, Aalto University, Finland

Julien Baste, Sorbonne Université, France

Júlio Araújo, Universidade Federal do Ceará, Fortaleza Brazil

Junjie Luo, TU Berlin, China

Karl Bringmann, Max-Planck-Institut für Informatik, Germany

Katrin Casel, University of Potsdam, Germany

Kitty Meeks, University of Glasgow, United Kingdom

Lars Jaffke, University of Bergen, Norway

Lawqueen Kanesh, The Institute of Mathematical Sciences, Chennai, India

Lucas Isenmann, Université de Montpellier, France

Magnus Wahlström, Royal Holloway, University of London, United Kingdom

Måns Magnusson, Lund University, Sweden

Marc Roth, Saarland University, Germany
Marcin Pilipczuk, Institute of Informatics,
University of Warsaw, Poland

Martin Koutecký, Technion, Israel

Mateus De Oliveira Oliveira, University of
Bergen, Norway

Max Bannach, Universität zu Lübeck,
Germany

Meirav Zehavi, Ben-Gurion University, Israel

Mikko Koivisto, University of Helsinki,
Finland

Nicolas Bousquet, Grenoble INP, France

O-joung Kwon, Incheon National University,
South Korea

Ondřej Suchý, Czech Technical University in
Prague, Czechia

Pallavi Jain, The Institute of Mathematical
Sciences, Chennai, India

Pierre Charbit, Université Paris Diderot,
France

Pranabendu Misra, University of Bergen,
India

Rémi Watrigant, Université de Lyon, France

Rolf Morel, University of Oxford, United
Kingdom

Saket Saurabh, The Institute of
Mathematical Sciences, Chennai, India

Sami Salonen, University of Helsinki, Finland

Shaohua Li, Institute of Informatics,
University of Warsaw, Poland

Spyridon Tzimas, University of Ioannina,
Greece

Stefan Kratsch, HU Berlin, Germany

Stéphan Thomassé, Université de Lyon,
France

Thore Husfeldt, IT University of
Copenhagen and Lund University, Denmark

Till Tantau, University Lübeck, Germany

Tomáš Gavenčiak, Charles University
Prague, Czechia

Torstein J. F. Strømme, University of
Bergen, Norway

Van Bang Le, Universität Rostock, Germany

Victor A. Campos, Universidade Federal do
Ceará, Fortaleza Brazil

Vinícius Fernandes Dos Santos, Universidade
Federal de Minas Gerais, Belo Horizonte,
Brazil
Marcin Pilipczuk, Institute of Informatics,
University of Warsaw, Poland

Martin Koutecký, Technion, Israel

Mateus De Oliveira Oliveira, University of
Bergen, Norway

Max Bannach, Universität zu Lübeck,
Germany

Meirav Zehavi, Ben-Gurion University, Israel

Mikko Koivisto, University of Helsinki,
Finland

Nicolas Bousquet, Grenoble INP, France

O-joung Kwon, Incheon National University,
South Korea

Ondřej Suchý, Czech Technical University in
Prague, Czechia

Pallavi Jain, The Institute of Mathematical
Sciences, Chennai, India

Pierre Charbit, Université Paris Diderot,
France

Pranabendu Misra, University of Bergen,
India

Rémi Watrigant, Université de Lyon, France

Rolf Morel, University of Oxford, United
Kingdom

Saket Saurabh, The Institute of
Mathematical Sciences, Chennai, India

Sami Salonen, University of Helsinki, Finland

Shaohua Li, Institute of Informatics,
University of Warsaw, Poland

Spyridon Tzimas, University of Ioannina,
Greece

Stefan Kratsch, HU Berlin, Germany

Stéphan Thomassé, Université de Lyon,
France

Thore Husfeldt, IT University of
Copenhagen and Lund University, Denmark

Till Tantau, University Lübeck, Germany

Tomáš Gavenčiak, Charles University
Prague, Czechia

Torstein J. F. Strømme, University of
Bergen, Norway

Van Bang Le, Universität Rostock, Germany

Victor A. Campos, Universidade Federal do
Ceará, Fortaleza Brazil

Vinícius Fernandes Dos Santos, Universidade
Federal de Minas Gerais, Belo Horizonte,
Brazil
# Counting Problems in Parameterized Complexity

## Radu Curticapean

Basic Algorithms Research Copenhagen (BARC) and IT University of Copenhagen, Copenhagen, Denmark
radu.curticapean@gmail.com

https://orcid.org/0000-0001-7201-9905

## Abstract

This survey is an invitation to parameterized counting problems for readers with a background in parameterized algorithms and complexity. After an introduction to the peculiarities of counting complexity, we survey the parameterized approach to counting problems, with a focus on two topics of recent interest: Counting small patterns in large graphs, and counting perfect matchings and Hamiltonian cycles in well-structured graphs.

While this survey presupposes familiarity with parameterized algorithms and complexity, we aim at explaining all relevant notions from counting complexity in a self-contained way.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Problems, reductions and completeness

**Keywords and phrases** counting complexity, parameterized complexity, graph motifs, perfect matchings, graph minor theory, Hamiltonian cycles

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.1

**Category** Invited Tutorial

**Funding** BARC is supported by Villum Foundation Grant No. 16582.

**Acknowledgements** I wish to thank all my colleagues for the discussions on this topic and the collaborations over the last years.

# 1 Introduction

Many problems in computer science ask about the *existence* of solutions, such as satisfying assignments or graph structures with certain properties. However, in both practice and theory, it may be equally important to *count* solutions.

In network science, counting problems occur in the context of *graph motifs* [79], which are small patterns in graphs that occur unexpectedly often. For instance, social networks exhibit lower numbers of induced 3-vertex paths than one would expect in comparable random networks. This is a consequence of the *triadic closure* [56], the fact that two people with a common friend are likely to be friends themselves. Such phenomena cannot be observed by merely testing existence of patterns.

In statistical physics, thermodynamic properties of discrete systems are determined by *partition functions* [59]; such functions essentially count the admissible states of systems. As an example, the *dimer model* is a graph-based system that models how atoms can pair up to two-atom molecules [90, 65, 66]. In the 1960s, while attempting to find formulas for the partition function of the dimer model, physicists invented a polynomial-time algorithm for counting perfect matchings in planar graphs.

<figure><img src="image_14.png" /></figure>
# Counting Problems in Parameterized Complexity

## Radu Curticapean

Basic Algorithms Research Copenhagen (BARC) and IT University of Copenhagen, Copenhagen, Denmark
radu.curticapean@gmail.com

<figure><img src="image_14.png" /></figure>

https://orcid.org/0000-0001-7201-9905

## Abstract

This survey is an invitation to parameterized counting problems for readers with a background in parameterized algorithms and complexity. After an introduction to the peculiarities of counting complexity, we survey the parameterized approach to counting problems, with a focus on two topics of recent interest: Counting small patterns in large graphs, and counting perfect matchings and Hamiltonian cycles in well-structured graphs.

While this survey presupposes familiarity with parameterized algorithms and complexity, we aim at explaining all relevant notions from counting complexity in a self-contained way.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Problems, reductions and completeness

**Keywords and phrases** counting complexity, parameterized complexity, graph motifs, perfect matchings, graph minor theory, Hamiltonian cycles

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.1

**Category** Invited Tutorial

**Funding** BARC is supported by Villum Foundation Grant No. 16582.

**Acknowledgements** I wish to thank all my colleagues for the discussions on this topic and the collaborations over the last years.

# 1 Introduction

Many problems in computer science ask about the *existence* of solutions, such as satisfying assignments or graph structures with certain properties. However, in both practice and theory, it may be equally important to *count* solutions.

In network science, counting problems occur in the context of *graph motifs* [79], which are small patterns in graphs that occur unexpectedly often. For instance, social networks exhibit lower numbers of induced 3-vertex paths than one would expect in comparable random networks. This is a consequence of the *triadic closure* [56], the fact that two people with a common friend are likely to be friends themselves. Such phenomena cannot be observed by merely testing existence of patterns.

In statistical physics, thermodynamic properties of discrete systems are determined by *partition functions* [59]; such functions essentially count the admissible states of systems. As an example, the *dimer model* is a graph-based system that models how atoms can pair up to two-atom molecules [90, 65, 66]. In the 1960s, while attempting to find formulas for the partition function of the dimer model, physicists invented a polynomial-time algorithm for counting perfect matchings in planar graphs.

<figure><img src="image_15.png" /></figure>
## 1:2 Counting Problems in Parameterized Complexity

Counting can also help for problems that do not explicitly ask about numbers: Some of the best known algorithms for Hamiltonicity or coloring problems rely on intermediate counting problems [57, 8, 7].

### 1.1 Counting complexity

Most interesting counting problems are not known to admit polynomial-time algorithms. Sometimes, this can be explained through NP-hardness: For instance, counting the satisfying assignments of Boolean formulas is clearly NP-hard, since counting is certainly not easier than deciding existence. Such arguments however do *not* show hardness for counting problems that admit polynomial-time solvable decision versions, such as counting perfect matchings in graphs, even though these problems are presumed to be hard.

This called for a complexity theory that is specific to counting problems—such a theory was provided in 1979 by Valiant [93] in a seminal paper that introduced the complexity class #P, which captures most natural counting problems. The problems in #P are the counting versions of problems in NP: Rather than deciding the existence of a witness on a given input, the task is to count the witnesses. Counting problems are #P-hard if they admit polynomial-time Turing reductions from counting satisfying assignments of CNF formulas. As desired, this includes natural counting problems with easy decision versions, such as the problem of counting perfect matchings, as shown in Valiant's paper [93]. The #P-hardness proof for this problem required the introduction of several new reduction techniques, which we survey in Section 1.3, and showed that counting complexity amounts to more than just checking that NP-hardness reductions carry over to the counting setting.

Since the initial #P-hardness results, the study of counting problems advanced to a rich sub-area of complexity theory. In particular, large territories of counting problems were classified successfully by means of *dichotomy theorems* that sort into polynomial-time solvable and #P-hard problems [46, 16, 45, 21, 19]. For instance, a dichotomy theorem for the counting versions of *constraint satisfaction problems* was first shown a decade ago [17, 47], while the analogous result for the decision version was a long-standing open problem that was resolved only last year [18, 99]. The known dichotomy theorems for counting problems show that most interesting problems are indeed #P-hard, with only few polynomial-time solvable exceptions, such as counting perfect matchings in planar graphs [90, 65, 66], counting spanning trees [67], and problems solved by holographic algorithms [94, 20].

Thus, even more so than for NP-hard decision problems, relaxations were needed to cope with #P-hard counting problems. The most popular such coping technique is *approximate counting*, which allows outputs within a multiplicative error of the actual count [38, 24, 54, 55, 64]. Important #P-hard counting problems admit randomized polynomial-time approximation schemes; these famously include counting perfect matchings in bipartite graphs [60]. (The same result for *general graphs* remains a major open problem in approximate counting.) Counting problems were also investigated through *parameterized, exponential-time*, and *fine-grained* complexity [48, 77, 40]. In this survey, we focus on these paradigms.

### 1.2 Parameterized counting complexity

The multivariate paradigm has proven to be very successful for decision and optimization problems [44, 49, 82, 36], and it also enables a deeper understanding of counting problems. One of the first results on parameterized counting actually lies in the three-fold intersection of parameterization, approximation, and counting: Arvind and Raman [6] showed in 2002 how to approximately count *H*-subgraph copies in a graph *G* to within a multiplicative error of $1 \pm \epsilon$ in randomized time $f(k, \epsilon) \cdot n^{tw(H)+O(1)}$. This gives an FPT-algorithm for approximately counting *k*-paths, *k*-cycles, and *k*-matchings.
## 1:2 Counting Problems in Parameterized Complexity

Counting can also help for problems that do not explicitly ask about numbers: Some of the best known algorithms for Hamiltonicity or coloring problems rely on intermediate counting problems [57, 8, 7].

### 1.1 Counting complexity

Most interesting counting problems are not known to admit polynomial-time algorithms. Sometimes, this can be explained through NP-hardness: For instance, counting the satisfying assignments of Boolean formulas is clearly NP-hard, since counting is certainly not easier than deciding existence. Such arguments however do *not* show hardness for counting problems that admit polynomial-time solvable decision versions, such as counting perfect matchings in graphs, even though these problems are presumed to be hard.

This called for a complexity theory that is specific to counting problems—such a theory was provided in 1979 by Valiant [93] in a seminal paper that introduced the complexity class #P, which captures most natural counting problems. The problems in #P are the counting versions of problems in NP: Rather than deciding the existence of a witness on a given input, the task is to count the witnesses. Counting problems are #P-hard if they admit polynomial-time Turing reductions from counting satisfying assignments of CNF formulas. As desired, this includes natural counting problems with easy decision versions, such as the problem of counting perfect matchings, as shown in Valiant's paper [93]. The #P-hardness proof for this problem required the introduction of several new reduction techniques, which we survey in Section 1.3, and showed that counting complexity amounts to more than just checking that NP-hardness reductions carry over to the counting setting.

Since the initial #P-hardness results, the study of counting problems advanced to a rich sub-area of complexity theory. In particular, large territories of counting problems were classified successfully by means of *dichotomy theorems* that sort into polynomial-time solvable and #P-hard problems [46, 16, 45, 21, 19]. For instance, a dichotomy theorem for the counting versions of *constraint satisfaction problems* was first shown a decade ago [17, 47], while the analogous result for the decision version was a long-standing open problem that was resolved only last year [18, 99]. The known dichotomy theorems for counting problems show that most interesting problems are indeed #P-hard, with only few polynomial-time solvable exceptions, such as counting perfect matchings in planar graphs [90, 65, 66], counting spanning trees [67], and problems solved by holographic algorithms [94, 20].

Thus, even more so than for NP-hard decision problems, relaxations were needed to cope with #P-hard counting problems. The most popular such coping technique is *approximate counting*, which allows outputs within a multiplicative error of the actual count [38, 24, 54, 55, 64]. Important #P-hard counting problems admit randomized polynomial-time approximation schemes; these famously include counting perfect matchings in bipartite graphs [60]. (The same result for *general graphs* remains a major open problem in approximate counting.) Counting problems were also investigated through *parameterized, exponential-time*, and *fine-grained* complexity [48, 77, 40]. In this survey, we focus on these paradigms.

### 1.2 Parameterized counting complexity

The multivariate paradigm has proven to be very successful for decision and optimization problems [44, 49, 82, 36], and it also enables a deeper understanding of counting problems. One of the first results on parameterized counting actually lies in the three-fold intersection of parameterization, approximation, and counting: Arvind and Raman [6] showed in 2002 how to approximately count *H*-subgraph copies in a graph *G* to within a multiplicative error of $1 \pm \epsilon$ in randomized time $f(k, \epsilon) \cdot n^{tw(H)+O(1)}$. This gives an FPT-algorithm for approximately counting *k*-paths, *k*-cycles, and *k*-matchings.
However, no FPT-algorithm is known for counting such subgraph patterns *exactly*, creating the need for a parameterized analogue of #P: While the problem of counting *k*-cliques (even approximately) is W[1]-hard through its decision version, we cannot say the same about counting *k*-paths, *k*-cycles, or *k*-matchings, as the decision versions of these problems are FPT [4]. To deal with such issues, Flum and Grohe [48] and independently McMartin [77] introduced the class #W[1], a natural parameterized version of #P: In analogy to W[1], the canonical #W[1]-hard problem is that of counting *k*-cliques in a graph, and a problem is #W[1]-hard if it admits a parameterized Turing reduction from counting *k*-cliques.

Apart from introducing the class #W[1], Flum and Grohe also proved an impressive parameterized reduction from counting *k*-cliques to counting *k*-cycles and *k*-paths, thus proving the #W[1]-hardness of these problems and paving the way for a rich complexity theory of parameterized counting problems. Techniques in parameterized counting were later used to classify the complexity of general subgraph counting problems parameterized by pattern size [10, 26, 32, 78, 63, 61, 62, 15, 85, 86, 31], to obtain FPT-approximation results for #P-hard problems [62, 63, 78, 1, 13], and to investigate classical #P-hard problems like counting perfect matchings under structural parameters [28, 35, 32, 34].

As for decision and optimization problems, more precise running time bounds for param-
eterized counting problems can be obtained through the exponential-time hypothesis ETH
[58]. This hypothesis also admits a counting version #ETH, introduced by Dell et al. [40],
which asserts that counting satisfying assignments to Boolean 3-CNF-formulas requires time
$2^{\Omega(n)}$. A sparsification lemma [40] and counting-specific reduction techniques [29] are known
for #ETH, enabling tight lower bounds for a variety of problems [14, 29]. Note that #ETH
may be a weaker assumption than ETH.

1.3 Techniques for counting problems

To gain some intuition for the algorithmic boundary of parameterized counting, let us examine
the fates of some techniques for parameterized algorithms as we go from decision to counting:

- To start on a positive note, *dynamic programming* often carries over to counting problems. For instance, in treewidth-based DPs, *join* nodes correspond very roughly to multiplication (more realistically, *convolution* [51]) and *forget* nodes correspond roughly to summation over the possible states of the vertex to be forgotten. Most importantly, Courcelle's theorem admits analogous counting versions [5, 26, 74]. There also is an FPT-algorithm for counting the models of FOL formulas on structures of locally bounded treewidth [52].

- On the other hand, *win-win* approaches like *bidimensionality* [42, 50] fail for counting problems when the large-treewidth case “wins” via a guaranteed solution: As an example, knowing that *k*-paths exist due to the presence of a $\sqrt{k} \times \sqrt{k}$ grid minor does a priori not facilitate counting. However, if the large-treewidth case guarantees the *absence* of the solutions sought for, then we only need to address the low-treewidth case: As mentioned above, treewidth-based DPs for decision problems often support the extension to counting.

- *Color coding* [4] fails, strictly speaking: While every *k*-set will be colorful under at least one coloring, there is otherwise no guarantee on the number of such colorings. In fact, it is known [2] that a perfectly balanced collection of colorings needs size $\Omega(n^{k/2})$. There are however approximately balanced collections that enable approximate counting [1, 3].

- Most *kernelization* techniques preserve only the existence of solutions. However, under proper definitions of a counting kernel, some techniques like the sunflower kernel for bounded-cardinality *k*-hitting sets do carry over [91]. In Section 3.1, we will also see an application of protrusion replacement [12] that works for counting.
However, no FPT-algorithm is known for counting such subgraph patterns *exactly*, creating the need for a parameterized analogue of #P: While the problem of counting *k*-cliques (even approximately) is W[1]-hard through its decision version, we cannot say the same about counting *k*-paths, *k*-cycles, or *k*-matchings, as the decision versions of these problems are FPT [4]. To deal with such issues, Flum and Grohe [48] and independently McMartin [77] introduced the class #W[1], a natural parameterized version of #P: In analogy to W[1], the canonical #W[1]-hard problem is that of counting *k*-cliques in a graph, and a problem is #W[1]-hard if it admits a parameterized Turing reduction from counting *k*-cliques.

Apart from introducing the class #W[1], Flum and Grohe also proved an impressive parameterized reduction from counting *k*-cliques to counting *k*-cycles and *k*-paths, thus proving the #W[1]-hardness of these problems and paving the way for a rich complexity theory of parameterized counting problems. Techniques in parameterized counting were later used to classify the complexity of general subgraph counting problems parameterized by pattern size [10, 26, 33, 78, 63, 61, 62, 15, 85, 86, 31], to obtain FPT-approximation results for #P-hard problems [62, 63, 78, 1, 13], and to investigate classical #P-hard problems like counting perfect matchings under structural parameters [28, 35, 32, 34].

As for decision and optimization problems, more precise running time bounds for param-
eterized counting problems can be obtained through the exponential-time hypothesis ETH
[58]. This hypothesis also admits a counting version #ETH, introduced by Dell et al. [40],
which asserts that counting satisfying assignments to Boolean 3-CNF-formulas requires time
$2^{\Omega(n)}$. A sparsification lemma [40] and counting-specific reduction techniques [29] are known
for #ETH, enabling tight lower bounds for a variety of problems [14, 29]. Note that #ETH
may be a weaker assumption than ETH.

1.3 Techniques for counting problems

To gain some intuition for the algorithmic boundary of parameterized counting, let us examine
the fates of some techniques for parameterized algorithms as we go from decision to counting:

- To start on a positive note, *dynamic programming* often carries over to counting problems. For instance, in treewidth-based DPs, *join* nodes correspond very roughly to multiplication (more realistically, *convolution* [51]) and *forget* nodes correspond roughly to summation over the possible states of the vertex to be forgotten. Most importantly, Courcelle's theorem admits analogous counting versions [5, 26, 74]. There also is an FPT-algorithm for counting the models of FOL formulas on structures of locally bounded treewidth [52].

- On the other hand, *win-win* approaches like *bidimensionality* [42, 50] fail for counting problems when the large-treewidth case “wins” via a guaranteed solution: As an example, knowing that *k*-paths exist due to the presence of a $\sqrt{k} \times \sqrt{k}$ grid minor does a priori not facilitate counting. However, if the large-treewidth case guarantees the *absence* of the solutions sought for, then we only need to address the low-treewidth case: As mentioned above, treewidth-based DPs for decision problems often support the extension to counting.

- *Color coding* [4] fails, strictly speaking: While every *k*-set will be colorful under at least one coloring, there is otherwise no guarantee on the number of such colorings. In fact, it is known [2] that a perfectly balanced collection of colorings needs size $\Omega(n^{k/2})$. There are however approximately balanced collections that enable approximate counting [1, 3].

- Most *kernelization* techniques preserve only the existence of solutions. However, under proper definitions of a counting kernel, some techniques like the sunflower kernel for bounded-cardinality *k*-hitting sets do carry over [91]. In Section 3.1, we will also see an application of protrusion replacement [12] that works for counting.
## 1:4 Counting Problems in Parameterized Complexity

What we lose in algorithmic techniques when going into the counting world, we gain in new reduction techniques for proving hardness. In the following, we survey some reduction techniques for #P- and #W[1]-hardness that are unavailable for NP- and W[1]-hardness.

### Cancellations in gadgets

Gadgets in NP- or W[1]-hardness proofs typically serve the purpose of testing local states: They can be extended by an internal solution iff their external state is *admissible* in a problem-specific sense. In counting problems with easy decision versions, gadgets with this property may not necessarily exist, as they might imply hardness of the decision version. We must actually use the power of counting: As first done by Valiant [93], we can design gadgets that do admit unwanted internal extensions for non-admissible external states, but such that the (weighted) contributions of unwanted internal extensions *cancel out to zero*.

As an example, let us consider a weighted version of counting perfect matchings: Given an edge-weighted graph $G = (V, E, w)$, we define

$$ \text{PerfMatch}(G) = \sum_M \prod_{e \in M} w(e), $$

where $M$ ranges over the perfect matchings of $G$. The following edge-weighted gadget $\Gamma$ with special vertices $X = \{x_1, \dots, x_4\}$ acts as an “equality gadget” for PerfMatch: For $S = \emptyset$ and $S = X$, we have $\text{PerfMatch}(\Gamma - S) = 1$, and we also have $\text{PerfMatch}(\Gamma - S) = 0$ for all other $S \subseteq X$. (The gadget is from [34] and was found with a computer algebra system.)

<figure><img src="image_15.png" /></figure>

Summarizing, if the gadget $\Gamma$ is used in a larger construction, then *effectively* either all or none of $X$ must be matched by edges outside of $\Gamma$. Even though $\Gamma$ does admit internal matchings in some of the other cases, the weighted number of such matchings cancels to zero.

### Interpolation

In the counting world, Turing reductions become very powerful, as the results of oracle queries can be added, multiplied, subtracted—a luxury we do not have with Boolean values. This enables linear algebra on oracle outputs, in particular, *polynomial interpolation* [93, 92, 98, 29]. As an example of this prevalent technique, we show a classical reduction that computes $\text{PerfMatch}(G)$ for an $n$-vertex graph $G$ with edge-weights $\pm 1$ when given an oracle for counting perfect matchings in unweighted graphs.

Let $x$ be an indeterminate and define a graph $G_x$ by replacing each edge of weight $-1$ in $G$ by an edge of weight $x$. Then $p := \text{PerfMatch}(G_x)$ is a polynomial in $x$ of degree at most $\frac{n}{2}$ such that $p(-1) = \text{PerfMatch}(G)$. If we knew the $\frac{n}{2} + 1$ values $p(0), \dots, p(\frac{n}{2})$, we could recover all coefficients of $p(G)$ via Lagrange interpolation and could thus evaluate $p(-1)$. But the evaluation $p(i)$ for $0 \le i \le \frac{n}{2}$ can be obtained as $\text{PerfMatch}(G_i)$ for the graph $G_i$ in which each edge of weight $x$ is replaced by an edge of weight $i$. Each such edge in turn can be simulated by a bundle of $i$ parallel unweighted edges.

Overall, we can recover the value of $\text{PerfMatch}(G)$ for the $\pm 1$-weighted graph $G$ by counting perfect matchings in the unweighted graphs $G_0, \dots, G_{n/2}$ via oracle calls and performing linear algebra on the oracle results to interpolate the polynomial $p$.
## 1:4 Counting Problems in Parameterized Complexity

What we lose in algorithmic techniques when going into the counting world, we gain in new reduction techniques for proving hardness. In the following, we survey some reduction techniques for #P- and #W[1]-hardness that are unavailable for NP- and W[1]-hardness.

### Cancellations in gadgets

Gadgets in NP- or W[1]-hardness proofs typically serve the purpose of testing local states: They can be extended by an internal solution iff their external state is *admissible* in a problem-specific sense. In counting problems with easy decision versions, gadgets with this property may not necessarily exist, as they might imply hardness of the decision version. We must actually use the power of counting: As first done by Valiant [93], we can design gadgets that do admit unwanted internal extensions for non-admissible external states, but such that the (weighted) contributions of unwanted internal extensions *cancel out to zero*.

As an example, let us consider a weighted version of counting perfect matchings: Given an edge-weighted graph $G = (V, E, w)$, we define

$$ \text{PerfMatch}(G) = \sum_M \prod_{e \in M} w(e), $$

where $M$ ranges over the perfect matchings of $G$. The following edge-weighted gadget $\Gamma$ with special vertices $X = \{x_1, \dots, x_4\}$ acts as an “equality gadget” for $\text{PerfMatch}$: For $S = \emptyset$ and $S = X$, we have $\text{PerfMatch}(\Gamma - S) = 1$, and we also have $\text{PerfMatch}(\Gamma - S) = 0$ for all other $S \subseteq X$. (The gadget is from [34] and was found with a computer algebra system.)

<figure><img src="image_16.png" /></figure>

Summarizing, if the gadget $\Gamma$ is used in a larger construction, then *effectively* either all or none of $X$ must be matched by edges outside of $\Gamma$. Even though $\Gamma$ does admit internal matchings in some of the other cases, the weighted number of such matchings cancels to zero.

### Interpolation

In the counting world, Turing reductions become very powerful, as the results of oracle queries can be added, multiplied, subtracted—a luxury we do not have with Boolean values. This enables linear algebra on oracle outputs, in particular, *polynomial interpolation* [93, 92, 98, 29]. As an example of this prevalent technique, we show a classical reduction that computes $\text{PerfMatch}(G)$ for an $n$-vertex graph $G$ with edge-weights $\pm 1$ when given an oracle for counting perfect matchings in unweighted graphs.

Let $x$ be an indeterminate and define a graph $G_x$ by replacing each edge of weight $-1$ in $G$ by an edge of weight $x$. Then $p := \text{PerfMatch}(G_x)$ is a polynomial in $x$ of degree at most $\frac{n}{2}$ such that $p(-1) = \text{PerfMatch}(G)$. If we knew the $\frac{n}{2} + 1$ values $p(0), \dots, p(\frac{n}{2})$, we could recover all coefficients of $p(G)$ via Lagrange interpolation and could thus evaluate $p(-1)$. But the evaluation $p(i)$ for $0 \le i \le \frac{n}{2}$ can be obtained as $\text{PerfMatch}(G_i)$ for the graph $G_i$ in which each edge of weight $x$ is replaced by an edge of weight $i$. Each such edge in turn can be simulated by a bundle of $i$ parallel unweighted edges.

Overall, we can recover the value of $\text{PerfMatch}(G)$ for the $\pm 1$-weighted graph $G$ by counting perfect matchings in the unweighted graphs $G_0, \dots, G_{n/2}$ via oracle calls and performing linear algebra on the oracle results to interpolate the polynomial $p$.
## Inclusion-exclusion

Also taking linear combinations of oracle outputs, the inclusion-exclusion principle is a very useful tool for parameterized hardness results [78, 39, 25, 33]. Given a universe $\Omega$ and “bad” subsets $A_1, \dots, A_k \subseteq \Omega$, inclusion-exclusion allows us to count those elements of $\Omega$ that avoid all bad subsets, provided that we know the sizes of intersections of bad subsets:

$$ \left| \Omega \setminus \bigcup_{i=1}^{k} A_i \right| = \sum_{S \subseteq \{1, \dots, k\}} (-1)^{|S|} |A_S| \quad (1) $$

with $A_\emptyset := \Omega$ and $A_S := \bigcap_{i \in S} A_i$ for $\emptyset \subset S \subseteq [k]$. We can thus determine the left-hand side with $2^k$ oracle calls to numbers $|A_S|$ for $S \subseteq [k]$.

We use (1) for a parameterized reduction from the colorful subgraph isomorphism problem to the uncolored version [78, 33]. Let $H$ and $G$ be graphs such that $G$ is (not necessarily properly) vertex-colored with colors from $\{1, \dots, k\}$ for $k = |V(H)|$. A subgraph copy of $H$ in $G$ is colorful if it does not avoid any color. Thus, writing $\Omega$ for the set of all $H$-copies in $G$, and defining $A_i$ for $i \in [k]$ to be the set of $H$-copies that do avoid color $i$, we can invoke (1) to obtain the number of colorful $H$-copies if we knew the cardinalities $|A_S|$ for $S \subseteq [k]$. But $|A_S|$ is just the number of $H$-copies avoiding all colors in $S$. These are precisely the $H$-copies in the graph $G_S$ obtained from $G$ by removing all vertices with a color among $S$ and ignoring colors. The numbers of $H$-copies in $G_S$ can then be obtained by oracle calls to counting uncolored $H$-copies, and we only need $2^k$ such numbers to evaluate (1).

Somewhat peculiarly, this reduction goes the opposite way as in the decision problem: In the decision version of subgraph isomorphism, color-coding reduces from the uncolored to the colorful setting, while the reverse direction is generally not known. In the counting version however, we have just seen a reduction from the uncolored to the colorful setting. Furthermore, the converse reduction is generally false: Counting $k$-paths is #W[1]-hard [48], whereas a simple FPT-algorithm counts colorful $k$-paths. See also an article by Meeks [78] for a nice overview of the relationship between colored and uncolored subgraph problems.

## Organization of this survey

After this brief introduction, we apply the multivariate perspective on counting to two specific problems: In Section 2, we count small patterns in large graphs. Complementary to that, in Section 3, we then count large patterns like perfect matchings and Hamiltonian cycles in graphs excluding fixed minors or bounded treewidth.

## 2 Counting small patterns

Large networks can often be approached by counting small patterns [79, 73]. This naturally leads to parameterized pattern counting problems: Given as input a pattern graph $H$ and a host graph $G$, determine the number of occurrences of $H$ in $G$, parameterized by the size of $H$. Such problems have been intensively studied in different communities; we survey some results in Section 2.1 and present recent developments in Section 2.2.

### 2.1 Results for individual pattern types

There are different ways of formalizing an occurrence of a pattern in a graph, and they can lead to stark differences in complexity. Below are some of the most common notions:
## Inclusion-exclusion

Also taking linear combinations of oracle outputs, the inclusion-exclusion principle is a very useful tool for parameterized hardness results [78, 39, 25, 33]. Given a universe $\Omega$ and “bad” subsets $A_1, \dots, A_k \subseteq \Omega$, inclusion-exclusion allows us to count those elements of $\Omega$ that avoid all bad subsets, provided that we know the sizes of intersections of bad subsets:

$$ \left| \Omega \setminus \bigcup_{i=1}^{k} A_i \right| = \sum_{S \subseteq \{1, \dots, k\}} (-1)^{|S|} |A_S| \quad (1) $$

with $A_\emptyset := \Omega$ and $A_S := \bigcap_{i \in S} A_i$ for $\emptyset \subseteq S \subseteq [k]$. We can thus determine the left-hand side with $2^k$ oracle calls to numbers $|A_S|$ for $S \subseteq [k]$.

We use (1) for a parameterized reduction from the colorful subgraph isomorphism problem to the uncolored version [78, 33]. Let $H$ and $G$ be graphs such that $G$ is (not necessarily properly) vertex-colored with colors from $\{1, \dots, k\}$ for $k = |V(H)|$. A subgraph copy of $H$ in $G$ is colorful if it does not avoid any color. Thus, writing $\Omega$ for the set of all $H$-copies in $G$, and defining $A_i$ for $i \in [k]$ to be the set of $H$-copies that do avoid color $i$, we can invoke (1) to obtain the number of colorful $H$-copies if we knew the cardinalities $|A_S|$ for $S \subseteq [k]$. But $|A_S|$ is just the number of $H$-copies avoiding all colors in $S$. These are precisely the $H$-copies in the graph $G_S$ obtained from $G$ by removing all vertices with a color among $S$ and ignoring colors. The numbers of $H$-copies in $G_S$ can then be obtained by oracle calls to counting uncolored $H$-copies, and we only need $2^k$ such numbers to evaluate (1).

Somewhat peculiarly, this reduction goes the opposite way as in the decision problem: In the decision version of subgraph isomorphism, color-coding reduces from the uncolored to the colorful setting, while the reverse direction is generally not known. In the counting version however, we have just seen a reduction from the uncolored to the colorful setting. Furthermore, the converse reduction is generally false: Counting $k$-paths is \#W[1]-hard [48], whereas a simple FPT-algorithm counts colorful $k$-paths. See also an article by Meeks [78] for a nice overview of the relationship between colored and uncolored subgraph problems.

## Organization of this survey

After this brief introduction, we apply the multivariate perspective on counting to two specific problems: In Section 2, we count small patterns in large graphs. Complementary to that, in Section 3, we then count large patterns like perfect matchings and Hamiltonian cycles in graphs excluding fixed minors or bounded treewidth.

# 2 Counting small patterns

Large networks can often be approached by counting small patterns [79, 73]. This naturally leads to parameterized pattern counting problems: Given as input a pattern graph $H$ and a host graph $G$, determine the number of occurrences of $H$ in $G$, parameterized by the size of $H$. Such problems have been intensively studied in different communities; we survey some results in Section 2.1 and present recent developments in Section 2.2.

## 2.1 Results for individual pattern types

There are different ways of formalizing an occurrence of a pattern in a graph, and they can lead to stark differences in complexity. Below are some of the most common notions:
1:6 Counting Problems in Parameterized Complexity

- Let us write $\text{sub}(H, G)$ for the number of (not necessarily induced) *subgraphs* of $G$ that are isomorphic to $H$. Closely related is $\text{emb}(H, G)$, the number of *embeddings* from $H$ to $G$: An embedding from $H$ to $G$ is an injective function $f: V(H) \to V(G)$ such that $uv \in E(H)$ implies $f(u)f(v) \in E(G)$. We have $\text{emb}(H, G) = \text{aut}(H) \cdot \text{sub}(H, G)$, where $\text{aut}(H)$ is the number of automorphisms of $H$.

- Depending on the application, we may also ask for the number $\text{ind}(H, G)$ of *induced subgraphs* isomorphic to $H$. Extending this, Jerrum and Meeks introduced a more general model [62, 61]: For a fixed property $\Phi$ of $k$-vertex graphs, we can ask to determine the number $\text{ind}(\Phi, G)$ of $k$-vertex subsets inducing a subgraph with property $\Phi$.

- We could also ask for the number $\text{hom}(H, G)$ of *homomorphisms* from $H$ to $G$. These are essentially embeddings that need not be injective, that is, functions $f: V(H) \to V(G)$ such that $uv \in E(H)$ implies $f(u)f(v) \in E(G)$. Homomorphism counts appear in the setting of database queries [22], they are a fundamental notion in the theory of graph limits and graph algebras [73], and we will see in Section 2.2 that they enable a deeper understanding of subgraph and induced subgraph counting problems.

Improved algorithms

All of the above numbers can be computed in time $O(f(k) \cdot n^k)$ by brute force; we write $k = |V(H)|$ and $n = |V(G)|$ throughout. As even a moderate value of $k$ can be prohibitively large for large host graphs $G$, the possibility of improved algorithms was investigated:

- Fast matrix multiplication solves the above problems in time $f(k) \cdot n^{\omega k/3+O(1)}$, where $\omega < 2.373$ is the exponent of matrix multiplication [81].

- For computing $\text{sub}(H, G)$ and thin patterns $H$, an additional improvement to $f(k) \cdot n^{0.46k+2\text{pw}(H)+O(1)}$ time is possible, where $\text{pw}(H)$ denotes the pathwidth of $H$ [9].

- Again for $\text{sub}(H, G)$, substantial improvements can be made when $H$ has bounded vertex-cover number $\text{vc}(H)$: As an example, if $H = K_{1,k}$ is a star with $k \ge 2$ rays, then $\text{sub}(H, G) = \sum_{v \in V(G)} \binom{d(v)}{k}$, where $d(v)$ denotes the degree of $v$. This formula can be evaluated in linear time. More generally, if $H$ has a vertex-cover $C$, then we can iterate over all $n^{|C|}$ maps from $C$ into $G$ and determine, for each map, the number of ways to extend the image of $C$ to a full copy of $H$. This last step can be performed in polynomial time, enabling an overall running time of $f(k) \cdot n^{\text{vc}(H)+O(1)}$ [69, 97].

- We will show in Section 2.2 that $\text{sub}(H, G)$ can be computed in $f(k) \cdot n^{0.174\ell+O(1)}$ time when $H$ has $\ell$ edges; this is useful for counting matchings, paths, or cycles.

It is natural to ask how far such improvements can be pushed. For fixed graphs $H$, let us write $\text{sub}(H, \cdot)$, $\text{ind}(H, \cdot)$ and $\text{hom}(H, \cdot)$ for the graph parameters<fnref n="1" /> that map input graphs $G$ to the numbers $\text{sub}(H, G)$, $\text{ind}(H, G)$ and $\text{hom}(H, G)$. As it is interesting to quantify running time improvements even for algorithms that are not FPT, we define the *complexity exponent* of graph parameters like $\text{sub}(H, \cdot)$ to be the infimum over all $C \in \mathbb{R}$ such that $\text{sub}(H, G)$ can be evaluated in time $O(n^C)$ on input $G$ [30]. Note that the complexity exponent of $\text{sub}(H, \cdot)$, $\text{ind}(H, \cdot)$ and $\text{hom}(H, \cdot)$ for fixed $H$ is always bounded from above by $k$, but it may be well below $k$, say, for $\text{sub}(H, \cdot)$ where $H$ has low vertex-cover number.

<footnote n="1">¹ A graph parameter $f$ is a function from graphs into $\mathbb{Q}$. Please note that *graph parameters* are not (necessarily) *parameters* in the sense of parameterized complexity—it is a bit awkward to talk about the “parameterized complexity of graph parameters”, but graph parameters are a well-established notion.</footnote>
1:6 Counting Problems in Parameterized Complexity

Let us write $\text{sub}(H, G)$ for the number of (not necessarily induced) *subgraphs* of $G$ that are isomorphic to $H$. Closely related is $\text{emb}(H, G)$, the number of *embeddings* from $H$ to $G$: An embedding from $H$ to $G$ is an injective function $f: V(H) \to V(G)$ such that $uv \in E(H)$ implies $f(u)f(v) \in E(G)$. We have $\text{emb}(H, G) = \text{aut}(H) \cdot \text{sub}(H, G)$, where $\text{aut}(H)$ is the number of automorphisms of $H$.

Depending on the application, we may also ask for the number $\text{ind}(H, G)$ of *induced subgraphs* isomorphic to $H$. Extending this, Jerrum and Meeks introduced a more general model [62, 61]: For a fixed property $\Phi$ of $k$-vertex graphs, we can ask to determine the number $\text{ind}(\Phi, G)$ of $k$-vertex subsets inducing a subgraph with property $\Phi$.

We could also ask for the number $\text{hom}(H, G)$ of *homomorphisms* from $H$ to $G$. These are essentially embeddings that need not be injective, that is, functions $f: V(H) \to V(G)$ such that $uv \in E(H)$ implies $f(u)f(v) \in E(G)$. Homomorphism counts appear in the setting of database queries [22], they are a fundamental notion in the theory of graph limits and graph algebras [73], and we will see in Section 2.2 that they enable a deeper understanding of subgraph and induced subgraph counting problems.

Improved algorithms

All of the above numbers can be computed in time $O(f(k) \cdot n^k)$ by brute force; we write $k = |V(H)|$ and $n = |V(G)|$ throughout. As even a moderate value of $k$ can be prohibitively large for large host graphs $G$, the possibility of improved algorithms was investigated:

Fast matrix multiplication solves the above problems in time $f(k) \cdot n^{\omega k/3+O(1)}$, where $\omega < 2.373$ is the exponent of matrix multiplication [81].

For computing $\text{sub}(H, G)$ and thin patterns $H$, an additional improvement to $f(k) \cdot n^{0.46k+2\text{pw}(H)+O(1)}$ time is possible, where $\text{pw}(H)$ denotes the pathwidth of $H$ [9].

Again for $\text{sub}(H, G)$, substantial improvements can be made when $H$ has bounded vertex-cover number $\text{vc}(H)$: As an example, if $H = K_{1,k}$ is a star with $k \ge 2$ rays, then $\text{sub}(H, G) = \sum_{v \in V(G)} \binom{d(v)}{k}$, where $d(v)$ denotes the degree of $v$. This formula can be evaluated in linear time. More generally, if $H$ has a vertex-cover $C$, then we can iterate over all $n^{|C|}$ maps from $C$ into $G$ and determine, for each map, the number of ways to extend the image of $C$ to a full copy of $H$. This last step can be performed in polynomial time, enabling an overall running time of $f(k) \cdot n^{\text{vc}(H)+O(1)}$ [69, 97].

We will show in Section 2.2 that $\text{sub}(H, G)$ can be computed in $f(k) \cdot n^{0.174\ell+O(1)}$ time when $H$ has $\ell$ edges; this is useful for counting matchings, paths, or cycles.

It is natural to ask how far such improvements can be pushed. For fixed graphs $H$, let us write $\text{sub}(H, \cdot)$, $\text{ind}(H, \cdot)$ and $\text{hom}(H, \cdot)$ for the graph parameters<fnref n="1" /> that map input graphs $G$ to the numbers $\text{sub}(H, G)$, $\text{ind}(H, G)$ and $\text{hom}(H, G)$. As it is interesting to quantify running time improvements even for algorithms that are not FPT, we define the *complexity exponent* of graph parameters like $\text{sub}(H, \cdot)$ to be the infimum over all $C \in \mathbb{R}$ such that $\text{sub}(H, G)$ can be evaluated in time $O(n^C)$ on input $G$ [30]. Note that the complexity exponent of $\text{sub}(H, \cdot)$, $\text{ind}(H, \cdot)$ and $\text{hom}(H, \cdot)$ for fixed $H$ is always bounded from above by $k$, but it may be well below $k$, say, for $\text{sub}(H, \cdot)$ where $H$ has low vertex-cover number.

<footnote n="1">¹ A graph parameter *f* is a function from graphs into Q. Please note that *graph parameters* are not (necessarily) *parameters* in the sense of parameterized complexity—it is a bit awkward to talk about the “parameterized complexity of graph parameters”, but graph parameters are a well-established notion.</footnote>
## Hardness results

We want to understand the optimal complexity exponents of graph parameters that count small patterns. Parameterized complexity allows us to aggregate graph parameters into classes $\mathcal{H}$ and prove statements on the asymptotic behaviour of the complexity exponents: Given a graph class $\mathcal{H}$, we define the problem $\text{sub}(\mathcal{H}, \cdot)$, where the task is to compute $\text{sub}(H, G)$ on input a pattern graph $H \in \mathcal{H}$ and an arbitrary host graph $G$. An analogous definition gives the problems $\text{ind}(\mathcal{H}, \cdot)$ and $\text{hom}(\mathcal{H}, \cdot)$.

If a problem $\text{sub}(\mathcal{H}, \cdot)$ is FPT or even polynomial-time solvable, then there is a fixed constant $C$ that bounds all complexity exponents of $\text{sub}(H, \cdot)$ for $H \in \mathcal{H}$. If $\text{sub}(\mathcal{H}, \cdot)$ is \#W[1]-hard, then we believe that no such constant exists. Furthermore, conditional lower bounds under \#ETH enable lower bounds on the asymptotic growth of complexity exponents. Indeed, such lower bounds are known for counting subgraphs, induced subgraphs, and homomorphisms for restricted pattern classes $\mathcal{H}$ that are recursively enumerable.

- If $\mathcal{H}$ is finite, then $\text{ind}(\mathcal{H}, \cdot)$ is polynomial-time solvable, otherwise it is \#W[1]-hard [25]. Furthermore, if $\mathcal{H}$ is infinite, then there is no $f(k) \cdot n^{o(k)}$ time algorithm for $\text{ind}(\mathcal{H}, \cdot)$ unless ETH fails. Note that this result holds for every fixed recursively enumerable class $\mathcal{H}$; it shows that no pattern structure whatsoever can be exploited for counting induced subgraphs. Jerrum and Meeks generalized this result and proved that counting $k$-vertex subgraphs with fixed properties $\Phi$ is \#W[1]-hard for certain well-behaved properties $\Phi$ like connectedness or having even/odd number of edges [61, 62, 63].

- For counting not necessarily induced subgraphs, we have seen above that pattern structure can be exploited: If the maximum vertex-cover number of graphs in $\mathcal{H}$ is finite, then $\text{sub}(\mathcal{H}, \cdot)$ is polynomial-time solvable. Otherwise the problem is known to be \#W[1]-hard [33]. We will see in the next section that an $f(k) \cdot n^{o(\text{vc}(H)/\log \text{vc}(H))}$ time algorithm would refute \#ETH, even for patterns from fixed classes $\mathcal{H}$.

- For counting homomorphisms, we may even allow bounded-treewidth patterns: If the treewidth of $\mathcal{H}$ is finite, then $\text{hom}(\mathcal{H}, \cdot)$ is polynomial-time solvable; otherwise the problem is \#W[1]-hard [39]. As a consequence of Marx's cornerstone "Can you beat treewidth" paper, \#ETH rules out an $f(k) \cdot n^{o(\text{tw}(H)/\log \text{tw}(H))}$ time algorithm [76].

## 2.2 Graph motif parameters

Despite the similar appearance of the problems $\text{ind}(\mathcal{H}, \cdot)$, $\text{sub}(\mathcal{H}, \cdot)$, and $\text{hom}(\mathcal{H}, \cdot)$, their dichotomy theorems were each proven about five years apart, by different people, using somewhat different techniques. Recently, it was shown that these problems can be studied in a uniform way: From the perspective of parameterized complexity, these problems become the same problem when "extended linearly".

More formally, graph parameters like $\text{sub}(H, \cdot)$ or $\text{ind}(H, \cdot)$ for fixed $H$ are special cases of so-called *graph motif parameters*, a notion introduced in [30] that adapts early works by Lovász [71, 73] to study counting small patterns from a parameterized perspective. Apart from $\text{sub}(H, \cdot)$ and $\text{ind}(H, \cdot)$, graph motif parameters include the graph parameters $\text{ind}(\Phi, \cdot)$ that count induced $k$-vertex subgraphs with a fixed property $\Phi$, and generally, every graph parameter that depends only on the numbers of constant-sized subgraphs.

**► Definition 1.** A *graph motif parameter* is any graph parameter $f$ that can be written as

$$f(\cdot) = \sum_{F \in \mathcal{F}} \alpha_F \cdot \text{ind}(F, \cdot) \qquad (2)$$
## Hardness results

We want to understand the optimal complexity exponents of graph parameters that count small patterns. Parameterized complexity allows us to aggregate graph parameters into classes $\mathcal{H}$ and prove statements on the asymptotic behaviour of the complexity exponents: Given a graph class $\mathcal{H}$, we define the problem $\text{sub}(\mathcal{H}, \cdot)$, where the task is to compute $\text{sub}(H, G)$ on input a pattern graph $H \in \mathcal{H}$ and an arbitrary host graph $G$. An analogous definition gives the problems $\text{ind}(\mathcal{H}, \cdot)$ and $\text{hom}(\mathcal{H}, \cdot)$.

If a problem $\text{sub}(\mathcal{H}, \cdot)$ is FPT or even polynomial-time solvable, then there is a fixed constant $C$ that bounds all complexity exponents of $\text{sub}(H, \cdot)$ for $H \in \mathcal{H}$. If $\text{sub}(\mathcal{H}, \cdot)$ is \#W[1]-hard, then we believe that no such constant exists. Furthermore, conditional lower bounds under \#ETH enable lower bounds on the asymptotic growth of complexity exponents. Indeed, such lower bounds are known for counting subgraphs, induced subgraphs, and homomorphisms for restricted pattern classes $\mathcal{H}$ that are recursively enumerable.

- If $\mathcal{H}$ is finite, then $\text{ind}(\mathcal{H}, \cdot)$ is polynomial-time solvable, otherwise it is \#W[1]-hard [25]. Furthermore, if $\mathcal{H}$ is infinite, then there is no $f(k) \cdot n^{o(k)}$ time algorithm for $\text{ind}(\mathcal{H}, \cdot)$ unless ETH fails. Note that this result holds for every fixed recursively enumerable class $\mathcal{H}$; it shows that no pattern structure whatsoever can be exploited for counting induced subgraphs. Jerrum and Meeks generalized this result and proved that counting $k$-vertex subgraphs with fixed properties $\Phi$ is \#W[1]-hard for certain well-behaved properties $\Phi$ like connectedness or having even/odd number of edges [61, 62, 63].

- For counting not necessarily induced subgraphs, we have seen above that pattern structure can be exploited: If the maximum vertex-cover number of graphs in $\mathcal{H}$ is finite, then $\text{sub}(\mathcal{H}, \cdot)$ is polynomial-time solvable. Otherwise the problem is known to be \#W[1]-hard [33]. We will see in the next section that an $f(k) \cdot n^{o(\text{vc}(H)/\log \text{vc}(H))}$ time algorithm would refute \#ETH, even for patterns from fixed classes $\mathcal{H}$.

- For counting homomorphisms, we may even allow bounded-treewidth patterns: If the treewidth of $\mathcal{H}$ is finite, then $\text{hom}(\mathcal{H}, \cdot)$ is polynomial-time solvable; otherwise the problem is \#W[1]-hard [39]. As a consequence of Marx's cornerstone "Can you beat treewidth" paper, \#ETH rules out an $f(k) \cdot n^{o(\text{tw}(H)/\log \text{tw}(H))}$ time algorithm [76].

## 2.2 Graph motif parameters

Despite the similar appearance of the problems $\text{ind}(\mathcal{H}, \cdot)$, $\text{sub}(\mathcal{H}, \cdot)$, and $\text{hom}(\mathcal{H}, \cdot)$, their dichotomy theorems were each proven about five years apart, by different people, using somewhat different techniques. Recently, it was shown that these problems can be studied in a uniform way: From the perspective of parameterized complexity, these problems become the same problem when "extended linearly".

More formally, graph parameters like $\text{sub}(H, \cdot)$ or $\text{ind}(H, \cdot)$ for fixed $H$ are special cases of so-called *graph motif parameters*, a notion introduced in [30] that adapts early works by Lovász [71, 73] to study counting small patterns from a parameterized perspective. Apart from $\text{sub}(H, \cdot)$ and $\text{ind}(H, \cdot)$, graph motif parameters include the graph parameters $\text{ind}(\Phi, \cdot)$ that count induced $k$-vertex subgraphs with a fixed property $\Phi$, and generally, every graph parameter that depends only on the numbers of constant-sized subgraphs.

**► Definition 1.** A *graph motif parameter* is any graph parameter $f$ that can be written as

$$f(\cdot) = \sum_{F \in \mathcal{F}} \alpha_F \cdot \text{ind}(F, \cdot) \qquad (2)$$
## 1:8 Counting Problems in Parameterized Complexity

for a finite set of graphs $\mathcal{F}$ and coefficients $\alpha_F$ for $F \in \mathcal{F}$. In other words, $f$ is a (point-wise) linear combination of a finite set of functions ind($F$, $\cdot$) for fixed patterns $F$. Recall that the function ind($F$, $\cdot$) takes as input a graph $G$ and outputs ind($F$, $G$).

The graph motif parameter evaluation problem asks to evaluate $f(G)$ when given as input a graph $G$ and a representation of $f$ via $\mathcal{F} = \{F_1, \dots, F_t\}$ and coefficients $\alpha_1, \dots, \alpha_t$. We parameterize the problem by the description length of $f$.

Note that the functions ind($H$, $\cdot$) for fixed $H$ are graph motif parameters themselves, but using linear combinations of such functions allows us to express much more counting functions as graph motif parameters. As an example, for any $H$, we have

$$ \mathrm{sub}(H, \cdot) = \sum_{F \text{ extends } H} \beta_F \cdot \mathrm{ind}(F, \cdot), \qquad (3) $$

where an unlabeled graph $F$ extends $H$ if $F$ is a supergraph of $H$ on $|V(H)|$ vertices, and the coefficient $\beta_F$ equals sub($F$, $H$). Since only finitely many graphs $F$ occur in (3), the graph parameter sub($H$, $\cdot$) for fixed $H$ is a graph motif parameter. Moreover, the graphs and coefficients can be computed in time depending only on $H$. It follows that the problem of computing sub($H$, $G$) on input $H$ and $G$, parameterized by $H$, admits a parameterized reduction to the graph motif evaluation problem.

Interestingly, (3) admits a converse form that expresses the number of induced subgraphs ind($H$, $\cdot$) as a finite linear combination of subgraph counts sub($F$, $\cdot$), see [73, (5.17)]. Thus, subgraph counts are finite linear combinations of induced subgraph counts, and vice versa. We could thus replace ind with sub in Definition 1 and still end up defining the same objects: Any graph motif parameter $f = \sum_{F \in \mathcal{F}} \alpha_F \cdot \mathrm{ind}(F, \cdot)$ can also be written as

$$ f(\cdot) = \sum_{F \in \mathcal{F}'} \beta_F \cdot \mathrm{sub}(F, \cdot). \qquad (4) $$

for a finite set of graphs $\mathcal{F}'$ and coefficients $\beta_F$ for $F \in \mathcal{F}'$ that can be computed from $\mathcal{F}$ and the coefficients $\alpha_F$ for $F \in \mathcal{F}$. We call (4) the sub-expansion of $f$ and (2) its ind-expansion.<fnref n="2" />

### Homomorphism counts count

There are actually many equivalent ways of expanding graph motif parameters into finite linear combinations of basis functions, with explicit formulas for changing bases between such expansions [73, Chapter 5.2]. As it turns out, such basis changes enable a much better understanding of the complexity of graph motif parameters. In particular, expanding graph motif parameters into linear combinations of the previously neglected homomorphism counts will prove to be extremely useful for algorithmic purposes.

Let us have a more detailed look at the relation between embeddings<fnref n="3" /> and homomorphisms: We can easily express the number of homomorphisms $\mathrm{hom}(H, \cdot)$ as a finite linear combination of embeddings $\mathrm{emb}(F, \cdot)$. A graph $F$ is a quotient of $H$ if $F$ can be obtained from $H$ by repeated identifications of vertex pairs. These identifications can be performed all at once: If $\pi$ is a partition of $V(H)$, then the quotient $H/\pi$ is obtained from $H$ by identifying, for each

<footnote n="2">² We could have chosen to call the parameterized counting problem from Definition 1 the “evaluation problem for graph motif parameters in the ind-expansion” and could have defined an analogous version for the sub-expansion, but the fact that the sub-expansion and the ind-expansion can be transformed into each other algorithmically implies that these problems are FPT-interreducible.</footnote>

<footnote n="3">³ Recall that an embedding is an injective homomorphism, and that $\mathrm{emb}(H, \cdot) = \mathrm{aut}(H) \cdot \mathrm{sub}(H, \cdot)$.</footnote>
1:8 Counting Problems in Parameterized Complexity

for a finite set of graphs $\mathcal{F}$ and coefficients $\alpha_F$ for $F \in \mathcal{F}$. In other words, $f$ is a (point-wise) linear combination of a finite set of functions ind($F$, $\cdot$) for fixed patterns $F$. Recall that the function ind($F$, $\cdot$) takes as input a graph $G$ and outputs ind($F$, $G$).

The graph motif parameter evaluation problem asks to evaluate $f(G)$ when given as input a graph $G$ and a representation of $f$ via $\mathcal{F} = \{F_1, \dots, F_t\}$ and coefficients $\alpha_1, \dots, \alpha_t$. We parameterize the problem by the description length of $f$.

Note that the functions ind($H$, $\cdot$) for fixed $H$ are graph motif parameters themselves, but using linear combinations of such functions allows us to express much more counting functions as graph motif parameters. As an example, for any $H$, we have

$$ \mathrm{sub}(H, \cdot) = \sum_{F \text{ extends } H} \beta_F \cdot \mathrm{ind}(F, \cdot), \qquad (3) $$

where an unlabeled graph $F$ extends $H$ if $F$ is a supergraph of $H$ on $|V(H)|$ vertices, and the coefficient $\beta_F$ equals $\mathrm{sub}(F, H)$. Since only finitely many graphs $F$ occur in (3), the graph parameter $\mathrm{sub}(H, \cdot)$ for fixed $H$ is a graph motif parameter. Moreover, the graphs and coefficients can be computed in time depending only on $H$. It follows that the problem of computing $\mathrm{sub}(H, G)$ on input $H$ and $G$, parameterized by $H$, admits a parameterized reduction to the graph motif evaluation problem.

Interestingly, (3) admits a converse form that expresses the number of induced subgraphs ind($H$, $\cdot$) as a finite linear combination of subgraph counts $\mathrm{sub}(F, \cdot)$, see [73, (5.17)]. Thus, subgraph counts are finite linear combinations of induced subgraph counts, and vice versa. We could thus replace ind with sub in Definition 1 and still end up defining the same objects: Any graph motif parameter $f = \sum_{F \in \mathcal{F}} \alpha_F \cdot \mathrm{ind}(F, \cdot)$ can also be written as

$$ f(\cdot) = \sum_{F \in \mathcal{F}'} \beta_F \cdot \mathrm{sub}(F, \cdot). \qquad (4) $$

for a finite set of graphs $\mathcal{F}'$ and coefficients $\beta_F$ for $F \in \mathcal{F}'$ that can be computed from $\mathcal{F}$ and the coefficients $\alpha_F$ for $F \in \mathcal{F}$. We call (4) the *sub-expansion* of $f$ and (2) its *ind-expansion*.<fnref n="2" />

## Homomorphism counts count

There are actually many equivalent ways of expanding graph motif parameters into finite linear combinations of basis functions, with explicit formulas for changing bases between such expansions [73, Chapter 5.2]. As it turns out, such basis changes enable a much better understanding of the *complexity* of graph motif parameters. In particular, expanding graph motif parameters into linear combinations of the previously neglected *homomorphism* counts will prove to be extremely useful for algorithmic purposes.

Let us have a more detailed look at the relation between embeddings<fnref n="3" /> and homomorphisms: We can easily express the number of homomorphisms $\mathrm{hom}(H, \cdot)$ as a finite linear combination of embeddings $\mathrm{emb}(F, \cdot)$. A graph $F$ is a *quotient* of $H$ if $F$ can be obtained from $H$ by repeated identifications of vertex pairs. These identifications can be performed all at once: If $\pi$ is a partition of $V(H)$, then the quotient $H/\pi$ is obtained from $H$ by identifying, for each

<footnote n="2">² We could have chosen to call the parameterized counting problem from Definition 1 the “evaluation problem for graph motif parameters in the ind-expansion” and could have defined an analogous version for the sub-expansion, but the fact that the sub-expansion and the ind-expansion can be transformed into each other algorithmically implies that these problems are FPT-interreducible.</footnote>

<footnote n="3">³ Recall that an embedding is an injective homomorphism, and that $\mathrm{emb}(H, \cdot) = \mathrm{aut}(H) \cdot \mathrm{sub}(H, \cdot)$.</footnote>
block $B$ of $\pi$, the vertices in $B$ to a single vertex. Quotients of graphs $H$ correspond to the images that $H$ can attain under homomorphisms, and we obtain

$$ \operatorname{hom}(H, \cdot) = \sum_{\pi} \operatorname{emb}(H/\pi, \cdot), \qquad (5) $$

where $\pi$ ranges over all partitions of $V(H)$. Different partitions can yield isomorphic quotients, and after collecting for isomorphic copies in (5) and rewriting $\operatorname{emb} = \operatorname{aut} \cdot \operatorname{sub}$, we obtain a formula for the sub-expansion of $\operatorname{hom}(H, \cdot)$.

More interestingly, as shown in [73, (5.18)], the formula (5) can be inverted<fnref n="4" /> to read

$$ \operatorname{emb}(H, \cdot) = \sum_{\pi} (-1)^{k-|\pi|} \prod_{B \in \pi} (|B| - 1)! \cdot \operatorname{hom}(H/\pi, \cdot), \qquad (6) $$

where we write $|\pi|$ for the number of blocks in $\pi$. The precise form of (6) and $\mu(\pi)$ will become important later on, but for now let us just use it to conclude that every graph motif parameter $f$ can be expressed as a linear combination of homomorphism counts

$$ f(\cdot) = \sum_{F \in \mathcal{F}''} \gamma_F \cdot \operatorname{hom}(F, \cdot) \qquad (7) $$

for a finite set of graphs $\mathcal{F}''$ and coefficients $\gamma_F$ for $F \in \mathcal{F}''$. We call (7) the hom-expansion of $f$. This works because every graph motif parameter has a sub-expansion via (4), and because subgraph counts are rescaled embedding counts, which in turn are linear combinations of homomorphism counts by (6).

## Complexity monotonicity of the hom-expansion

Lovász showed that homomorphism counts enjoy a wealth of mathematical properties that make them more well-behaved than subgraph or induced subgraph counts [73], and some of these properties translate almost directly into complexity-theoretic properties. Most importantly for us, the hom-expansion of graph motif parameters enjoys a monotonicity property with respect to complexity exponents: Any linear combination of homomorphism counts, as in (7), is unconditionally at least as hard to evaluate as its hardest terms.

**Theorem 2** ([30, 22]). Let $f$ be a graph motif parameter with $f = \sum_{F \in \mathcal{F}} \alpha_F \cdot \operatorname{hom}(F, \cdot)$ for a finite set of pairwise non-isomorphic graphs $\mathcal{F}$ with $\alpha_F \neq 0$ for all $F \in \mathcal{F}$. Then the complexity exponent of $f$ is exactly the maximum over all complexity exponents of the functions $\operatorname{hom}(F, \cdot)$ for $F \in \mathcal{F}$.

**Remark.** A result similar to Theorem 2 cannot be obtained for the sub-expansion or the ind-expansion. In these cases, we can “hide” cliques in easy linear combinations: For any $k \in \mathbb{N}$, summing over the induced subgraph counts from all $k$-vertex graphs $H$ gives $\sum_H \operatorname{ind}(H, G) = (|V(G)|)$, which can be evaluated in linear time for any graph $G$, even though the left-hand side contains a $k$-clique. Theorem 2 rules this out for homomorphisms. Via Theorem 2, we obtain a good grip on the complexity of a graph motif parameter $f$ if we manage to understand (i) what patterns $F$ occur in the hom-expansion of $f$, and (ii) how hard counting homomorphisms $\operatorname{hom}(F, \cdot)$ is for these patterns. For the first item, we can use enumerative combinatorics to obtain formulas like (6). For the second item, we can use the known lower bounds under ETH for cliques [23] or patterns of large treewidth [76].

<footnote n="4">⁴ This is done via Möbius inversion on the partition lattice, a generalization of the inclusion-exclusion principle, which can be viewed as Möbius inversion on the subset lattice [88].</footnote>
block $B$ of $\pi$, the vertices in $B$ to a single vertex. Quotients of graphs $H$ correspond to the images that $H$ can attain under homomorphisms, and we obtain

$$ \operatorname{hom}(H, \cdot) = \sum_{\pi} \operatorname{emb}(H/\pi, \cdot), \qquad (5) $$

where $\pi$ ranges over all partitions of $V(H)$. Different partitions can yield isomorphic quotients, and after collecting for isomorphic copies in (5) and rewriting $\operatorname{emb} = \operatorname{aut} \cdot \operatorname{sub}$, we obtain a formula for the sub-expansion of $\operatorname{hom}(H, \cdot)$.

More interestingly, as shown in [73, (5.18)], the formula (5) can be inverted<fnref n="4" /> to read

$$ \operatorname{emb}(H, \cdot) = \sum_{\pi} (-1)^{k-|\pi|} \prod_{B \in \pi} (|B| - 1)! \cdot \operatorname{hom}(H/\pi, \cdot), \qquad (6) $$

where we write $|\pi|$ for the number of blocks in $\pi$. The precise form of (6) and $\mu(\pi)$ will become important later on, but for now let us just use it to conclude that every graph motif parameter $f$ can be expressed as a linear combination of homomorphism counts

$$ f(\cdot) = \sum_{F \in \mathcal{F}''} \gamma_F \cdot \operatorname{hom}(F, \cdot) \qquad (7) $$

for a finite set of graphs $\mathcal{F}''$ and coefficients $\gamma_F$ for $F \in \mathcal{F}''$. We call (7) the hom-expansion of $f$. This works because every graph motif parameter has a sub-expansion via (4), and because subgraph counts are rescaled embedding counts, which in turn are linear combinations of homomorphism counts by (6).

## Complexity monotonicity of the hom-expansion

Lovász showed that homomorphism counts enjoy a wealth of mathematical properties that make them more well-behaved than subgraph or induced subgraph counts [73], and some of these properties translate almost directly into complexity-theoretic properties. Most importantly for us, the hom-expansion of graph motif parameters enjoys a monotonicity property with respect to complexity exponents: Any linear combination of homomorphism counts, as in (7), is unconditionally at least as hard to evaluate as its hardest terms.

**Theorem 2** ([30, 22]). Let $f$ be a graph motif parameter with $f = \sum_{F \in \mathcal{F}} \alpha_F \cdot \operatorname{hom}(F, \cdot)$ for a finite set of pairwise non-isomorphic graphs $\mathcal{F}$ with $\alpha_F \neq 0$ for all $F \in \mathcal{F}$. Then the complexity exponent of $f$ is exactly the maximum over all complexity exponents of the functions $\operatorname{hom}(F, \cdot)$ for $F \in \mathcal{F}$.

**Remark.** A result similar to Theorem 2 cannot be obtained for the sub-expansion or the ind-expansion. In these cases, we can “hide” cliques in easy linear combinations: For any $k \in \mathbb{N}$, summing over the induced subgraph counts from all $k$-vertex graphs $H$ gives $\sum_H \operatorname{ind}(H, G) = (|V(G)|)$, which can be evaluated in linear time for any graph $G$, even though the left-hand side contains a $k$-clique. Theorem 2 rules this out for homomorphisms. Via Theorem 2, we obtain a good grip on the complexity of a graph motif parameter $f$ if we manage to understand (i) what patterns $F$ occur in the hom-expansion of $f$, and (ii) how hard counting homomorphisms $\operatorname{hom}(F, \cdot)$ is for these patterns. For the first item, we can use enumerative combinatorics to obtain formulas like (6). For the second item, we can use the known lower bounds under ETH for cliques [23] or patterns of large treewidth [76].

<footnote n="4">⁴ This is done via Möbius inversion on the partition lattice, a generalization of the inclusion-exclusion principle, which can be viewed as Möbius inversion on the subset lattice [88].</footnote>
1:10 Counting Problems in Parameterized Complexity

Understanding subgraph counting via homomorphisms

In the following, we use the two-step approach to give upper and lower bounds on the
complexity of counting subgraphs sub(H, ·) for fixed H. Let us start with an upper bound.

**Theorem 3 ([30]).** On input *H* and *G*, the number sub(*H*,*G*) can be determined in time
$k^{O(k)} \cdot n^{0{.}174\ell+O(1)}$ with $\ell = |E(*H*)|$.

**Proof.** Consider the formula (6) for transforming embedding counts into homomorphism counts. The right-hand side sums over all partitions $\pi$ of $V(H)$, of which there are at most $k^{O(k)}$, and requires homomorphism numbers from quotients $H/\pi$ into $G$. Any quotient $H/\pi$ has at most $\ell$ edges, and the treewidth of $\ell$-edge graphs $F$ is known to be at most $\text{tw}(F) \le 0.174\ell + o(\ell)$ [87]. By a standard DP approach, we can determine $\text{hom}(H/\pi, G)$ in time $2^{O(k)} \cdot n^{0.174\ell+O(1)}$ for every fixed $\pi$, and the overall running time bound follows. ◀

It is not much harder to prove hardness results for subgraph counting via Theorem 2:

**Theorem 4.** For any fixed recursively enumerable class $\mathcal{H}$, the problem sub($\mathcal{H}$, ·) cannot be solved in time $f(k) \cdot n^{o(\text{vc}(\mathcal{H})/\log \text{vc}(\mathcal{H}))}$ for patterns $H \in \mathcal{H}$ unless ETH fails.

**Proof.** Consider $\text{sub}(H, \cdot)$ for $H \in \mathcal{H}$. If $H$ has vertex-cover number $b \in \mathbb{N}$, then $H$ contains a matching $M$ with $t = b/2$ edges. We show that for every $t$-edge graph $S$, the hom-expansion of $\text{sub}(H, \cdot)$ contains a supergraph of $S$ with non-zero coefficient. In particular, this holds for bounded-degree expanders $S$ of treewidth $\Omega(t)$. Supergraphs have only larger treewidth.

Every $t$-edge graph $S$ is some quotient of the $t$-matching $M$ in $H$. It follows that some supergraph of $S$ is a quotient of $H$. Using (6), we can see that every quotient $H/\pi$ appears with non-zero coefficient in the hom-expansion of $\text{sub}(H, \cdot)$ even after collecting for isomorphic graphs: While different partitions $\pi, \pi'$ may lead to isomorphic quotients, this requires $|\pi| = |\pi'|$. But since the sign of $\mu(\pi)$ in (6) depends only on $|\pi|$, the contributions of $\pi$ and $\pi'$ cannot cancel. ◀

The hom-expansion of graph motif parameters is a fascinating object of study on its own that
connects various mathematical areas: After the results for subgraph counting, Theorem 2
was used by Roth [85] to classify the complexity of counting homomorphism variants such as
locally injective homomorphisms. This was obtained by finding large-treewidth patterns in the
relevant hom-expansions through matroid theory. Very recently, an almost exhaustive #W[1]-
hardness proof for counting induced k-vertex subgraphs with a fixed monotone property Φ
was given by Roth and Schmitt [86] by using topological properties of abstract simplicial
complexes. In unpublished work by the author, connections to finite model theory and
chromatic polynomials were also uncovered.

3 Counting large patterns in “simple” graphs

In this last and shorter part of the survey, we count large objects in graphs of simple structure:
In Section 3.1, we attempt to count perfect matchings in graphs that exclude fixed minors,
and in Section 3.2, we count Hamiltonian cycles in graphs of bounded pathwidth.

**3.1 Counting perfect matchings in minor-free graphs**

Counting perfect matchings was the first problem shown to be #P-hard for interesting reasons, and it admits a beautiful polynomial-time algorithm on planar graphs, the *Fisher-Kasteleyn-Temperley (FKT) method* [90, 65, 66], which we already mentioned earlier. Other
1:10 Counting Problems in Parameterized Complexity

Understanding subgraph counting via homomorphisms

In the following, we use the two-step approach to give upper and lower bounds on the
complexity of counting subgraphs sub(H, ·) for fixed H. Let us start with an upper bound.

**Theorem 3 ([30]).** On input *H* and *G*, the number sub(*H*,*G*) can be determined in time
$k^{O(k)} \cdot n^{0{.}174\ell+O(1)}$ with $\ell = |E(*H*)|$.

**Proof.** Consider the formula (6) for transforming embedding counts into homomorphism counts. The right-hand side sums over all partitions $\pi$ of $V(H)$, of which there are at most $k^{O(k)}$, and requires homomorphism numbers from quotients $H/\pi$ into $G$. Any quotient $H/\pi$ has at most $\ell$ edges, and the treewidth of $\ell$-edge graphs $F$ is known to be at most $\text{tw}(F) \le 0.174\ell + o(\ell)$ [87]. By a standard DP approach, we can determine $\text{hom}(H/\pi, G)$ in time $2^{O(k)} \cdot n^{0.174\ell+O(1)}$ for every fixed $\pi$, and the overall running time bound follows. ◀

It is not much harder to prove hardness results for subgraph counting via Theorem 2:

**Theorem 4.** For any fixed recursively enumerable class $\mathcal{H}$, the problem sub($\mathcal{H}$, ·) cannot be solved in time $f(k) \cdot n^{o(\text{vc}(H)/\log \text{vc}(H))}$ for patterns $H \in \mathcal{H}$ unless ETH fails.

**Proof.** Consider sub(*H*, ·) for *H* ∈ *H*. If *H* has vertex-cover number *b* ∈ N, then *H* contains a matching *M* with *t* = *b*/2 edges. We show that for every *t*-edge graph *S*, the hom-expansion of sub(*H*, ·) contains a supergraph of *S* with non-zero coefficient. In particular, this holds for bounded-degree expanders *S* of treewidth Ω(*t*). Supergraphs have only larger treewidth.

Every *t*-edge graph *S* is some quotient of the *t*-matching *M* in *H*. It follows that some supergraph of *S* is a quotient of *H*. Using (6), we can see that every quotient *H*/π appears with non-zero coefficient in the hom-expansion of sub(*H*, ·) even after collecting for isomorphic graphs: While different partitions π, π' may lead to isomorphic quotients, this requires |π| = |π'|. But since the sign of μ(π) in (6) depends only on |π|, the contributions of π and π' cannot cancel. ◀

The hom-expansion of graph motif parameters is a fascinating object of study on its own that
connects various mathematical areas: After the results for subgraph counting, Theorem 2
was used by Roth [85] to classify the complexity of counting homomorphism variants such as
locally injective homomorphisms. This was obtained by finding large-treewidth patterns in the
relevant hom-expansions through matroid theory. Very recently, an almost exhaustive #W[1]-
hardness proof for counting induced k-vertex subgraphs with a fixed monotone property Φ
was given by Roth and Schmitt [86] by using topological properties of abstract simplicial
complexes. In unpublished work by the author, connections to finite model theory and
chromatic polynomials were also uncovered.

3 Counting large patterns in “simple” graphs

In this last and shorter part of the survey, we count large objects in graphs of simple structure:
In Section 3.1, we attempt to count perfect matchings in graphs that exclude fixed minors,
and in Section 3.2, we count Hamiltonian cycles in graphs of bounded pathwidth.

**3.1 Counting perfect matchings in minor-free graphs**

Counting perfect matchings was the first problem shown to be #P-hard for interesting reasons, and it admits a beautiful polynomial-time algorithm on planar graphs, the *Fisher-Kasteleyn-Temperley (FKT) method* [90, 65, 66], which we already mentioned earlier. Other
than planar graphs, there are further tractable graph classes $\mathcal{C}$: For instance, while planar graphs exclude both $K_{3,3}$ and $K_5$ as minors, it was shown that excluding *either* of these two minors is sufficient [70, 96, 89]. The FKT method was also extended to an FPT-algorithm with running time $4^\gamma n^{O(1)}$ for graphs that are embedded on a surface of genus $\gamma$ [53]; together with an FPT-algorithm for finding such embeddings [80], this shows that counting perfect matchings is FPT when parameterized by genus. Furthermore, dynamic programming with subset convolution yields an $O(2^{\mathit{tw}(G)}n)$ time algorithm when $G$ is given with an optimal tree-decomposition [95]. It is also possible to count perfect matchings in time $O(n^{\mathit{cw}(G)+1})$ on graphs of clique-width $\mathit{cw}(G)$ given with an optimal parse-tree, but unlike the previous results, this holds only for unweighted graphs [75].

The above list shows that, apart from clique-width, all tractability results for counting perfect matchings address graphs that exclude some fixed minor. In fact, the algorithms for $K_{3,3}$-free and $K_5$-free graphs make use of classical precursors to Robertson and Seymour's graph structure theorem for $H$-minor free graphs [84]: By Wagner's theorem [43], the $K_{3,3}$-free and $K_5$-free graphs admit tree-decompositions of adhesion 3 in which every torso is planar or has bounded size. Prior to proving the full graph structure theorem, Robertson and Seymour showed very similar decompositions for all graphs excluding minors $H$ that can be drawn in the plane with at most one crossing [83], such as $H = K_{3,3}$ and $H = K_5$. Such decompositions can be used algorithmically:

**Theorem 5** ([28, 89]). For any fixed graph $H$ that can be drawn in the plane with at most one crossing, there is an $O(n^4)$ time algorithm for counting perfect matchings in $H$-minor free graphs $G$.

**Proof.** For single-crossing minors $H$, a tree-decomposition of $H$-free graphs $G$ into planar and bounded-treewidth torsos of adhesion 3 can be obtained in $O(f(H) \cdot n^4)$ time [41]. Given such a decomposition, the algorithm now uses a counting version of protrusion replacement [12]: When counting perfect matchings, any 3-boundaried graph $S$ can be simulated by an equivalent planar 3-boundaried graph $S'$ with edge-weights [94], and the graph $S'$ can be computed in FPT-time for planar and bounded-treewidth graphs $S$. Traversing the decomposition of $G$ bottom-up, we can successively replace torsos $S$ by planar replacement graphs $S'$ until all of $G$ is processed. ◀

How far can we push this result? In particular, is it possible to obtain polynomial-time algorithms for counting perfect matchings for any graph class that excludes some fixed graph $H$? More strongly, is the problem FPT when parameterized by the *Hadwiger number*, which is the maximum size of a clique minor in $G$? The answer to the second question is negative, as we can show \#W[1]-hardness on $k$-apex graphs. These are the graphs that become planar after deleting at most $k$ vertices; this upper-bounds their *Hadwiger number* by $k+5$.

**Theorem 6** ([35]). Counting perfect matchings in $k$-apex graphs is \#W[1]-hard and an $f(k)n^{o(k/\log k)}$ time algorithm would refute \#ETH.

Thus, counting perfect matchings is also \#W[1]-hard when parameterized by the *Hadwiger number*. However, an *XP*-algorithm might still be possible, e.g., because there is a simple $O(n^{k+3})$ time algorithm for counting perfect matchings in $k$-apex graphs: Simply iterate over all $n^k$ possible choices for matching the $k$ apices to vertices in the planar base graph, delete the apices together with their matching partners, and count perfect matchings in the remaining *planar* graph via the FKT method.

To recapitulate, we know that counting perfect matchings is FPT parameterized by genus, in *XP* parameterized by *apex number*, and we have seen some techniques for dealing
than planar graphs, there are further tractable graph classes $\mathcal{C}$: For instance, while planar graphs exclude both $K_{3,3}$ and $K_5$ as minors, it was shown that excluding *either* of these two minors is sufficient [70, 96, 89]. The FKT method was also extended to an FPT-algorithm with running time $4^\gamma n^{O(1)}$ for graphs that are embedded on a surface of genus $\gamma$ [53]; together with an FPT-algorithm for finding such embeddings [80], this shows that counting perfect matchings is FPT when parameterized by genus. Furthermore, dynamic programming with subset convolution yields an $O(2^{\text{tw}(G)}n)$ time algorithm when $G$ is given with an optimal tree-decomposition [95]. It is also possible to count perfect matchings in time $O(n^{\text{cw}(G)+1})$ on graphs of clique-width $\text{cw}(G)$ given with an optimal parse-tree, but unlike the previous results, this holds only for unweighted graphs [75].

The above list shows that, apart from clique-width, all tractability results for counting perfect matchings address graphs that exclude some fixed minor. In fact, the algorithms for $K_{3,3}$-free and $K_5$-free graphs make use of classical precursors to Robertson and Seymour's graph structure theorem for $H$-minor free graphs [84]: By Wagner's theorem [43], the $K_{3,3}$-free and $K_5$-free graphs admit tree-decompositions of adhesion 3 in which every torso is planar or has bounded size. Prior to proving the full graph structure theorem, Robertson and Seymour showed very similar decompositions for all graphs excluding minors $H$ that can be drawn in the plane with at most one crossing [83], such as $H = K_{3,3}$ and $H = K_5$. Such decompositions can be used algorithmically:

**Theorem 5** ([28, 89]). For any fixed graph $H$ that can be drawn in the plane with at most one crossing, there is an $O(n^4)$ time algorithm for counting perfect matchings in $H$-minor free graphs $G$.

**Proof.** For single-crossing minors $H$, a tree-decomposition of $H$-free graphs $G$ into planar and bounded-treewidth torsos of adhesion 3 can be obtained in $O(f(H) \cdot n^4)$ time [41]. Given such a decomposition, the algorithm now uses a counting version of protrusion replacement [12]: When counting perfect matchings, any 3-boundaried graph $S$ can be simulated by an equivalent planar 3-boundaried graph $S'$ with edge-weights [94], and the graph $S'$ can be computed in FPT-time for planar and bounded-treewidth graphs $S$. Traversing the decomposition of $G$ bottom-up, we can successively replace torsos $S$ by planar replacement graphs $S'$ until all of $G$ is processed. ◀

How far can we push this result? In particular, is it possible to obtain polynomial-time algorithms for counting perfect matchings for *any* graph class that excludes some fixed graph $H$? More strongly, is the problem FPT when parameterized by the *Hadwiger number*, which is the maximum size of a clique minor in $G$? The answer to the second question is negative, as we can show \#W[1]-hardness on $k$-apex graphs. These are the graphs that become planar after deleting at most $k$ vertices; this upper-bounds their Hadwiger number by $k+5$.

**Theorem 6** ([35]). Counting perfect matchings in $k$-apex graphs is \#W[1]-hard and an $f(k)n^{o(k/\log k)}$ time algorithm would refute \#ETH.

Thus, counting perfect matchings is also \#W[1]-hard when parameterized by the Hadwiger number. However, an $X$-algorithm might still be possible, e.g., because there is a simple $O(n^{k+3})$ time algorithm for counting perfect matchings in $k$-apex graphs: Simply iterate over all $n^k$ possible choices for matching the $k$ apices to vertices in the planar base graph, delete the apices together with their matching partners, and count perfect matchings in the remaining *planar* graph via the FKT method.

To recapitulate, we know that counting perfect matchings is FPT parameterized by genus, in $X$ parameterized by apex number, and we have seen some techniques for dealing
1:12 Counting Problems in Parameterized Complexity

with clique-sums in Theorem 5. By the graph structure theorem [84], these are almost all
the building blocks of $H$-minor free graphs, and thus an XP algorithm for counting perfect
matchings on such graphs almost seems within reach.

Alas, we blocked out *vortices*: In general, *H*-minor free graphs allow for graphs of bounded pathwidth to be inserted at the faces of the bounded-genus parts; these structures are called vortices. It turns out that counting perfect matchings is *#P*-hard even in planar graphs with one single vortex, and such graphs can be seen to exclude a constant-sized minor.

**► Theorem 7** (Unpublished work by the author with Mingji Xia). *There is a fixed graph H such that counting perfect matchings is #P-hard in graphs excluding H.*

Thus, polynomial-time algorithms cannot be obtained for each excluded minor $H$, but it is
still open to find out which fixed graphs $H$ can be excluded for polynomial-time algorithms.

## 3.2 Counting Hamiltonian cycles in low-pathwidth graphs

To conclude, we briefly consider counting Hamiltonian cycles parameterized by pathwidth. The standard DP for this problem gives a running time of $O^*(\mathbf{pw}^{O(\mathbf{pw})})$ for counting and decision, but celebrated improvements [37] enabled $O^*((2 + \sqrt{2})^{\mathbf{pw}})$ time for the decision problem and for counting modulo 2, and $O^*(6^{\mathbf{pw}})$ time for counting [11]. The bases $2 + \sqrt{2}$ and 6 are optimal under the strong exponential-time hypothesis SETH [37, 32].

Curiously, the concrete numbers $2 + \sqrt{2}$ and 6 can be explained through *connection matrices*. These are particularly nice objects in the intersection of linear algebra and combinatorics [72, 73]. Given a graph parameter $f$ such as the number of Hamiltonian cycles, and $k \in \mathbb{N}$, the $k$-th connection matrix of $f$ is an infinite matrix $C_{f,k}$, indexed by $k$-boundedaried graphs, that describes the behavior of $f$ under graph separations of size $k$. The entry $C_{f,k}(G, H)$ for $k$-boundedaried graphs $G, H$ is defined to be $f(G \oplus H)$, where $G \oplus H$ is the union of $k$-boundedaried graphs $G$ and $H$ with matching vertices identified. Even though the matrices $C_{f,k}$ are infinite-sized, they have finite rank for many interesting graph parameters $f$, including all MSOL-definable $f$ [68]. It can be shown furthermore that evaluating graph parameters $f$ with finite-rank connection matrices is nonuniformly FPT when parameterized by treewidth [73]; this gives an alternative proof of Courcelle's theorem.

Let us focus again on the connection matrix $C_{\text{HC},k}$ for the number of Hamiltonian cycles: Lovász [72] upper-bounded the rank of $C_{\text{HC},k}$ over $\mathbb{Q}$ by $k^{O(k)}$. This bound was recently improved to $\Theta(6^k)$ up to polynomial factors, with a matching lower bound [32]. It was also known before that the rank of $C_{\text{HC},k}$ drops to $\Theta((2+\sqrt{2})^k)$ over the ring $\mathbb{Z}_2$ with a matching lower bound [37]. Note that the constants 6 and $2+\sqrt{2}$ appearing in the rank of $C_{\text{HC},k}$ over $\mathbb{Q}$ and $\mathbb{Z}_2$ are the running time bases for counting Hamiltonian cycles over these rings parameterized by pathwidth. This is a consequence of a more general statement:

**► Theorem 8 ([32]).** Let $\mathbb{R}$ be any of the rings $\mathbb{Q}$ or $\mathbb{Z}_p$ for prime $p$. If the connection matrix $C_{\text{HC},k}$ of the number of Hamiltonian cycles has rank $\Omega(c^k)$ over $\mathbb{R}$, then an algorithm with running time $O^*((c - \epsilon)^{\mathbf{pw}})$ for counting Hamiltonian cycles over $\mathbb{R}$ refutes SETH.

While we do know that the rank of $C_{\text{HC},k}$ is $\Omega(3.97^k)$ over $\mathbb{Z}_p$ when $p \neq 2$, resulting in a
corresponding complexity lower bound [32], algorithms faster than $O^*(6^{\mathbf{pw}})$ are not known.
It is also interesting to close this gap and to investigate to what extent the proof technique
in Theorem 8 can be applied to study problems other than Hamiltonian cycles through their
connection matrices.
1:12 Counting Problems in Parameterized Complexity

with clique-sums in Theorem 5. By the graph structure theorem [84], these are almost all
the building blocks of $H$-minor free graphs, and thus an XP algorithm for counting perfect
matchings on such graphs almost seems within reach.

Alas, we blocked out *vortices*: In general, *H*-minor free graphs allow for graphs of bounded pathwidth to be inserted at the faces of the bounded-genus parts; these structures are called vortices. It turns out that counting perfect matchings is *#P*-hard even in planar graphs with one single vortex, and such graphs can be seen to exclude a constant-sized minor.

**► Theorem 7** (Unpublished work by the author with Mingji Xia). *There is a fixed graph H such that counting perfect matchings is #P-hard in graphs excluding H.*

Thus, polynomial-time algorithms cannot be obtained for each excluded minor $H$, but it is
still open to find out which fixed graphs $H$ can be excluded for polynomial-time algorithms.

## 3.2 Counting Hamiltonian cycles in low-pathwidth graphs

To conclude, we briefly consider counting Hamiltonian cycles parameterized by pathwidth. The standard DP for this problem gives a running time of $O^*(\mathbf{pw}^{O(\mathbf{pw})})$ for counting and decision, but celebrated improvements [37] enabled $O^*((2 + \sqrt{2})^{\mathbf{pw}})$ time for the decision problem and for counting modulo 2, and $O^*(6^{\mathbf{pw}})$ time for counting [11]. The bases $2 + \sqrt{2}$ and 6 are optimal under the strong exponential-time hypothesis SETH [37, 32].

Curiously, the concrete numbers $2 + \sqrt{2}$ and 6 can be explained through *connection matrices*. These are particularly nice objects in the intersection of linear algebra and combinatorics [72, 73]. Given a graph parameter $f$ such as the number of Hamiltonian cycles, and $k \in \mathbb{N}$, the $k$-th connection matrix of $f$ is an infinite matrix $C_{f,k}$, indexed by $k$-boundedaried graphs, that describes the behavior of $f$ under graph separations of size $k$. The entry $C_{f,k}(G, H)$ for $k$-boundedaried graphs $G, H$ is defined to be $f(G \oplus H)$, where $G \oplus H$ is the union of $k$-boundedaried graphs $G$ and $H$ with matching vertices identified. Even though the matrices $C_{f,k}$ are infinite-sized, they have finite rank for many interesting graph parameters $f$, including all MSOL-definable $f$ [68]. It can be shown furthermore that evaluating graph parameters $f$ with finite-rank connection matrices is nonuniformly FPT when parameterized by treewidth [73]; this gives an alternative proof of Courcelle's theorem.

Let us focus again on the connection matrix $C_{\mathrm{HC},k}$ for the number of Hamiltonian cycles: Lovász [72] upper-bounded the rank of $C_{\mathrm{HC},k}$ over $\mathbb{Q}$ by $k^{O(k)}$. This bound was recently improved to $\Theta(6^k)$ up to polynomial factors, with a matching lower bound [32]. It was also known before that the rank of $C_{\mathrm{HC},k}$ drops to $\Theta((2+\sqrt{2})^k)$ over the ring $\mathbb{Z}_2$ with a matching lower bound [37]. Note that the constants 6 and $2+\sqrt{2}$ appearing in the rank of $C_{\mathrm{HC},k}$ over $\mathbb{Q}$ and $\mathbb{Z}_2$ are the running time bases for counting Hamiltonian cycles over these rings parameterized by pathwidth. This is a consequence of a more general statement:

**► Theorem 8** ([32]). Let $\mathbb{R}$ be any of the rings $\mathbb{Q}$ or $\mathbb{Z}_p$ for prime $p$. If the connection matrix $C_{\mathrm{HC},k}$ of the number of Hamiltonian cycles has rank $\Omega(c^k)$ over $\mathbb{R}$, then an algorithm with running time $O^*((c - \epsilon)^{\mathbf{pw}})$ for counting Hamiltonian cycles over $\mathbb{R}$ refutes SETH.

While we do know that the rank of $C_{\text{HC},k}$ is $\Omega(3.97^k)$ over $\mathbb{Z}_p$ when $p \neq 2$, resulting in a corresponding complexity lower bound [32], algorithms faster than $O^*(6^{\mathbf{pw}})$ are not known. It is also interesting to close this gap and to investigate to what extent the proof technique in Theorem 8 can be applied to study problems other than Hamiltonian cycles through their connection matrices.
References

1 Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. *Bioinformatics*, 24(13):i241–i249, 2008. doi:10.1093/bioinformatics/btn163.

2 Noga Alon and Shai Gutner. Balanced Hashing, Color Coding and Approximate Counting. In *Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers*, pages 1–16, 2009. doi:10.1007/978-3-642-11269-0_1.

3 Noga Alon and Shai Gutner. Balanced families of perfect hash functions and their applications. *ACM Trans. Algorithms*, 6(3):54:1–54:12, 2010. doi:10.1145/1798596.1798607.

4 Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. *J. ACM*, 42(4):844–856, 1995. doi:10.1145/210332.210337.

5 Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy Problems for Tree-Decomposable Graphs. *J. Algorithms*, 12(2):308–340, 1991. doi:10.1016/0196-6774(91)90006-K.

6 Vikraman Arvind and Venkatesh Raman. Approximation Algorithms for Some Parameterized Counting Problems. In *Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings*, pages 453–464, 2002. doi:10.1007/3-540-36136-7_40.

7 Andreas Björklund. Determinant Sums for Undirected Hamiltonicity. In *51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA*, pages 173–182, 2010. doi:10.1109/FOCS.2010.24.

8 Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set Partitioning via Inclusion-Exclusion. *SIAM Journal on Computing*, 39(2):546–563, 2009. doi:10.1137/070683933.

9 Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time. *ACM Trans. Algorithms*, 13(4):48:1–48:26, 2017. doi:10.1145/3125500.

10 Markus Bläser and Radu Curticapean. Weighted Counting of k-Matchings Is #W[1]-Hard. In *Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings*, pages 171–181, 2012. doi:10.1007/978-3-642-33293-7_17.

11 Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. *Inf. Comput.*, 243:86–111, 2015. doi:10.1016/j.ic.2014.12.008.

12 Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. *J. ACM*, 63(5):44:1–44:69, 2016. doi:10.1145/2973749.

13 Cornelius Brand, Holger Dell, and Thore Husfeldt. Extensor-coding. In *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018*, pages 151–164, 2018. doi:10.1145/3188745.3188902.

14 Cornelius Brand, Holger Dell, and Marc Roth. Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP. In *11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark*, pages 9:1–9:14, 2016. doi:10.4230/LIPIcs.IPEC.2016.9.

15 Cornelius Brand and Marc Roth. Parameterized Counting of Trees, Forests and Matroid Bases. In *Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings*, pages 85–98, 2017. doi:10.1007/978-3-319-58747-9_10.

16 Andrei Bulatov and Martin Grohe. The complexity of partition functions. *Theoretical Computer Science*, 348(2):148–186, 2005. doi:10.1016/j.tcs.2005.09.011.
References

1 Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. *Bioinformatics*, 24(13):i241–i249, 2008. doi:10.1093/bioinformatics/btn163.

2 Noga Alon and Shai Gutner. Balanced Hashing, Color Coding and Approximate Counting. In *Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers*, pages 1–16, 2009. doi:10.1007/978-3-642-11269-0_1.

3 Noga Alon and Shai Gutner. Balanced families of perfect hash functions and their applications. *ACM Trans. Algorithms*, 6(3):54:1–54:12, 2010. doi:10.1145/1798596.1798607.

4 Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. *J. ACM*, 42(4):844–856, 1995. doi:10.1145/210332.210337.

5 Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy Problems for Tree-Decomposable Graphs. *J. Algorithms*, 12(2):308–340, 1991. doi:10.1016/0196-6774(91)90006-K.

6 Vikraman Arvind and Venkatesh Raman. Approximation Algorithms for Some Parameterized Counting Problems. In *Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings*, pages 453–464, 2002. doi:10.1007/3-540-36136-7_40.

7 Andreas Björklund. Determinant Sums for Undirected Hamiltonicity. In *51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA*, pages 173–182, 2010. doi:10.1109/FOCS.2010.24.

8 Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set Partitioning via Inclusion-Exclusion. *SIAM Journal on Computing*, 39(2):546–563, 2009. doi:10.1137/070683933.

9 Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time. *ACM Trans. Algorithms*, 13(4):48:1–48:26, 2017. doi:10.1145/3125500.

10 Markus Bläser and Radu Curticapean. Weighted Counting of k-Matchings Is #W[1]-Hard. In *Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings*, pages 171–181, 2012. doi:10.1007/978-3-642-33293-7_17.

11 Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. *Inf. Comput.*, 243:86–111, 2015. doi:10.1016/j.ic.2014.12.008.

12 Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. *J. ACM*, 63(5):44:1–44:69, 2016. doi:10.1145/2973749.

13 Cornelius Brand, Holger Dell, and Thore Husfeldt. Extensor-coding. In *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018*, pages 151–164, 2018. doi:10.1145/3188745.3188902.

14 Cornelius Brand, Holger Dell, and Marc Roth. Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP. In *11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark*, pages 9:1–9:14, 2016. doi:10.4230/LIPIcs.IPEC.2016.9.

15 Cornelius Brand and Marc Roth. Parameterized Counting of Trees, Forests and Matroid Bases. In *Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings*, pages 85–98, 2017. doi:10.1007/978-3-319-58747-9_10.

16 Andrei Bulatov and Martin Grohe. The complexity of partition functions. *Theoretical Computer Science*, 348(2):148–186, 2005. doi:10.1016/j.tcs.2005.09.011.
1:14 Counting Problems in Parameterized Complexity

17 Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. *J. ACM*, 60(5):34, 2013. doi:10.1145/2528400.

18 Andrei A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In *58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017*, pages 319-330, 2017. doi:10.1109/FOCS.2017.37.

19 Jin-Yi Cai and Xi Chen. Complexity of Counting CSP with Complex Weights. *J. ACM*, 64(3):19:1-19:39, 2017. doi:10.1145/2822891.

20 Jin-yi Cai and Pinyan Lu. Holographic algorithms: From art to science. *J. Comput. Syst. Sci.*, 77(1):41-61, 2011. doi:10.1016/j.jcss.2010.06.005.

21 Jin-yi Cai, Pinyan Lu, and Mingji Xia. Computational Complexity of Holant Problems. *SIAM J. Comput.*, 40(4):1101-1132, 2011. doi:10.1137/100814585.

22 Hubie Chen and Stefan Mengel. Counting Answers to Existential Positive Queries: A Complexity Classification. In *Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016*, pages 315-326, 2016. doi:10.1145/2902251.2902279.

23 Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. *Information and Computation*, 201(2):216-231, 2005. doi:10.1016/j.ic.2005.05.001.

24 Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby. The complexity of approximating conservative counting CSPs. *J. Comput. Syst. Sci.*, 81(1):311-329, 2015. doi:10.1016/j.jcss.2014.06.006.

25 Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. In *Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games*, pages 587-596, 2008. doi:10.1007/978-3-540-70575-8_48.

26 Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. *Discrete Applied Mathematics*, 108(1-2):23-52, 2001. doi:10.1016/S0166-218X(00)00221-3.

27 Radu Curticapean. Counting Matchings of Size *k* Is \#W[1]-Hard. In *Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I*, pages 352-363, 2013. doi:10.1007/978-3-642-39206-1_30.

28 Radu Curticapean. Counting perfect matchings in graphs that exclude a single-crossing minor. *CoRR*, abs/1406.4056, 2014. URL: http://arxiv.org/abs/1406.4056, arXiv: 1406.4056.

29 Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. *Inf. Comput.*, 261(Part):265-280, 2018. doi:10.1016/j.ic.2018.02.008.

30 Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In *Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017*, pages 210-223, 2017. doi:10.1145/3055399.3055502.

31 Radu Curticapean, Holger Dell, and Marc Roth. Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes. In *34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany*, pages 25:1-25:15, 2017. doi:10.4230/LIPIcs.STACS.2017.25.

32 Radu Curticapean, Nathan Lindzey, and Jesper Nederlof. A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank. In *Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018*, pages 1080-1099, 2018. doi:10.1137/1.9781611975031.70.
1:14 Counting Problems in Parameterized Complexity

17 Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. *J. ACM*, 60(5):34, 2013. doi:10.1145/2528400.

18 Andrei A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In *58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017*, pages 319-330, 2017. doi:10.1109/FOCS.2017.37.

19 Jin-Yi Cai and Xi Chen. Complexity of Counting CSP with Complex Weights. *J. ACM*, 64(3):19:1-19:39, 2017. doi:10.1145/2822891.

20 Jin-yi Cai and Pinyan Lu. Holographic algorithms: From art to science. *J. Comput. Syst. Sci.*, 77(1):41-61, 2011. doi:10.1016/j.jcss.2010.06.005.

21 Jin-yi Cai, Pinyan Lu, and Mingji Xia. Computational Complexity of Holant Problems. *SIAM J. Comput.*, 40(4):1101-1132, 2011. doi:10.1137/100814585.

22 Hubie Chen and Stefan Mengel. Counting Answers to Existential Positive Queries: A Complexity Classification. In *Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016*, pages 315-326, 2016. doi:10.1145/2902251.2902279.

23 Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. *Information and Computation*, 201(2):216-231, 2005. doi:10.1016/j.ic.2005.05.001.

24 Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby. The complexity of approximating conservative counting CSPs. *J. Comput. Syst. Sci.*, 81(1):311-329, 2015. doi:10.1016/j.jcss.2014.06.006.

25 Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. In *Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games*, pages 587-596, 2008. doi:10.1007/978-3-540-70575-8_48.

26 Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. *Discrete Applied Mathematics*, 108(1-2):23-52, 2001. doi:10.1016/S0166-218X(00)00221-3.

27 Radu Curticapean. Counting Matchings of Size *k* Is #W[1]-Hard. In *Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I*, pages 352-363, 2013. doi:10.1007/978-3-642-39206-1_30.

28 Radu Curticapean. Counting perfect matchings in graphs that exclude a single-crossing minor. *CoRR*, abs/1406.4056, 2014. URL: http://arxiv.org/abs/1406.4056, arXiv: 1406.4056.

29 Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. *Inf. Comput.*, 261(Part):265-280, 2018. doi:10.1016/j.ic.2018.02.008.

30 Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In *Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017*, pages 210-223, 2017. doi:10.1145/3055399.3055502.

31 Radu Curticapean, Holger Dell, and Marc Roth. Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes. In *34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany*, pages 25:1-25:15, 2017. doi:10.4230/LIPIcs.STACS.2017.25.

32 Radu Curticapean, Nathan Lindzey, and Jesper Nederlof. A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank. In *Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018*, pages 1080-1099, 2018. doi:10.1137/1.9781611975031.70.
33 Radu Curticapean and Dániel Marx. Complexity of Counting Subgraphs: Only the Bound- edness of the Vertex-Cover Number Counts. In *55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014*, pages 130–139, 2014. doi:10.1109/FOCS.2014.22.

34 Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. In *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016*, pages 1650–1669, 2016. doi:10.1137/1.9781611974331.ch13.

35 Radu Curticapean and Mingji Xia. Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k. In *IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015*, pages 994–1009, 2015. doi:10.1109/FOCS.2015.65.

36 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015. doi:10.1007/978-3-319-21275-3.

37 Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity Checking Via Bases of Perfect Matchings. *J. ACM*, 65(3):12:1–12:46, 2018. doi:10.1145/3148227.

38 Paul Dagum and Michael Luby. Approximating the Permanent of Graphs with Large Factors. *Theoretical Computer Science*, 102(2):283–305, 1992. doi:10.1016/0304-3975(92)90234-7.

39 Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. *Theoretical Computer Science*, 329(1-3):315–323, 2004. doi:10.1016/j.tcs.2004.08.008.

40 Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential Time Complexity of the Permanent and the Tutte Polynomial. *ACM Transactions on Algorithms*, 10(4):21, 2014. doi:10.1145/2635812.

41 E. Demaine, M. Hajiaghayi, and D. Thilikos. Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors. *Algorithmica*, 41(4):245–267, 2005. doi:10.1007/s00453-004-1125-y.

42 Erik D. Demaine and Mohammad Taghi Hajiaghayi. The Bidimensionality Theory and Its Algorithmic Applications. *Comput. J.*, 51(3):292–302, 2008. doi:10.1093/comjnl/bxm033.

43 Reinhard Diestel. *Graph Theory, 4th Edition*, volume 173 of *Graduate texts in mathematics*. Springer, 2012.

44 Rodney G. Downey and Michael R. Fellows. *Parameterized Complexity*. Monographs in Computer Science. Springer, 1999. doi:10.1007/978-1-4612-0515-9.

45 Martin Dyer, Leslie Ann Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. *J. ACM*, 54, December 2007. doi:10.1145/1314690.1314691.

46 Martin E. Dyer and Catherine S. Greenhill. The complexity of counting graph homomorphisms. *Random Struct. Algorithms*, 17(3-4):260–289, 2000. doi:10.1002/1098-2418(200010/12)17:3/4\%3C260::AID-RSA5\%3E3.0.CO;2-W.

47 Martin E. Dyer and David Richerby. An Effective Dichotomy for the Counting Constraint Satisfaction Problem. *SIAM J. Comput.*, 42(3):1245–1274, 2013. doi:10.1137/100811258.

48 Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. *SIAM Journal on Computing*, 33(4):892–922, 2004. doi:10.1137/S0097539703427203.

49 Jörg Flum and Martin Grohe. *Parameterized Complexity Theory*. Springer, 2006.

50 Fedor V. Fomin, Erik D. Demaine, and Mohammad Taghi Hajiaghayi. Bidimensionality. In *Encyclopedia of Algorithms*. Springer, 2015. doi:10.1007/978-3-642-27848-8_47-2.

51 Fedor V. Fomin and Dieter Kratsch. *Subset Convolution*, pages 125–139. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. doi:10.1007/978-3-642-16533-7_7.
33 Radu Curticapean and Dániel Marx. Complexity of Counting Subgraphs: Only the Bound- edness of the Vertex-Cover Number Counts. In *55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014*, pages 130–139, 2014. doi:10.1109/FOCS.2014.22.

34 Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. In *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016*, pages 1650–1669, 2016. doi:10.1137/1.9781611974331.ch13.

35 Radu Curticapean and Mingji Xia. Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k. In *IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015*, pages 994–1009, 2015. doi:10.1109/FOCS.2015.65.

36 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015. doi:10.1007/978-3-319-21275-3.

37 Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity Checking Via Bases of Perfect Matchings. *J. ACM*, 65(3):12:1–12:46, 2018. doi:10.1145/3148227.

38 Paul Dagum and Michael Luby. Approximating the Permanent of Graphs with Large Factors. *Theoretical Computer Science*, 102(2):283–305, 1992. doi:10.1016/0304-3975(92)90234-7.

39 Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. *Theoretical Computer Science*, 329(1-3):315–323, 2004. doi:10.1016/j.tcs.2004.08.008.

40 Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential Time Complexity of the Permanent and the Tutte Polynomial. *ACM Transactions on Algorithms*, 10(4):21, 2014. doi:10.1145/2635812.

41 E. Demaine, M. Hajiaghayi, and D. Thilikos. Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors. *Algorithmica*, 41(4):245–267, 2005. doi:10.1007/s00453-004-1125-y.

42 Erik D. Demaine and Mohammad Taghi Hajiaghayi. The Bidimensionality Theory and Its Algorithmic Applications. *Comput. J.*, 51(3):292–302, 2008. doi:10.1093/comjnl/bxm033.

43 Reinhard Diestel. *Graph Theory, 4th Edition*, volume 173 of *Graduate texts in mathematics*. Springer, 2012.

44 Rodney G. Downey and Michael R. Fellows. *Parameterized Complexity*. Monographs in Computer Science. Springer, 1999. doi:10.1007/978-1-4612-0515-9.

45 Martin Dyer, Leslie Ann Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. *J. ACM*, 54, December 2007. doi:10.1145/1314690.1314691.

46 Martin E. Dyer and Catherine S. Greenhill. The complexity of counting graph homomorphisms. *Random Struct. Algorithms*, 17(3-4):260–289, 2000. doi:10.1002/1098-2418(200010/12)17:3/4\%3C260::AID-RSA5\%3E3.0.CO;2-W.

47 Martin E. Dyer and David Richerby. An Effective Dichotomy for the Counting Constraint Satisfaction Problem. *SIAM J. Comput.*, 42(3):1245–1274, 2013. doi:10.1137/100811258.

48 Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. *SIAM Journal on Computing*, 33(4):892–922, 2004. doi:10.1137/S0097539703427203.

49 Jörg Flum and Martin Grohe. *Parameterized Complexity Theory*. Springer, 2006.

50 Fedor V. Fomin, Erik D. Demaine, and Mohammad Taghi Hajiaghayi. Bidimensionality. In *Encyclopedia of Algorithms*. Springer, 2015. doi:10.1007/978-3-642-27848-8_47-2.

51 Fedor V. Fomin and Dieter Kratsch. *Subset Convolution*, pages 125–139. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. doi:10.1007/978-3-642-16533-7_7.
1:16 Counting Problems in Parameterized Complexity

52 Markus Frick. Generalized Model-Checking over Locally Tree-Decomposable Classes. *Theory Comput. Syst.*, 37(1):157–191, 2004. doi:10.1007/s00224-003-1111-9.

53 Anna Galluccio and Martin Loebl. On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents. *Electronic Journal of Combinatorics*, 6, 1998.

54 Leslie Ann Goldberg and Mark Jerrum. Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. *J. Comput. Syst. Sci.*, 79(1):68–78, 2013. doi:10.1016/j.jcss.2012.04.005.

55 Leslie Ann Goldberg and Mark Jerrum. The Complexity of Approximately Counting Tree Homomorphisms. *TOCT*, 6(2):8, 2014. doi:10.1145/2600917.

56 Mark S. Granovetter. The Strength of Weak Ties. *American Journal of Sociology*, 78(6):1360–1380, 1973.

57 Thore Husfeldt. Invitation to Algorithmic Uses of Inclusion-Exclusion. In *Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II*, pages 42–59, 2011. doi:10.1007/978-3-642-22012-8_3.

58 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? *J. Comput. System Sci.*, 63(4):512–530, 2001.

59 A. Isihara. *Statistical physics*. Academic Press, 1971.

60 M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. *J. ACM*, 51(4):671–697, 2004. doi:10.1145/1008731.1008738.

61 Mark Jerrum and Kitty Meeks. Some hard families of parameterized counting problems. *ACM Transactions on Computation Theory*, 7(3):11, 2015. doi:10.1145/2786017.

62 Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. *J. Comput. Syst. Sci.*, 81(4):702–716, 2015. doi:10.1016/j.jcss.2014.11.015.

63 Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. *Combinatorica*, pages 1–26, 2016. doi:10.1007/s00493-016-3338-5.

64 Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. *SIAM Journal on Computing*, 22(5):1087–1116, 1993. doi:10.1137/0222066.

65 Pieter W. Kasteleyn. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. *Physica*, 27(12):1209–1225, 1961. doi:10.1016/0031-8914(61)90063-5.

66 Pieter W. Kasteleyn. Graph Theory and Crystal Physics. In *Graph Theory and Theoretical Physics*, pages 43–110. Academic Press, 1967.

67 Gustav Kirchhoff. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. *Annalen der Physik und Chemie*, LXXIL(12), 1847.

68 Tomer Kotek and Johann A. Makowsky. Connection Matrices and the Definability of Graph Parameters. *Logical Methods in Computer Science*, 10(4), 2014. doi:10.2168/LMCS-10(4:1)2014.

69 Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Counting and Detecting Small Subgraphs via Equations. *SIAM J. Discrete Math.*, 27(2):892–909, 2013. doi:10.1137/110859798.

70 Charles Little. An Extension of Kasteleyn's method of enumerating the 1-factors of planar graphs. In *Combinatorial Mathematics*, LNCS, pages 63–72. Springer, 1974. doi:10.1007/BFb0057377.

71 László Lovász. Operations with structures. *Acta Mathematica Hungarica*, 18(3-4):321–328, 1967.
1:16 Counting Problems in Parameterized Complexity

52 Markus Frick. Generalized Model-Checking over Locally Tree-Decomposable Classes. *Theory Comput. Syst.*, 37(1):157–191, 2004. doi:10.1007/s00224-003-1111-9.

53 Anna Galluccio and Martin Loebl. On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents. *Electronic Journal of Combinatorics*, 6, 1998.

54 Leslie Ann Goldberg and Mark Jerrum. Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. *J. Comput. Syst. Sci.*, 79(1):68–78, 2013. doi:10.1016/j.jcss.2012.04.005.

55 Leslie Ann Goldberg and Mark Jerrum. The Complexity of Approximately Counting Tree Homomorphisms. *TOCT*, 6(2):8, 2014. doi:10.1145/2600917.

56 Mark S. Granovetter. The Strength of Weak Ties. *American Journal of Sociology*, 78(6):1360–1380, 1973.

57 Thore Husfeldt. Invitation to Algorithmic Uses of Inclusion-Exclusion. In *Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II*, pages 42–59, 2011. doi:10.1007/978-3-642-22012-8_3.

58 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? *J. Comput. System Sci.*, 63(4):512–530, 2001.

59 A. Isihara. *Statistical physics*. Academic Press, 1971.

60 M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. *J. ACM*, 51(4):671–697, 2004. doi:10.1145/1008731.1008738.

61 Mark Jerrum and Kitty Meeks. Some hard families of parameterized counting problems. *ACM Transactions on Computation Theory*, 7(3):11, 2015. doi:10.1145/2786017.

62 Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. *J. Comput. Syst. Sci.*, 81(4):702–716, 2015. doi:10.1016/j.jcss.2014.11.015.

63 Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. *Combinatorica*, pages 1–26, 2016. doi:10.1007/s00493-016-3338-5.

64 Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. *SIAM Journal on Computing*, 22(5):1087–1116, 1993. doi:10.1137/0222066.

65 Pieter W. Kasteleyn. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. *Physica*, 27(12):1209–1225, 1961. doi:10.1016/0031-8914(61)90063-5.

66 Pieter W. Kasteleyn. Graph Theory and Crystal Physics. In *Graph Theory and Theoretical Physics*, pages 43–110. Academic Press, 1967.

67 Gustav Kirchhoff. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. *Annalen der Physik und Chemie*, LXXIL(12), 1847.

68 Tomer Kotek and Johann A. Makowsky. Connection Matrices and the Definability of Graph Parameters. *Logical Methods in Computer Science*, 10(4), 2014. doi:10.2168/LMCS-10(4:1)2014.

69 Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Counting and Detecting Small Subgraphs via Equations. *SIAM J. Discrete Math.*, 27(2):892–909, 2013. doi:10.1137/110859798.

70 Charles Little. An Extension of Kasteleyn's method of enumerating the 1-factors of planar graphs. In *Combinatorial Mathematics*, LNCS, pages 63–72. Springer, 1974. doi:10.1007/BFb0057377.

71 László Lovász. Operations with structures. *Acta Mathematica Hungarica*, 18(3-4):321–328, 1967.
72 László Lovász. The rank of connection matrices and the dimension of graph algebras. *Eur. J. Comb.*, 27(6):962–970, 2006. doi:10.1016/j.ejc.2005.04.012.

73 László Lovász. *Large networks and graph limits*, volume 60. American Mathematical Society Providence, 2012.

74 Johann A. Makowsky. Algorithmic uses of the Feferman-Vaught Theorem. *Annals of Pure and Applied Logic*, 126(1-3):159–213, 2004. Provinces of logic determined. Essays in the memory of Alfred Tarski. Parts I, II and III. doi:10.1016/j.apal.2003.11.002.

75 Johann A. Makowsky, Udi Rotics, Ilya Averbouch, and Benny Godlin. Computing Graph Polynomials on Graphs of Bounded Clique-Width. In *Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers*, pages 191–204, 2006. doi:10.1007/11917496_18.

76 Dániel Marx. Can You Beat Treewidth? *Theory of Computing*, 6(1):85–112, 2010. doi: 10.4086/toc.2010.v006a005.

77 Catherine McCartin. Parameterized counting problems. *Ann. Pure Appl. Logic*, 138(1-3):147–182, 2006. doi:10.1016/j.apal.2005.06.010.

78 Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. *Discrete Applied Mathematics*, 198:170–194, 2016. doi:10.1016/j.dam.2015.06.019.

79 Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: Simple building blocks of complex networks. *Science*, 298(5594):824–827, 2002. doi:10.1126/science.298.5594.824.

80 Bojan Mohar. A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface. *SIAM J. Discrete Math.*, 12(1):6–26, 1999. URL: http://epubs.siam.org/sam-bin/dbq/article/29248.

81 Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. *Com-mentaciones Mathematicae Universitatis Carolinae*, 26(2):415–419, 1985.

82 Rolf Niedermeier. *Invitation to fixed-parameter algorithms*, volume 31 of *Oxford Lecture Series in Mathematics and its Applications*. Oxford University Press, Oxford, 2006.

83 Neil Robertson and Paul D. Seymour. Excluding a graph with one crossing. In *Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991*, pages 669–675, 1993.

84 Neil Robertson and Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. *J. Comb. Theory, Ser. B*, 89(1):43–76, 2003. doi:10.1016/S0095-8956(03)00042-X.

85 Marc Roth. Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lat-tices. In *25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017*, Vienna, Austria, pages 63:1–63:14, 2017. doi:10.4230/LIPIcs.ESA.2017.63.

86 Marc Roth and Johannes Schmitt. Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. *CoRR*, abs/1807.01920, 2018. arXiv:1807.01920.

87 Alexander D. Scott and Gregory B. Sorkin. Linear-programming design and analysis of fast algorithms for Max 2-CSP. *Discrete Optimization*, 4(3-4):260–287, 2007. doi:10.1016/j.disopt.2007.08.001.

88 Richard P. Stanley. *Enumerative Combinatorics*, volume 1. Cambridge University Press, second edition, 2011.

89 Simon Straub, Thomas Thierauf, and Fabian Wagner. Counting the Number of Perfect Matchings in $K_5$-Free Graphs. In *IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014*, pages 66–77, 2014. doi:10.1109/CCC.2014.15.

90 H. N. V. Temperley and Michael E. Fisher. Dimer problem in statistical mechanics - an exact result. *Philosophical Magazine*, 6(68):1478–6435, 1961.
72 László Lovász. The rank of connection matrices and the dimension of graph algebras. *Eur. J. Comb.*, 27(6):962–970, 2006. doi:10.1016/j.ejc.2005.04.012.

73 László Lovász. *Large networks and graph limits*, volume 60. American Mathematical Society Providence, 2012.

74 Johann A. Makowsky. Algorithmic uses of the Feferman-Vaught Theorem. *Annals of Pure and Applied Logic*, 126(1-3):159–213, 2004. Provinces of logic determined. Essays in the memory of Alfred Tarski. Parts I, II and III. doi:10.1016/j.apal.2003.11.002.

75 Johann A. Makowsky, Udi Rotics, Ilya Averbouch, and Benny Godlin. Computing Graph Polynomials on Graphs of Bounded Clique-Width. In *Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers*, pages 191–204, 2006. doi:10.1007/11917496_18.

76 Dániel Marx. Can You Beat Treewidth? *Theory of Computing*, 6(1):85–112, 2010. doi: 10.4086/toc.2010.v006a005.

77 Catherine McCartin. Parameterized counting problems. *Ann. Pure Appl. Logic*, 138(1-3):147–182, 2006. doi:10.1016/j.apal.2005.06.010.

78 Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. *Discrete Applied Mathematics*, 198:170–194, 2016. doi:10.1016/j.dam.2015.06.019.

79 Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: Simple building blocks of complex networks. *Science*, 298(5594):824–827, 2002. doi:10.1126/science.298.5594.824.

80 Bojan Mohar. A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface. *SIAM J. Discrete Math.*, 12(1):6–26, 1999. URL: http://epubs.siam.org/sam-bin/dbq/article/29248.

81 Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. *Com-mentaciones Mathematicae Universitatis Carolinae*, 26(2):415–419, 1985.

82 Rolf Niedermeier. *Invitation to fixed-parameter algorithms*, volume 31 of *Oxford Lecture Series in Mathematics and its Applications*. Oxford University Press, Oxford, 2006.

83 Neil Robertson and Paul D. Seymour. Excluding a graph with one crossing. In *Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991*, pages 669–675, 1993.

84 Neil Robertson and Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. *J. Comb. Theory, Ser. B*, 89(1):43–76, 2003. doi:10.1016/S0095-8956(03)00042-X.

85 Marc Roth. Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lat-tices. In *25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017*, Vienna, Austria, pages 63:1–63:14, 2017. doi:10.4230/LIPIcs.ESA.2017.63.

86 Marc Roth and Johannes Schmitt. Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. CoRR, abs/1807.01920, 2018. arXiv:1807.01920.

87 Alexander D. Scott and Gregory B. Sorkin. Linear-programming design and analysis of fast algorithms for Max 2-CSP. *Discrete Optimization*, 4(3-4):260–287, 2007. doi:10.1016/j.disopt.2007.08.001.

88 Richard P. Stanley. *Enumerative Combinatorics*, volume 1. Cambridge University Press, second edition, 2011.

89 Simon Straub, Thomas Thierauf, and Fabian Wagner. Counting the Number of Perfect Matchings in $K_5$-Free Graphs. In *IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014*, pages 66–77, 2014. doi:10.1109/CCC.2014.15.

90 H. N. V. Temperley and Michael E. Fisher. Dimer problem in statistical mechanics - an exact result. *Philosophical Magazine*, 6(68):1478–6435, 1961.
1:18 Counting Problems in Parameterized Complexity

91 Marc Thurley. Kernelizations for Parameterized Counting Problems. In *Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings*, pages 703-714, 2007. doi:10.1007/978-3-540-72504-6_64.

92 Salil P. Vadhan. The Complexity of Counting in Sparse, Regular, and Planar Graphs. *SIAM J. Comput.*, 31(2):398-427, 2001. doi:10.1137/S0097539797321602.

93 Leslie G. Valiant. The complexity of computing the permanent. *Theoret. Comput. Sci.*, 8(2):189-201, 1979.

94 Leslie G. Valiant. Holographic Algorithms. *SIAM J. Comput.*, 37(5):1565-1594, 2008. doi:10.1137/070682575.

95 Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. In *Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings*, pages 566-577, 2009. doi:10.1007/978-3-642-04128-0_51.

96 Vijay V. Vazirani. NC algorithms for computing the number of perfect matchings in $K_{3,3}$-free graphs and related problems. *Inf. Comput.*, 80(2):152-164, 1989.

97 Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. *SIAM Journal on Computing*, 42(3):831-854, 2013. doi:10.1137/09076619X.

98 Mingji Xia, Peng Zhang, and Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. *Theoretical Computer Science*, 384(1):111-125, 2007. Theory and Applications of Models of Computation. doi:10.1016/j.tcs.2007.05.023.

99 Dmitriy Zhuk. A Proof of CSP Dichotomy Conjecture. In *58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017*, pages 331-342, 2017. doi:10.1109/FOCS.2017.38.
1:18 Counting Problems in Parameterized Complexity

91 Marc Thurley. Kernelizations for Parameterized Counting Problems. In *Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings*, pages 703-714, 2007. doi:10.1007/978-3-540-72504-6_64.

92 Salil P. Vadhan. The Complexity of Counting in Sparse, Regular, and Planar Graphs. *SIAM J. Comput.*, 31(2):398-427, 2001. doi:10.1137/S0097539797321602.

93 Leslie G. Valiant. The complexity of computing the permanent. *Theoret. Comput. Sci.*, 8(2):189-201, 1979.

94 Leslie G. Valiant. Holographic Algorithms. *SIAM J. Comput.*, 37(5):1565-1594, 2008. doi:10.1137/070682575.

95 Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. In *Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings*, pages 566-577, 2009. doi:10.1007/978-3-642-04128-0_51.

96 Vijay V. Vazirani. NC algorithms for computing the number of perfect matchings in $K_{3,3}$-free graphs and related problems. *Inf. Comput.*, 80(2):152-164, 1989.

97 Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. *SIAM Journal on Computing*, 42(3):831-854, 2013. doi:10.1137/09076619X.

98 Mingji Xia, Peng Zhang, and Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. *Theoretical Computer Science*, 384(1):111-125, 2007. Theory and Applications of Models of Computation. doi:10.1016/j.tcs.2007.05.023.

99 Dmitriy Zhuk. A Proof of CSP Dichotomy Conjecture. In *58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017*, pages 331-342, 2017. doi:10.1109/FOCS.2017.38.
# A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth

## Julien Baste

Sorbonne Université, Laboratoire d'Informatique de Paris 6, LIP6, Paris, France
julien.baste@uni-ulm.de

## Ignasi Sau

LIRMM, CNRS, Université de Montpellier, Montpellier, France
ignasi.sau@lirmm.fr

https://orcid.org/0000-0002-8981-9287

## Dimitrios M. Thilikos

LIRMM, CNRS, Université de Montpellier, Montpellier, France, and
Department of Mathematics, National and Kapodistrian University of Athens, Greece
sedthilk@thilikos.info

https://orcid.org/0000-0003-0470-1800

## Abstract

For a fixed graph $H$, we are interested in the parameterized complexity of the following problem, called $\{H\}$-M-DELETION, parameterized by the treewidth $\mathrm{tw}$ of the input graph: given an $n$-vertex graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \le k$ such that $G \setminus S$ does not contain $H$ as a minor. In previous work [IPEC, 2017] we proved that if $H$ is planar and connected, then the problem cannot be solved in time $2^{o(\mathrm{tw})} \cdot n^{O(1)}$ under the ETH, and can be solved in time $2^{\mathcal{O}(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$. In this article we manage to classify the optimal asymptotic complexity of $\{H\}$-M-DELETION when $H$ is a connected planar graph on at most 5 vertices. Out of the 29 possibilities (discarding the trivial case $H = K_1$), we prove that 9 of them are solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$, and that the other 20 ones are solvable in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$. Namely, we prove that $K_4$ and the **diamond** are the only graphs on at most 4 vertices for which the problem is solvable in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$, and that the **chair** and the **banner** are the only graphs on 5 vertices for which the problem is solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$. For the version of the problem where $H$ is forbidden as a **topological minor**, the case $H = K_{1,4}$ can be solved in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$. This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems.

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.2

**Related Version** All the results and proofs of this article, as well as those of [1] and some other ones, are permanently available at https://arxiv.org/abs/1704.07284.

**Funding** Work supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).

**Acknowledgements** We would like to thank Eun Jung Kim and Édouard Bonnet for insightful discussions on the topic of this paper.

<figure><img src="image_16.png" /></figure>

© Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos;
licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 2; pp. 2:1–2:13

<figure><img src="image_17.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth

## Julien Baste

Sorbonne Université, Laboratoire d'Informatique de Paris 6, LIP6, Paris, France
julien.baste@uni-ulm.de

## Ignasi Sau

LIRMM, CNRS, Université de Montpellier, Montpellier, France
ignasi.sau@lirmm.fr

https://orcid.org/0000-0002-8981-9287

## Dimitrios M. Thilikos

LIRMM, CNRS, Université de Montpellier, Montpellier, France, and
Department of Mathematics, National and Kapodistrian University of Athens, Greece
sedthilk@thilikos.info

https://orcid.org/0000-0003-0470-1800

## Abstract

For a fixed graph $H$, we are interested in the parameterized complexity of the following problem, called $\{H\}$-M-DELETION, parameterized by the treewidth $\mathrm{tw}$ of the input graph: given an $n$-vertex graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \le k$ such that $G \setminus S$ does not contain $H$ as a minor. In previous work [IPEC, 2017] we proved that if $H$ is planar and connected, then the problem cannot be solved in time $2^{o(\mathrm{tw})} \cdot n^{O(1)}$ under the ETH, and can be solved in time $2^{\mathcal{O}(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$. In this article we manage to classify the optimal asymptotic complexity of $\{H\}$-M-DELETION when $H$ is a connected planar graph on at most 5 vertices. Out of the 29 possibilities (discarding the trivial case $H = K_1$), we prove that 9 of them are solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$, and that the other 20 ones are solvable in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$. Namely, we prove that $K_4$ and the **diamond** are the only graphs on at most 4 vertices for which the problem is solvable in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$, and that the **chair** and the **banner** are the only graphs on 5 vertices for which the problem is solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$. For the version of the problem where $H$ is forbidden as a **topological minor**, the case $H = K_{1,4}$ can be solved in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$. This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems.

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.2

**Related Version** All the results and proofs of this article, as well as those of [1] and some other ones, are permanently available at https://arxiv.org/abs/1704.07284.

**Funding** Work supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).

**Acknowledgements** We would like to thank Eun Jung Kim and Édouard Bonnet for insightful discussions on the topic of this paper.

<figure><img src="image_17.png" /></figure>

© Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos;
licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 2; pp. 2:1–2:13

<figure><img src="image_18.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
### 1 Introduction

Let $H$ be a fixed graph. In the {$H$}-M-DELETION (resp. {$H$}-TM-DELETION) problem, we are given an $n$-vertex graph $G$ and an integer $k$, and the objective is to decide whether there exists a set $S \subseteq V(G)$ with $|S| \le k$ such that $G \setminus S$ does not contain $H$ as a minor (resp. topological minor). These problems belong to the more general category of graph modification problems. The cases where $H$ is planar and connected are already quite general, as the cases $H = K_2$ and $H = K_3$ correspond to VERTEX COVER and FEEDBACK VERTEX SET, respectively. We are interested in the parameterized complexity of {$H$}-M-DELETION and {$H$}-TM-DELETION taking as the parameter the treewidth of $G$, denoted by $\mathrm{tw}$.

Determining the optimal asymptotic complexity of {$H$}-M-DELETION parameterized by treewidth has been an active area in the parameterized complexity community during the last years. As relevant examples, VERTEX COVER is easily solvable in time $2^{O(\mathrm{tw})} \cdot n^{O(1)}$, called single-exponential, by standard dynamic-programming techniques, and no algorithm with running time $2^{o(\mathrm{tw})} \cdot n^{O(1)}$ exists unless the Exponential Time Hypothesis (ETH)<fnref n="1" /> fails [10]. For FEEDBACK VERTEX SET, the existence of a single-exponential algorithm remained open for a while, until Cygan et al. [6] presented the Cut&Count technique. See also [2, 9, 11, 15].

We recently studied these problems in [1] and proved<fnref n="2" />, among other results, that if $H$ is planar and connected, then the problems cannot be solved in time $2^{o(\mathrm{tw})} \cdot n^{O(1)}$ under the ETH, and can be solved in time $2^{O(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$ (for {$H$}-TM-DELETION, we additionally need $H$ to have maximum degree at most 3). We also presented a dichotomy when $H = C_i$ is a cycle on $i$ vertices, by proving that both problems (which are clearly equivalent for subcubic graphs) can be solved in single-exponential time if and only if $i \le 4$. We aimed at a similar dichotomy when $H = P_i$ is a path on $i$ vertices, but we left open the case $H = P_5$. In this article we obtain the following results, the lower bounds holding under the ETH:

1. When $H = K_{1,i}$, the star with $i$ leaves, $\{K_{1,i}\}$-M-DELETION is solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$ for $i \le 3$, and in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$ for $i \ge 4$. On the other hand, $\{K_{1,i}\}$-TM-DELETION can be solved in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$ for every $i \ge 1$. To the best of our knowledge, this is the first example of a graph $H$ for which the complexity of {$H$}-M-DELETION and {$H$}-TM-DELETION differ.

2. When $H = \theta_i$, the multigraph consisting of two vertices and $i \ge 1$ parallel edges, both problems can be solved in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$ for $i \le 2$, and in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$ for $i \ge 3$. The same dichotomy occurs when $H = K_{2,i}$.

3. We classify the optimal asymptotic complexity of {$H$}-M-DELETION when $H$ is a connected planar graph on at most 5 vertices. Out of the 29 possibilities (discarding the trivial case $H = \{K_1\}$), we prove that 9 of them are solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$, and that the other 20 ones are solvable in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$; a summary is shown in Figure 1. Note that $K_4$ and the **diamond** are the only graphs on at most 4 vertices for which the problem is solvable in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$, and that the **chair** and the **banner** are the only graphs on 5 vertices for which the problem is solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$. In particular, this settles the complexity of $\{P_5\}$-M-DELETION, which we left open in [1]. All the lower bounds also hold for {$H$}-TM-DELETION, with the only difference that the case $H = K_{1,4}$ can be solved in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$, as mentioned in item 1 above.

<footnote n="1">¹ The ETH states that 3-SAT on $n$ variables cannot be solved in time $2^{o(n)}$; see [10] for more details.</footnote>

<footnote n="2">² In [1] we considered the more general case where all the graphs in a fixed finite family $\mathcal{F}$ are forbidden as (topological) minors. For simplicity, we only consider here the case where $\mathcal{F}$ contains a single graph.</footnote>
### 1 Introduction

Let $H$ be a fixed graph. In the {$H$}-M-DELETION (resp. {$H$}-TM-DELETION) problem, we are given an $n$-vertex graph $G$ and an integer $k$, and the objective is to decide whether there exists a set $S \subseteq V(G)$ with $|S| \le k$ such that $G \setminus S$ does not contain $H$ as a minor (resp. topological minor). These problems belong to the more general category of graph modification problems. The cases where $H$ is planar and connected are already quite general, as the cases $H = K_2$ and $H = K_3$ correspond to VERTEX COVER and FEEDBACK VERTEX SET, respectively. We are interested in the parameterized complexity of {$H$}-M-DELETION and {$H$}-TM-DELETION taking as the parameter the treewidth of $G$, denoted by $\mathrm{tw}$.

Determining the optimal asymptotic complexity of {$H$}-M-DELETION parameterized by treewidth has been an active area in the parameterized complexity community during the last years. As relevant examples, VERTEX COVER is easily solvable in time $2^{O(\mathrm{tw})} \cdot n^{O(1)}$, called single-exponential, by standard dynamic-programming techniques, and no algorithm with running time $2^{o(\mathrm{tw})} \cdot n^{O(1)}$ exists unless the Exponential Time Hypothesis (ETH)<fnref n="1" /> fails [10]. For FEEDBACK VERTEX SET, the existence of a single-exponential algorithm remained open for a while, until Cygan et al. [6] presented the Cut&Count technique. See also [2, 9, 11, 15].

We recently studied these problems in [1] and proved<fnref n="2" />, among other results, that if $H$ is planar and connected, then the problems cannot be solved in time $2^{o(\mathrm{tw})} \cdot n^{O(1)}$ under the ETH, and can be solved in time $2^{O(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$ (for {$H$}-TM-DELETION, we additionally need $H$ to have maximum degree at most 3). We also presented a dichotomy when $H = C_i$ is a cycle on $i$ vertices, by proving that both problems (which are clearly equivalent for subcubic graphs) can be solved in single-exponential time if and only if $i \le 4$. We aimed at a similar dichotomy when $H = P_i$ is a path on $i$ vertices, but we left open the case $H = P_5$. In this article we obtain the following results, the lower bounds holding under the ETH:

1. When $H = K_{1,i}$, the star with $i$ leaves, $\{K_{1,i}\}$-M-DELETION is solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$ for $i \le 3$, and in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$ for $i \ge 4$. On the other hand, $\{K_{1,i}\}$-TM-DELETION can be solved in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$ for every $i \ge 1$. To the best of our knowledge, this is the first example of a graph $H$ for which the complexity of {$H$}-M-DELETION and {$H$}-TM-DELETION differ.

2. When $H = \theta_i$, the multigraph consisting of two vertices and $i \ge 1$ parallel edges, both problems can be solved in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$ for $i \le 2$, and in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$ for $i \ge 3$. The same dichotomy occurs when $H = K_{2,i}$.

3. We classify the optimal asymptotic complexity of {$H$}-M-DELETION when $H$ is a connected planar graph on at most 5 vertices. Out of the 29 possibilities (discarding the trivial case $H = \{K_1\}$), we prove that 9 of them are solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$, and that the other 20 ones are solvable in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$; a summary is shown in Figure 1. Note that $K_4$ and the **diamond** are the only graphs on at most 4 vertices for which the problem is solvable in time $2^{\Theta(\mathrm{tw} \cdot \log \mathrm{tw})} \cdot n^{O(1)}$, and that the **chair** and the **banner** are the only graphs on 5 vertices for which the problem is solvable in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$. In particular, this settles the complexity of $\{P_5\}$-M-DELETION, which we left open in [1]. All the lower bounds also hold for {$H$}-TM-DELETION, with the only difference that the case $H = K_{1,4}$ can be solved in time $2^{\Theta(\mathrm{tw})} \cdot n^{O(1)}$, as mentioned in item 1 above.

<footnote n="1">¹ The ETH states that 3-SAT on $n$ variables cannot be solved in time $2^{o(n)}$; see [10] for more details.</footnote>

<footnote n="2">² In [1] we considered the more general case where all the graphs in a fixed finite family $\mathcal{F}$ are forbidden as (topological) minors. For simplicity, we only consider here the case where $\mathcal{F}$ contains a single graph.</footnote>
<figure><img src="image_18.png" /><figcaption>■ **Figure 1** Classification of the complexity of {$H$}-M-DELETION for all connected simple planar graphs $H$ with $|V(H)| \le 5$ and $|E(H)| \ge 1$: for the 9 graphs on the left (resp. 20 graphs on the right), the problem is solvable in time $2^{\Theta(\text{tw})} \cdot n^{O(1)}$ (resp. $2^{\Theta(\text{tw} \cdot \log \text{tw})} \cdot n^{O(1)}$). For {$H$}-TM-DELETION, $K_{1,4}$ should be on the left. The results of this article correspond to the red (darker) graphs; the other ones were either already known (namely, $P_2$, $P_3$, and $C_3$) or obtained in [1].</figcaption></figure>

Let us discuss about the techniques that we used to obtain the above results. The single-exponential algorithms are ad hoc, some being easier than others. All of them exploit a structural characterization of the graphs that exclude that particular graph as a (topological) minor; cf. for instance Lemma 1. Intuitively, the “complexity” of this characterization is what determines the difficulty of the corresponding dynamic programming algorithm, and is also what makes the difference between being solvable in single-exponential time or not.

More precisely, the algorithms for {$K_{1,s}$}-TM-DELETION are simple and use standard dynamic programming techniques on graphs of bounded treewidth. The algorithm for {$\mathbf{paw}$}-TM-DELETION is more involved and uses the rank-based approach introduced by Bodlaender et al. [2], similarly to the algorithm for {$C_4$}-TM-DELETION that we presented in [1]. Finally, the algorithms for {$\mathbf{chair}$}-TM-DELETION and {$\mathbf{banner}$}-TM-DELETION are a combination of some of the algorithms given here and in [1], the latter one using the rank-based approach.

The superexponential lower bounds of this article are inspired by a reduction of Bonnet et al. [4]. Namely, we prove subexponential lower bounds for $P_5$, $K_{1,i}$ with $i \ge 4$ for the minor version, $K_{2,i}$ and $\theta_i$ for $i \ge 3$ (note that if $G$ is a simple graph, {$\theta_3$}-DELETION is equivalent to {$\mathbf{diamond}$}-DELETION), and the following graphs depicted in Figure 1: the $\mathbf{px}$, the $\mathbf{kite}$, the $\mathbf{ dart}$, the $\mathbf{bull}$, the $\mathbf{butterfly}$, the $\mathbf{cricket}$, and the $\mathbf{co-banner}$. All these reductions are based on a general construction (cf. Section 4.1), and then we need particular small gadgets to deal with each of the graphs. On the other hand, one can easily check that all the other graphs
<figure><img src="image_19.png" /><figcaption>■ **Figure 1** Classification of the complexity of {$H$}-M-DELETION for all connected simple planar graphs $H$ with $|V(H)| \le 5$ and $|E(H)| \ge 1$: for the 9 graphs on the left (resp. 20 graphs on the right), the problem is solvable in time $2^{\Theta(\text{tw})} \cdot n^{O(1)}$ (resp. $2^{\Theta(\text{tw} \cdot \log \text{tw})} \cdot n^{O(1)}$). For {$H$}-TM-DELETION, $K_{1,4}$ should be on the left. The results of this article correspond to the red (darker) graphs; the other ones were either already known (namely, $P_2$, $P_3$, and $C_3$) or obtained in [1].</figcaption></figure>

Let us discuss about the techniques that we used to obtain the above results. The single-exponential algorithms are ad hoc, some being easier than others. All of them exploit a structural characterization of the graphs that exclude that particular graph as a (topological) minor; cf. for instance Lemma 1. Intuitively, the “complexity” of this characterization is what determines the difficulty of the corresponding dynamic programming algorithm, and is also what makes the difference between being solvable in single-exponential time or not.

More precisely, the algorithms for {$K_{1,s}$}-TM-DELETION are simple and use standard dynamic programming techniques on graphs of bounded treewidth. The algorithm for {$\mathbf{paw}$}-TM-DELETION is more involved and uses the rank-based approach introduced by Bodlaender et al. [2], similarly to the algorithm for {$C_4$}-TM-DELETION that we presented in [1]. Finally, the algorithms for {$\mathbf{chair}$}-TM-DELETION and {$\mathbf{banner}$}-TM-DELETION are a combination of some of the algorithms given here and in [1], the latter one using the rank-based approach.

The superexponential lower bounds of this article are inspired by a reduction of Bonnet et al. [4]. Namely, we prove subexponential lower bounds for $P_5$, $K_{1,i}$ with $i \ge 4$ for the minor version, $K_{2,i}$ and $\theta_i$ for $i \ge 3$ (note that if $G$ is a simple graph, {$\theta_3$}-DELETION is equivalent to {$\mathbf{diamond}$}-DELETION), and the following graphs depicted in Figure 1: the $\mathbf{px}$, the $\mathbf{kite}$, the $\mathbf{ dart}$, the $\mathbf{bull}$, the $\mathbf{butterfly}$, the $\mathbf{cricket}$, and the $\mathbf{co-banner}$. All these reductions are based on a general construction (cf. Section 4.1), and then we need particular small gadgets to deal with each of the graphs. On the other hand, one can easily check that all the other graphs
## 2:4 A Complexity Dichotomy for Hitting Small Planar Minors

on the right hand side of Figure 1, namely $K_4$, $C_5$, $\overline{K_3 \cup 2K_1}$, $K_5$-e, $W_4$, $\overline{P_3 \cup 2K_1}$, $\overline{P_2 \cup P_3}$, the gem, and the house, satisfy the general condition given in [1, Theorem 20], and therefore the superexponential lower bound follows for both problems and each of these graphs. This completes the dichotomy for all connected (simple) planar graphs on at most 5 vertices.

The remainder of this article is organized as follows. In Section 2 we provide some preliminaries. The single-exponential algorithms are presented in Section 3 and the superexponential lower bounds in Section 4. We conclude the article in Section 5. Due to space constraints, the proofs of the results marked with ‘(★)’ can be found in the full version of this article.

## 2 Preliminaries

We use standard graph-theoretic notation, and we refer to [7] for any undefined term and the notions of minor and topological minor. We also refer to [8, 5] for the basic definitions of parameterized complexity, tree decompositions, and treewidth. We need to introduce nice tree decompositions, which make the presentation of the algorithms much simpler.

Let $\mathcal{D} = (T, \mathcal{X})$ be a tree decomposition of $G$, $r$ be a vertex of $T$, and $\mathcal{G} = \{G_t \mid t \in V(T)\}$ be a collection of subgraphs of $G$, indexed by the vertices of $T$. We say that the triple $(\mathcal{D}, r, \mathcal{G})$ is a *nice tree decomposition* of $G$ if the following conditions hold:

- $X_r = \emptyset$ and $G_r = G$,

- each node of $\mathcal{D}$ has at most two children in $T$,

- for each leaf $t \in V(T)$, $X_t = \emptyset$ and $G_t = (\emptyset, \emptyset)$. Such $t$ is called a *leaf node*,

- if $t \in V(T)$ has exactly one child $t'$, then either

- $X_t = X_{t'} \cup \{v_{\text{insert}}\}$ for some $v_{\text{insert}} \notin X_{t'}$ and $G_t = G[V(G_{t'}) \cup \{v_{\text{insert}}\}]$. The node $t$ is called *introduce vertex node* and the vertex $v_{\text{insert}}$ is the *insertion vertex* of $X_t$,

- $X_t = X_{t'} \setminus \{v_{\text{forget}}\}$ for some $v_{\text{forget}} \in X_{t'}$ and $G_t = G_{t'}$. The node $t$ is called *forget vertex node* and $v_{\text{forget}}$ is the *forget vertex* of $X_t$.

- if $t \in V(T)$ has exactly two children $t'$ and $t''$, then $X_t = X_{t'} = X_{t''}$, and $E(G_{t'}) \cap E(G_{t''}) = \emptyset$. The node $t$ is called a *join node*.

For each $t \in V(T)$, we denote by $V_t$ the set $V(G_t)$. Given a tree decomposition, it is possible to transform it in polynomial time to a *nice* new one of the same width [12]. Moreover, by Bodlaender et al. [3] we can find in time $2^{O(\text{tw})} \cdot n$ a tree decomposition of width $\mathcal{O}(\text{tw})$ of any graph $G$. Hence, since in this article we focus on single-exponential algorithms, we may assume that a nice tree decomposition of width $w = \mathcal{O}(\text{tw})$ is given with the input.

If a graph $G$ contains a graph $H$ as a minor (resp. topological minor), we denote it by $H \preceq_m G$ (resp. $H \preceq_{\text{tm}} G$). For a fixed graph $H$ and a graph $G$, we define the parameter $\mathbf{m}_{\{H\}}(G)$ (resp. $\mathbf{tm}_{\{H\}}(G)$) as the minimum size of a set $S \subseteq V(G)$ such that $H \not\preceq_m G \setminus S$ (resp. $H \not\preceq_{\text{tm}} G \setminus S$).

## 3 Single-exponential algorithms

In this section we present single-exponential algorithms for hitting particular graphs. Since the algorithms when $H = K_{1,s}$ use standard dynamic programming techniques, they have been moved to the full version. In what follows we present a single-exponential algorithm for $\{\text{paw}\}$-TM-DELETION. For completeness, the basic ingredients and notations of the rank-based approach of Bodlaender et al. [2] are given in the full version. The algorithms for the *chair* and the *banner* are also given in the full version.

We start with a simple structural characterization of the simple graphs that exclude the *paw* as a topological minor; recall the *paw* graph in Figure 1.
## 2:4 A Complexity Dichotomy for Hitting Small Planar Minors

on the right hand side of Figure 1, namely $K_4$, $C_5$, $\overline{K_3 \cup 2K_1}$, $K_5$-e, $W_4$, $\overline{P_3 \cup 2K_1}$, $\overline{P_2 \cup P_3}$, the gem, and the house, satisfy the general condition given in [1, Theorem 20], and therefore the superexponential lower bound follows for both problems and each of these graphs. This completes the dichotomy for all connected (simple) planar graphs on at most 5 vertices.

The remainder of this article is organized as follows. In Section 2 we provide some preliminaries. The single-exponential algorithms are presented in Section 3 and the superexponential lower bounds in Section 4. We conclude the article in Section 5. Due to space constraints, the proofs of the results marked with ‘(★)’ can be found in the full version of this article.

## 2 Preliminaries

We use standard graph-theoretic notation, and we refer to [7] for any undefined term and the notions of minor and topological minor. We also refer to [8, 5] for the basic definitions of parameterized complexity, tree decompositions, and treewidth. We need to introduce nice tree decompositions, which make the presentation of the algorithms much simpler.

Let $\mathcal{D} = (T, \mathcal{X})$ be a tree decomposition of $G$, $r$ be a vertex of $T$, and $\mathcal{G} = \{G_t \mid t \in V(T)\}$ be a collection of subgraphs of $G$, indexed by the vertices of $T$. We say that the triple $(\mathcal{D}, r, \mathcal{G})$ is a *nice tree decomposition* of $G$ if the following conditions hold:

- $X_r = \emptyset$ and $G_r = G$,

- each node of $\mathcal{D}$ has at most two children in $T$,

- for each leaf $t \in V(T)$, $X_t = \emptyset$ and $G_t = (\emptyset, \emptyset)$. Such $t$ is called a *leaf node*,

- if $t \in V(T)$ has exactly one child $t'$, then either

- $X_t = X_{t'} \cup \{v_{\text{insert}}\}$ for some $v_{\text{insert}} \notin X_{t'}$ and $G_t = G[V(G_{t'}) \cup \{v_{\text{insert}}\}]$. The node $t$ is called *introduce vertex node* and the vertex $v_{\text{insert}}$ is the *insertion vertex* of $X_t$,

- $X_t = X_{t'} \setminus \{v_{\text{forget}}\}$ for some $v_{\text{forget}} \in X_{t'}$ and $G_t = G_{t'}$. The node $t$ is called *forget vertex node* and $v_{\text{forget}}$ is the *forget vertex* of $X_t$.

- if $t \in V(T)$ has exactly two children $t'$ and $t''$, then $X_t = X_{t'} = X_{t''}$, and $E(G_{t'}) \cap E(G_{t''}) = \emptyset$. The node $t$ is called a *join node*.

For each $t \in V(T)$, we denote by $V_t$ the set $V(G_t)$. Given a tree decomposition, it is possible to transform it in polynomial time to a *nice* new one of the same width [12]. Moreover, by Bodlaender et al. [3] we can find in time $2^{O(\text{tw})} \cdot n$ a tree decomposition of width $\mathcal{O}(\text{tw})$ of any graph $G$. Hence, since in this article we focus on single-exponential algorithms, we may assume that a nice tree decomposition of width $w = \mathcal{O}(\text{tw})$ is given with the input.

If a graph $G$ contains a graph $H$ as a minor (resp. topological minor), we denote it by $H \preceq_m G$ (resp. $H \preceq_{\text{tm}} G$). For a fixed graph $H$ and a graph $G$, we define the parameter $\mathbf{m}_{\{H\}}(G)$ (resp. $\mathbf{tm}_{\{H\}}(G)$) as the minimum size of a set $S \subseteq V(G)$ such that $H \not\preceq_m G \setminus S$ (resp. $H \not\preceq_{\text{tm}} G \setminus S$).

## 3 Single-exponential algorithms

In this section we present single-exponential algorithms for hitting particular graphs. Since the algorithms when $H = K_{1,s}$ use standard dynamic programming techniques, they have been moved to the full version. In what follows we present a single-exponential algorithm for $\{\text{paw}\}$-TM-DELETION. For completeness, the basic ingredients and notations of the rank-based approach of Bodlaender et al. [2] are given in the full version. The algorithms for the *chair* and the *banner* are also given in the full version.

We start with a simple structural characterization of the simple graphs that exclude the *paw* as a topological minor; recall the *paw* graph in Figure 1.