2026-08-17T10:36:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10202 2024-03-06T10:44:14Z ddc:004 open_access

Counting Problems in Parameterized Complexity Curticapean, Radu counting complexity parameterized complexity graph motifs perfect matchings graph minor theory Hamiltonian cycles 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Radu Curticapean 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.1 urn:nbn:de:0030-drops-102026 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.1 eng https://creativecommons.org/licenses/by/3.0/legalcode