Cover Image

Reducibility among NP-Hard graph problems and boundary classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hassan, Syed Mujtaba, Hussain, Shahid, Samad, Abdul
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Computation and Language Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

On coloring graphs with well-distributed edge density
by: Hassan, Syed Mujtaba, et al.
Published: (2024)

Three Hardness Results for Graph Similarity Problems
by: Sun, He, et al.
Published: (2023)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
by: Le, Hoang-Oanh, et al.
Published: (2023)

Hardness of Finding Kings and Strong Kings
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
by: Carbonnel, Clément
Published: (2026)

Infinitely growing configurations in Emil Post's tag system problem
by: Kurilenko, Nikita V.
Published: (2021)

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

Combinatorial refinement on circulant graphs
by: Kluge, Laurence
Published: (2022)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

On full-separating sets and related codes in graphs
by: Chakraborty, Dipayan, et al.
Published: (2024)

A structural description of Zykov and Blanche Descartes graphs
by: Marin, Malory, et al.
Published: (2024)

Temporal Reachability Dominating Sets: contagion in temporal graphs
by: Kutner, David C., et al.
Published: (2023)

Complexity results for a cops and robber game on directed graphs
by: Ben-Ameur, Walid, et al.
Published: (2024)

On the hardness of recognizing graphs of small mim-width and its variants
by: la Tour, Max Dupré, et al.
Published: (2025)

Algorithmic methods of finite discrete structures. Graph clique problem
by: Kurapov, Sergey, et al.
Published: (2024)

CMSO-transducing tree-like graph decompositions
by: Campbell, Rutger, et al.
Published: (2024)

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

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
by: Foucaud, Florent, et al.
Published: (2023)

Edge-Disjoint Paths in Eulerian Digraphs
by: Cavallaro, Dario, et al.
Published: (2024)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Computational complexity of the Weisfeiler-Leman dimension
by: Lichter, Moritz, et al.
Published: (2024)

The Parameterized Complexity of Terminal Monitoring Set
by: Aravind, N. R., et al.
Published: (2024)

Maximal Line Digraphs
by: Japhet, Quentin, et al.
Published: (2024)

Optimal Inapproximability of Promise Equations over Finite Groups
by: Butti, Silvia, et al.
Published: (2024)

Parallel Repetition for $3$-Player XOR Games
by: Bhangale, Amey, et al.
Published: (2024)

Complexity of Boolean automata networks under block-parallel update modes
by: Perrot, Kévin, et al.
Published: (2024)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
by: Armand, Jules, et al.
Published: (2025)

On the enumeration of Tarski fixed points
by: Müller, Julian
Published: (2023)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

Gap Preserving Reductions Between Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2022)

Gap Amplification for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2023)

Is Graph Local Complementation Inherently Sequential?
by: Concha-Vega, Pablo
Published: (2025)

An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
by: Marcille, Clara, et al.
Published: (2026)

Enumerating Minimal Defensive Alliances
by: Feng, Zhidan, et al.
Published: (2023)

Counting Subgraphs in Somewhere Dense Graphs
by: Bressan, Marco, et al.
Published: (2022)

How to Reconfigure Your Alliances
by: Fernau, Henning, et al.
Published: (2025)

List Decoding Quotient Reed-Muller Codes
by: Gotlib, Omri, et al.
Published: (2025)

Property Testing in Bounded Degree Hypergraphs
by: Aaronson, Hugo, et al.
Published: (2025)