Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies

Marco Bressan, Marc Roth

Type: Preprint

Publication Date: 2021-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2103.05588

View Publication

Locations

arXiv (Cornell University) - View - PDF
Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano) - View - PDF
Oxford University Research Archive (ORA) (University of Oxford) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Counting homomorphisms, subgraphs, and induced subgraphs in degenerate graphs: new hardness results and complete complexity classifications.	2021	Marco Bressan Marc Roth
+ PDF Chat	Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies	2022	Marco Bressan Marc Roth
+	Counting Subgraphs in Somewhere Dense Graphs	2022	Marco Bressan Leslie Ann Goldberg Kitty Meeks Marc Roth
+	Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles	2020	Suman K. Bera Noujan Pashanasangi C. Seshadhri
+	Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles	2020	Suman K. Bera Noujan Pashanasangi C. Seshadhri
+	Faster algorithms for counting subgraphs in sparse graphs	2018	Marco Bressan
+	Faster algorithms for counting subgraphs in sparse graphs	2018	Marco Bressan
+	On degeneracy and the parameterized complexity of subgraph counting.	2018	Marco Bressan
+ PDF Chat	Faster algorithms for counting subgraphs in sparse graphs	2021	Marco Bressan
+ PDF Chat	Homomorphisms are a good basis for counting small subgraphs	2017	Radu Curticapean Holger Dell Dániel Marx
+ PDF Chat	Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles	2021	Suman K. Bera Noujan Pashanasangi C. Seshadhri
+	Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time	2019	Jesper Nederlof
+	Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time	2019	Jesper Nederlof
+	A Dichotomy Hierarchy Characterizing Linear Time Subgraph Counting in Bounded Degeneracy Graphs	2023	Daniel Paul-Pena C. Seshadhri
+	The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree	2023	Marco Bressan Matthias Lanzinger Marc Roth
+	Faster subgraph counting in sparse graphs	2018	Marco Bressan
+	Counting Problems in Parameterized Complexity.	2019	Radu Curticapean
+	Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes	2017	Radu Curticapean Holger Dell Marc Roth
+ PDF Chat	Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs	2024	Daniel Paul-Pena C. Seshadhri
+	The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree	2022	Marco Bressan Matthias Lanzinger Marc Roth

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors