Imagen de Portada

Graph Homomorphism, Monotone Classes and Bounded Pathwidth

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Eagling-Vose, Tala, Martin, Barnaby, Paulusma, Daniel, Smith, Siani
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Logic in Computer Science
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
por: Eagling-Vose, Tala, et al.
Publicado: (2025)

Finding d-Cuts in Claw-free Graphs
por: Ahn, Jungho, et al.
Publicado: (2025)

On Detecting $H$-Induced Minors for Small $H$
por: Eagling-Vose, Tala, et al.
Publicado: (2026)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
por: Eagling-Vose, Tala, et al.
Publicado: (2025)

The complete classification for quantified equality constraints
por: Zhuk, Dmitriy, et al.
Publicado: (2021)

Finding $d$-Cuts in Probe $H$-Free Graphs
por: Dabrowski, Konrad K., et al.
Publicado: (2025)

First Order Logic on Pathwidth Revisited Again
por: Lampis, Michael
Publicado: (2022)

Steiner Forest for $H$-Subgraph-Free Graphs
por: Eagling-Vose, Tala, et al.
Publicado: (2026)

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
por: Ahn, Jungho, et al.
Publicado: (2026)

Restricted CSPs and F-free Digraph Algorithmics
por: Guzmán-Pro, Santiago, et al.
Publicado: (2025)

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
por: de Rezende, Susanna F., et al.
Publicado: (2024)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
por: Dwivedi, Prateek, et al.
Publicado: (2026)

Uniformity within Parameterized Circuit Classes
por: Hegeman, Steef, et al.
Publicado: (2025)

Testing for Renamability to Classes of Clause Sets
por: Brandl, Albert, et al.
Publicado: (2025)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
por: Lucke, Felicia, et al.
Publicado: (2024)

Optimal Lower Bounds for Symmetric Modular Circuits
por: Pago, Benedikt
Publicado: (2026)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
por: Roberson, David E., et al.
Publicado: (2023)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
por: Seppelt, Tim
Publicado: (2024)

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
por: Chen, Lijie, et al.
Publicado: (2024)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
por: Li, Jiawei, et al.
Publicado: (2024)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
por: Seppelt, Tim
Publicado: (2023)

A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation
por: Krinkin, Kirill
Publicado: (2026)

Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations
por: Antonelli, Melissa, et al.
Publicado: (2025)

Automated Reencoding Meets Graph Theory
por: Przybocki, Benjamin, et al.
Publicado: (2026)

Dynamic Planar Graph Isomorphism is in DynFO
por: Datta, Samir, et al.
Publicado: (2026)

New Bounds for the Ideal Proof System in Positive Characteristic
por: Behera, Amik Raj, et al.
Publicado: (2025)

The Descriptive Complexity of Graph Neural Networks
por: Grohe, Martin
Publicado: (2023)

Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
por: Berkholz, Christoph, et al.
Publicado: (2024)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
por: Nechesov, Andrey
Publicado: (2024)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
por: Atserias, Albert, et al.
Publicado: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
por: Zhuk, Dmitriy
Publicado: (2024)

Proof Complexity of Linear Logics
por: Tabatabai, Amirhossein Akbar, et al.
Publicado: (2026)

An order out of nowhere: a new algorithm for infinite-domain CSPs
por: Mottet, Antoine, et al.
Publicado: (2023)

The Proof Analysis Problem
por: Arteche, Noel, et al.
Publicado: (2025)

Proof complexity of positive branching programs
por: Das, Anupam, et al.
Publicado: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
por: Ježil, Ondřej, et al.
Publicado: (2026)

Effective Versions of Strong Measure Zero
por: Rayman, Matthew
Publicado: (2025)

Meta-Mathematics of Computational Complexity Theory
por: Oliveira, Igor C.
Publicado: (2025)

On the consistency of stronger lower bounds for NEXP
por: Thapen, Neil
Publicado: (2025)

Graph Homomorphisms and Universal Algebra
por: Bodirsky, Manuel
Publicado: (2026)