Cover Image

On the Complexity of Problems on Graphs Defined on Groups

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Das, Bireswar, Dey, Dipan, Ghosh, Jinia
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Discrete Mathematics Group Theory F.1.3; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
by: Anand, Emile
Published: (2025)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
by: Pavlov, Gorgi
Published: (2026)

Complexity of Firefighting on Graphs
by: Althoetmar, Julius, et al.
Published: (2025)

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
by: Fairbairn, David L., et al.
Published: (2024)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
by: Burke, Kyle, et al.
Published: (2025)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
by: Bartlett, Celina Janet
Published: (2025)

Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
by: Bok, Jan, et al.
Published: (2025)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems
by: Könen, David, et al.
Published: (2023)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

The Complexity of Blocking All Solutions
by: Grüne, Christoph, et al.
Published: (2025)

Fair Division Among Couples and Small Groups
by: Gölz, Paul, et al.
Published: (2025)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
by: Grüne, Christoph, et al.
Published: (2024)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
by: Istrate, Gabriel
Published: (2024)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
by: Grochow, Joshua A., et al.
Published: (2022)

Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
by: Prolubnikov, Alexander
Published: (2015)

On the complexity of Sandwich Problems for $M$-partitions
by: Barsukov, Alexey, et al.
Published: (2026)

On the hull and interval numbers of oriented graphs
by: Araujo, J., et al.
Published: (2022)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)

A Decomposition Approach to the Weighted $k$-server Problem
by: Ayyadevara, Nikhil, et al.
Published: (2024)

On Finding Randomly Planted Cliques in Arbitrary Graphs
by: Agrimonti, Francesco, et al.
Published: (2025)

New Results on Edge-coloring and Total-coloring of Split Graphs
by: Couto, Fernanda, et al.
Published: (2023)

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
by: Shalaby, Ahmed, et al.
Published: (2024)

Ordering groups and the Identity Problem
by: Bodart, Corentin, et al.
Published: (2024)

Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
by: Schindling, Georg
Published: (2025)

The Identity Problem in the special affine group of $\mathbb{Z}^2$
by: Dong, Ruiwen
Published: (2023)

Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs
by: Büngener, Aaron, et al.
Published: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

Arborescences and Shortest Path Trees when Colors Matter
by: Ardra, P. S., et al.
Published: (2024)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
by: Burke, Kyle, et al.
Published: (2024)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

Col is PSPACE-complete on Triangular Grids
by: Burke, Kyle, et al.
Published: (2025)

Quantitative Edge Eigenvector Universality for Random Regular Graphs: Berry-Esseen Bounds with Explicit Constants
by: Nagel, Leonhard
Published: (2025)