Cover Image

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Paul-Pena, Daniel, Seshadhri, C.
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
by: Paul-Pena, Daniel, et al.
Published: (2025)

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
by: Bentert, Matthias, et al.
Published: (2026)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

Temporal Graph Realization With Bounded Stretch
by: Mertzios, George B., et al.
Published: (2025)

A Dichotomy for Maximum PCSPs on Graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)

Optimal Padded Decomposition For Bounded Treewidth Graphs
by: Filtser, Arnold, et al.
Published: (2024)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
by: Abbasi, Ali, et al.
Published: (2026)

The Complexity of Homomorphism Reconstruction Revisited
by: Gervens, Timo, et al.
Published: (2026)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Spectral Triadic Decompositions of Real-World Networks
by: Basu, Sabyasachi, et al.
Published: (2022)

An Approximate Generalization of the Okamura-Seymour Theorem
by: Kumar, Nikhil
Published: (2022)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
by: de Montgolfier, Fabien, et al.
Published: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Determining Implication of Fixed Matrix Prenex Normal Forms Can Be Decided in Linear Time
by: Wang, Adam
Published: (2025)

Counting random $k$-SAT near the satisfiability threshold
by: Chen, Zongchen, et al.
Published: (2024)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
by: Ghanbari, Babak, et al.
Published: (2026)

Algorithmic Results for Weak Roman Domination Problem in Graphs
by: Paul, Kaustav, et al.
Published: (2024)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
by: Lill, Jonas, et al.
Published: (2024)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
by: Hamm, Thekla, et al.
Published: (2022)

Graph Visualization for Blockchain Data
by: Dietl, Marcell, et al.
Published: (2024)

Lower Bounds for Linear Operators
by: Ko, Young Kun
Published: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
by: Dahan, Anatole, et al.
Published: (2026)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

Fanciful Figurines flip Free Flood-It -- Polynomial-Time Miniature Painting on Co-gem-free Graphs
by: Rosenke, Christian, et al.
Published: (2026)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
by: Bourneuf, Romain, et al.
Published: (2025)

A Sublinear Algorithm for Approximate Shortest Paths in Large Networks
by: Basu, Sabyasachi, et al.
Published: (2024)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
by: Jordon, Addie, et al.
Published: (2025)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
by: Swamy, Chaitanya, et al.
Published: (2025)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
by: Harada, Tsubasa
Published: (2024)

Online Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

On the Relationship Between Several Variants of the Linear Hashing Conjecture
by: Westover, Alek
Published: (2023)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
by: Klimm, Max, et al.
Published: (2022)