Buchumschlag

The Complexity of Finding and Counting Subtournaments

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Döring, Simon, Houdaigoui, Sarah, Picasarri-Arrieta, Lucas, Wellnitz, Philip
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

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

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

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
von: Curticapean, Radu, 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)

Residue Domination in Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2024)

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

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

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

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

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)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
von: Abu-Khzam, Faisal N., et al.
Veröffentlicht: (2024)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

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

Complexity of Finding and Enumerating Interconnection Trees
von: Demange, Noé, et al.
Veröffentlicht: (2026)

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

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
von: Curticapean, Radu, et al.
Veröffentlicht: (2024)

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

Optimal Parallel Basis Finding in Graphic and Related Matroids
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Finding Maximum Common Contractions Between Phylogenetic Networks
von: Marchand, Bertrand, et al.
Veröffentlicht: (2024)

Finding One Local Optimum Is Easy -- but What About Two?
von: Kobayashi, Yasuaki, 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)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
von: de Berg, Mark, et al.
Veröffentlicht: (2025)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
von: Grüttemeier, Niels, et al.
Veröffentlicht: (2025)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
von: Gaspers, Serge, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Odd Coloring
von: Bhyravarapu, Sriram, et al.
Veröffentlicht: (2025)

On the Complexity of Signed Roman Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

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

Computational Complexity in Property Testing
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)

The Complexity of Maximal Common Subsequence Enumeration
von: Buzzega, Giovanni, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Min-Sum-Radii
von: Kumar, Pankaj, et al.
Veröffentlicht: (2026)

Novel Complexity Results for Temporal Separators with Deadlines
von: Dondi, Riccardo, et al.
Veröffentlicht: (2025)

Complexity of Local Search for Euclidean Clustering Problems
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

Streaming Complexity Separations for Dense and Sparse Graphs
von: Liu, Yang P., et al.
Veröffentlicht: (2026)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
von: Kurita, Kazuhiro, et al.
Veröffentlicht: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)