Buchumschlag

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Curticapean, Radu, Döring, Simon, Neuen, Daniel
Format:	Preprint
Veröffentlicht:	2025
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: Hardness via Fourier Analysis
von: Curticapean, Radu, et al.
Veröffentlicht: (2024)

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

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

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

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

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)

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)

Finding One Local Optimum Is Easy -- but What About Two?
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2025)

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

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

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

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

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

Parameterized Complexity of Vehicle Routing
von: Döring, Michelle, et al.
Veröffentlicht: (2025)

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)

Structural Parameterizations for Induced and Acyclic Matching
von: Lampis, Michael, et al.
Veröffentlicht: (2025)

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

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
von: Wang, Chengu
Veröffentlicht: (2026)

Deterministic Independent Sets in the Semi-Streaming Model
von: Ye, Daniel
Veröffentlicht: (2025)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
von: Clinch, Katie, et al.
Veröffentlicht: (2025)

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

Counting Locally Optimal Tours in the TSP
von: Manthey, Bodo, et al.
Veröffentlicht: (2024)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
von: Bai, Tian, et al.
Veröffentlicht: (2026)

Generalized Graph Packing Problems Parameterized by Treewidth
von: Esmer, Barış Can, et al.
Veröffentlicht: (2025)

On the Space Complexity of Online Convolution
von: Andersson, Joel Daniel, et al.
Veröffentlicht: (2025)

FPT Parameterisations of Fractional and Generalised Hypertree Width
von: Lanzinger, Matthias, et al.
Veröffentlicht: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

On the Advantage of Adaptivity for Sampling with Cell Probes
von: Byramji, Farzan, et al.
Veröffentlicht: (2026)

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

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