The set cover conjecture and subgraph isomorphism with a tree pattern

DOI10.4230/LIPICS.STACS.2019.45MaRDI QIDQ5090495zbMATH OpenFDO

Authors Robert Krauthgamer, Ohad Trabelsi

Publication date 18 July 2022

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

zbMATH Keywords

conditional lower boundshardness in Pset cover conjecturesubgraph isomorphism

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Subtree isomorphism revisited
• Subtree isomorphism revisited
• On star-cover and path-cover of a tree
• A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
• Exact algorithms and applications for tree-like Weighted Set Cover

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• Below all subsets for some permutational counting problems
• Color-coding
• Constrained multilinear detection and generalized graph motifs
• Determinant sums for undirected Hamiltonicity
• Dynamic Parameterized Problems
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
• Faster algorithms for subgraph isomorphism of k-connected partial k-trees
• Finding large set covers faster via the representation method
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3156818 (Why is no real title available?)
• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• LIMITS and applications of group algebras for parameterized problems
• Matching theory
• Matching triangles and basing hardness on an extremely popular conjecture
• Narrow sieves for parameterized paths and packings
• On finding rainbow and colorful paths
• On problems as hard as CNF-SAT
• On the complexity of k-SAT
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• On the equivalence among problems of bounded width
• Partitioning into sets of bounded cardinality
• Reducibility among combinatorial problems
• Set partitioning via inclusion-exclusion
• SETH-based lower bounds for subset sum and bicriteria path
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• The parity of set systems under random restrictions with applications to exponential time problems
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Which problems have strongly exponential complexity?

Cited in

(4)

• Parameterized pre-coloring extension and list coloring problems
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• On connections between k-coloring and Euclidean k-means

This page was built for publication: The set cover conjecture and subgraph isomorphism with a tree pattern

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090495)