Copertina

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Döring, Simon, Marx, Dániel, Wellnitz, Philip
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
di: Focke, Jacob, et al.
Pubblicazione: (2022)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
di: Curticapean, Radu, et al.
Pubblicazione: (2025)

The Complexity of Finding and Counting Subtournaments
di: Döring, Simon, et al.
Pubblicazione: (2025)

Residue Domination in Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2024)

The Complexity of Counting Small Sub-Hypergraphs
di: Bressan, Marco, et al.
Pubblicazione: (2025)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2025)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
di: Baril, Ambroise, et al.
Pubblicazione: (2025)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
di: Esmer, Barış Can, et al.
Pubblicazione: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
di: Grossman, Ofer, et al.
Pubblicazione: (2023)

Generalized Graph Packing Problems Parameterized by Treewidth
di: Esmer, Barış Can, et al.
Pubblicazione: (2025)

Steiner Forest for $H$-Subgraph-Free Graphs
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2026)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
di: Putterman, Aaron, et al.
Pubblicazione: (2026)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
di: Focke, Jacob, et al.
Pubblicazione: (2023)

Can You Link Up With Treewidth?
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
di: Abboud, Amir, et al.
Pubblicazione: (2026)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

Semi-Streaming Algorithms for Graph Property Certification
di: Das, Avinandan, et al.
Pubblicazione: (2025)

Quantum Property Testing for Bounded-Degree Directed Graphs
di: Peng, Pan, et al.
Pubblicazione: (2026)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
di: Firbas, Alexander, et al.
Pubblicazione: (2024)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
di: Lucke, Felicia, et al.
Pubblicazione: (2024)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
di: Frei, Fabian, et al.
Pubblicazione: (2025)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
di: Yu, Xifan, et al.
Pubblicazione: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
di: Frei, Fabian, et al.
Pubblicazione: (2024)

A Note on Approximability of Densest At-Least-k-Subgraph
di: Laekhanukit, Bundit, et al.
Pubblicazione: (2026)

Colouring $(P_r+P_s)$-Free Graphs
di: Klimošová, Tereza, et al.
Pubblicazione: (2018)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
di: Shih, Yu-Sheng, et al.
Pubblicazione: (2026)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
di: Wang, Chengu
Pubblicazione: (2026)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
di: S., Karthik C., et al.
Pubblicazione: (2023)

Efficient Catalytic Graph Algorithms
di: Cook, James, et al.
Pubblicazione: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
di: Dey, Palash, et al.
Pubblicazione: (2026)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
di: Fujie, Yuto, et al.
Pubblicazione: (2025)

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Knapsack on Graphs with Relaxed Neighborhood Constraints
di: Dey, Palash, et al.
Pubblicazione: (2025)

Matching and Edge Cover in Temporal Graphs
di: Cioni, Lapo, et al.
Pubblicazione: (2025)

The Parameterized Landscape of Labeled Graph Contractions
di: Lafond, Manuel, et al.
Pubblicazione: (2025)