Buchumschlag

Counting Small Induced Subgraphs: Hardness via Fourier Analysis

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Curticapean, Radu, Neuen, Daniel
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
von: Curticapean, Radu, et al.
Veröffentlicht: (2025)

Can You Link Up With Treewidth?
von: Curticapean, Radu, et al.
Veröffentlicht: (2024)

Faster Convolutions: Yates and Strassen Revisited
von: Brand, Cornelius, et al.
Veröffentlicht: (2025)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
von: Döring, Simon, et al.
Veröffentlicht: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

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

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

The Complexity of Counting Small Sub-Hypergraphs
von: Bressan, Marco, et al.
Veröffentlicht: (2025)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
von: Gamarnik, David, et al.
Veröffentlicht: (2026)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
von: Yu, Xifan, et al.
Veröffentlicht: (2024)

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

A Note on Approximability of Densest At-Least-k-Subgraph
von: Laekhanukit, Bundit, et al.
Veröffentlicht: (2026)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
von: Shih, Yu-Sheng, et al.
Veröffentlicht: (2026)

On Detecting $H$-Induced Minors for Small $H$
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2026)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
von: Neuen, Daniel
Veröffentlicht: (2020)

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

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
von: Dey, Palash, et al.
Veröffentlicht: (2026)

Fourier Analysis of Iterative Algorithms
von: Jones, Chris, et al.
Veröffentlicht: (2024)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

The Complexity of Finding and Counting Subtournaments
von: Döring, Simon, et al.
Veröffentlicht: (2025)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

Hardness of Dynamic Core and Truss Decompositions
von: Couto, Yan S., et al.
Veröffentlicht: (2025)

Algorithms and Hardness for Estimating Statistical Similarity
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Sampling Permutations with Cell Probes is Hard
von: Alekseev, Yaroslav, et al.
Veröffentlicht: (2025)

Hardness Results on Characteristics for Elastic-Degenerated Strings
von: Köppl, Dominik, et al.
Veröffentlicht: (2024)

k-SUM Hardness Implies Treewidth-SETH
von: Lampis, Michael
Veröffentlicht: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

Sumplete is Hard, Even with Two Different Numbers
von: Ruangwises, Suthee
Veröffentlicht: (2023)

Hardness and Algorithmic Results for Roman \{3\}-Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2026)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
von: Grossman, Ofer, et al.
Veröffentlicht: (2023)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

Testing Sumsets is Hard
von: Chen, Xi, et al.
Veröffentlicht: (2024)

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

Small Hazard-free Transducers
von: Bund, Johannes, et al.
Veröffentlicht: (2018)

Steiner Forest for $H$-Subgraph-Free Graphs
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2026)