article

On the complexity of fixed parameter clique and dominating set

Authors:

Friedrich Eisenbrand,

Fabrizio GrandoniAuthors Info & Claims

Theoretical Computer Science, Volume 326, Issue 1-3

Pages 57 - 67

https://doi.org/10.1016/j.tcs.2004.05.009

Published: 20 October 2004 Publication History

Abstract

We provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. Our algorithms are based on reductions to rectangular matrix multiplication. We also describe an improved algorithm for diamonds detection.

References

[1]

{1} N. Alon, R. Yuster, U. Zwick, Finding and counting given length cycles, Algorithmica 17 (3) (1997) 209-223.

Crossref

Google Scholar

[2]

{2} B. Bollobás, Extremal Graph Theory, in: London Mathematical Society Monographs, Vol. 11, Academic Press {Harcourt Brace Jovanovich Publishers}, London, 1978.

Digital Library

Google Scholar

[3]

{3} D. Coppersmith, Rectangular matrix multiplication revisited, J. Complexity 13 (1997) 42-49.

Digital Library

Google Scholar

[4]

{4} D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (3) (1990) 251-280.

Digital Library

Google Scholar

[5]

{5} R. Downey, Parameterized complexity for the skeptic, in: IEEE Annu. Conf. on Computational Complexity, 2003, pp. 147-170.

Google Scholar

[6]

{6} R.G. Downey, M.R. Fellows, Fixed-parameter tractability and completeness. II. On completeness for W{1}, Theoret. Comput. Sci. 141 (1-2) (1995) 109-131.

Digital Library

Google Scholar

[7]

{7} R.G. Downey, M.R. Fellows, Parameterized Complexity, Monographs in Computer Science, Springer, Berlin, 1999.

Google Scholar

[8]

{8} P. Erdös, On the number of complete subgraphs contained in certain graphs, Magyar Tudomanyos Akad. Mat. Kutató Intezetenek Közl. 7 (1962) 459-464.

Google Scholar

[9]

{9} M.R. Fellows, New directions and new challenges in algorithm design and complexity, parameterized, in: Workshop on Algorithms and Data Structures, 2003, pp. 505-519.

Google Scholar

[10]

{10} M.R. Garey, D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, Freemann, New York, 1979.

Digital Library

Google Scholar

[11]

{11} J. Håstad, Clique is hard to approximate within n1-ε, Acta Math. 182 (1) (1998) 105-142.

Crossref

Google Scholar

[12]

{12} X. Huang, V. Pan, Fast rectangular matrix multiplication and applications, J. Complexity 14 (2) (1998) 257-299.

Digital Library

Google Scholar

[13]

{13} A. Itai, M. Rodeh, Finding a minimum circuit in a graph, SIAM J. Comput. 7 (4) (1978) 413-423.

Crossref

Google Scholar

[14]

{14} S. Khanna, R. Motwani, M. Sudan, U. Vazirani, On syntactic versus computational views of approximability, SIAM J. Comput. 28 (1) (1999) 164-191.

Digital Library

Google Scholar

[15]

{15} T. Kloks, D. Kratsch, H. Müller, Finding and counting small induced subgraphs efficiently, Inform. Process. Lett. 74 (3-4) (2000) 115-121.

Digital Library

Google Scholar

[16]

{16} J. Nešetřil, S. Poljak, On the complexity of the subgraph problem, Commentationes Mathematicae Universitatis Carolinae 26 (2) (1985) 415-419.

Google Scholar

[17]

{17} R. Raz, S. Safra, A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP, in: ACM Symp. on the Theory of Computing, 1997, pp. 475-484.

Digital Library

Google Scholar

[18]

{18} K.W. Regan, Finitary substructure languages, in: Structure in Complexity Theory Conference, 1989, pp. 87-96.

Google Scholar

Cited By

View all

Yuster R(2025)Finding and counting small tournaments in large tournamentsTheoretical Computer Science10.1016/j.tcs.2024.1149111024:COnline publication date: 12-Jan-2025
https://dl.acm.org/doi/10.1016/j.tcs.2024.114911
Abboud AFischer NKelley ZLovett SMeka RMohar BShinkar IO'Donnell R(2024)New Graph Decompositions and Combinatorial Boolean Matrix Multiplication AlgorithmsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649696(935-943)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649696
Dalirrooyfard MMathialagan SWilliams VXu YMohar BShinkar IO'Donnell R(2024)Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller CliquesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649663(923-934)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649663
Show More Cited By

Index Terms

On the complexity of fixed parameter clique and dominating set
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K"1","3, the complete bipartite graph on four vertices where the two parts have one and three vertices, ...
Edge dominating set and colorings on graphs with fixed clique-width

We consider both the vertex and the edge versions of three graph partitioning problems. These problems are dominating set, list-q-coloring with costs (fixed number of colors q) and chromatic number. They are all known to be NP-hard in general. We show ...
The complexity of dominating set reconfiguration

Suppose that we are given two dominating sets D s and D t of a graph G whose cardinalities are at most a given threshold k. Then, we are asked whether there exists a sequence of dominating sets of G between D s and D t such that each dominating set in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 326, Issue 1-3

20 October 2004

433 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 20 October 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yuster R(2025)Finding and counting small tournaments in large tournamentsTheoretical Computer Science10.1016/j.tcs.2024.1149111024:COnline publication date: 12-Jan-2025
https://dl.acm.org/doi/10.1016/j.tcs.2024.114911
Abboud AFischer NKelley ZLovett SMeka RMohar BShinkar IO'Donnell R(2024)New Graph Decompositions and Combinatorial Boolean Matrix Multiplication AlgorithmsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649696(935-943)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649696
Dalirrooyfard MMathialagan SWilliams VXu YMohar BShinkar IO'Donnell R(2024)Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller CliquesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649663(923-934)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649663
Wang H(2024)On the Fine-Grained Complexity of Approximating Max k-CoverageFrontiers of Algorithmics10.1007/978-981-97-7752-5_6(79-93)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-7752-5_6
Abboud AFischer NShechter Y(2024)Faster Combinatorial k-Clique AlgorithmsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_13(193-206)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-55598-5_13
Oostveen Jvan Leeuwen E(2023)Streaming deletion problems parameterized by vertex coverTheoretical Computer Science10.1016/j.tcs.2023.114178979:COnline publication date: 10-Nov-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.114178
Chaplick S(2023)Intersection graphs of non-crossing pathsDiscrete Mathematics10.1016/j.disc.2023.113498346:8Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.disc.2023.113498
Jiang SNatura BWeinstein O(2023)A Faster Interior-Point Method for Sum-of-Squares OptimizationAlgorithmica10.1007/s00453-023-01112-485:9(2843-2884)Online publication date: 11-Apr-2023
https://dl.acm.org/doi/10.1007/s00453-023-01112-4
Dumitrescu ALingas A(2023)Finding Small Complete Subgraphs EfficientlyCombinatorial Algorithms10.1007/978-3-031-34347-6_16(185-196)Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-34347-6_16
Karthik CKhot S(2022)Almost polynomial factor inapproximability for parameterized k-cliqueProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.6(1-21)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.6
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Dominating set is fixed parameter tractable in claw-free graphs

Edge dominating set and colorings on graphs with fixed clique-width

The complexity of dominating set reconfiguration

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations