scientific article; zbMATH DE number 7378610

DOI10.4230/LIPIcs.IPEC.2018.24zbMath1502.68135arXiv1807.01920MaRDI QIDQ5009487

Johannes Schmitt, Marc Roth

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1807.01920

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Euler characteristicsimplicial complexeshomomorphismsparameterized complexitycounting complexity

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of simplicial complexes (05E45) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ Unnamed Item

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The complexity of counting homomorphisms seen from the other side
• Strong computational lower bounds via parameterized complexity
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Fixed-point sets of group actions on finite acyclic complexes
• On recognizing graph properties from adjacency matrices
• The parameterised complexity of counting even and odd induced subgraphs
• Some results related to the evasiveness conjecture.
• The parameterised complexity of counting connected subgraphs and graph motifs
• Simplicial complexes of graphs
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• Evasiveness of Subgraph Containment and Related Properties
• Some Hard Families of Parameterized Counting Problems
• Evasiveness of Graph Properties and Topological Fixed-Point Theorems
• Understanding the Complexity of Induced Subgraph Isomorphisms
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• On the Structure of Polynomial Time Reducibility
• The on-line encyclopedia of integer sequences
• The Parameterized Complexity of Counting Problems
• Homomorphisms are a good basis for counting small subgraphs
• Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
• Fixed-Point Theorems for Periodic Transformations

This page was built for publication: