On the complexity of fixed parameter clique and dominating set

DOI10.1016/J.TCS.2004.05.009zbMATH Open1071.68030OpenAlexW1973113631WikidataQ56210401 ScholiaQ56210401MaRDI QIDQ703534FDOQ703534

Authors: Friedrich Eisenbrand, Fabrizio Grandoni 

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

Recommendations

• On the parameterized complexity of approximating dominating set
• On the Parameterized Complexity of Approximating Dominating Set
• On hardness of approximating the parameterized clique problem
• Parameterized approximation of dominating set problems
• Exact algorithms for dominating clique problems (extended abstract)
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• scientific article; zbMATH DE number 1617251
• The parameterized complexity of dominating set and friends revisited for structured graphs
• Parameterized complexity of minimum membership dominating set
• Parameterized complexity of minimum membership dominating set

zbMATH Keywords

Dominating setCliqueDiamonds detectionParameterized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding and counting given length cycles
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Finding and counting small induced subgraphs efficiently
• Title not available (Why is that?)
• Finding a Minimum Circuit in a Graph
• Title not available (Why is that?)
• Fast rectangular matrix multiplication and applications
• On Syntactic versus Computational Views of Approximability
• Rectangular matrix multiplication revisited
• Algorithms and Data Structures

Cited In (46)

• A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
• Title not available (Why is that?)
• On the Parameterized Complexity of Approximating Dominating Set
• Faster algorithms for all-pairs bounded min-cuts
• Title not available (Why is that?)
• When can graph hyperbolicity be computed in linear time?
• Open problems around exact algorithms
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Efficient algorithms for clique problems
• Detecting and counting small pattern graphs
• Unique subgraphs are not easier to find
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• If the current clique algorithms are optimal, so is Valiant's parser
• Map graphs having witnesses of large girth
• Algorithms for dominating clique problems
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• A faster interior-point method for sum-of-squares optimization
• Tensor network complexity of multilinear maps
• Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Arboricity, \(h\)-index, and dynamic algorithms
• Counting connected subgraphs with maximum-degree-aware sieving
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
• Finding small complete subgraphs efficiently
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Intersection graphs of non-crossing paths
• Beating treewidth for average-case subgraph isomorphism
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• On linear algebraic algorithms for the subgraph matching problem and its variants
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Detecting and enumerating small induced subgraphs in \(c\)-closed graphs
• Finding and counting small tournaments in large tournaments
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• Exact weight subgraphs and the \(k\)-sum conjecture
• The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
• On approximating the number of \(k\)-cliques in sublinear time
• On the query complexity of clique size and maximum satisfiability
• Counting Subgraphs in Degenerate Graphs
• Counting subgraphs in relational event graphs
• Are unique subgraphs not easier to find?
• On the first-order complexity of induced subgraph isomorphism
• Hardness of RNA folding problem with four symbols
• Faster combinatorial \(k\)-clique algorithms
• Streaming deletion problems Parameterized by vertex cover

This page was built for publication: On the complexity of fixed parameter clique and dominating set

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