On the complexity of fixed parameter clique and dominating set
From MaRDI portal
Publication:703534
DOI10.1016/J.TCS.2004.05.009zbMath1071.68030OpenAlexW1973113631WikidataQ56210401 ScholiaQ56210401MaRDI QIDQ703534
Fabrizio Grandoni, Friedrich Eisenbrand
Publication date: 11 January 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.05.009
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (41)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs ⋮ Map graphs having witnesses of large girth ⋮ Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Exact Weight Subgraphs and the k-Sum Conjecture ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ A faster interior-point method for sum-of-squares optimization ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Arboricity, \(h\)-index, and dynamic algorithms ⋮ On linear algebraic algorithms for the subgraph matching problem and its variants ⋮ Unnamed Item ⋮ Finding small complete subgraphs efficiently ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Are unique subgraphs not easier to find? ⋮ Hardness of RNA folding problem with four symbols ⋮ A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ A fast deterministic detection of small pattern graphs in graphs without large cliques ⋮ Open problems around exact algorithms ⋮ Unnamed Item ⋮ Detecting and Counting Small Pattern Graphs ⋮ Algebraic methods in the congested clique ⋮ Efficient algorithms for clique problems ⋮ Intersection graphs of non-crossing paths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Counting Subgraphs in Relational Event Graphs ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Detecting and enumerating small induced subgraphs in \(c\)-closed graphs ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Logical complexity of induced subgraph isomorphism for certain families of graphs ⋮ Unique subgraphs are not easier to find ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Finding and counting given length cycles
- Matrix multiplication via arithmetic progressions
- Fast rectangular matrix multiplication and applications
- Rectangular matrix multiplication revisited
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Finding a Minimum Circuit in a Graph
- On Syntactic versus Computational Views of Approximability
- Algorithms and Data Structures
This page was built for publication: On the complexity of fixed parameter clique and dominating set
