Document Open Access Logo

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

Authors Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2016.13.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • parameterized complexity
  • graph automorphism
  • fixing number
  • base size
  • individualization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

In this paper we study the complexity of the following problems:

1. Given a colored graph X=(V,E,c), compute a minimum cardinality set of vertices  S (subset of V) such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S for a permutation group G <= S_n given by generators, i.e., a minimum cardinality subset S of [n] such that no nontrivial permutation in G fixes all elements of S. Our focus is mainly on the parameterized complexity of these problems. We show that when k=|S| is treated as parameter, then both problems are MINI[1]-hard. For the dual problems, where k=n-|S| is the parameter, we give FPT~algorithms.

2. A notion closely related to fixing is called individualization. Individualization combined with the Weisfeiler-Leman procedure is a fundamental technique in algorithms for Graph Isomorphism. Motivated by the power of individualization, in the present paper we explore the complexity of individualization: what is the minimum number of vertices we need to individualize in a given graph such that color refinement "succeeds" on it. Here "succeeds" could have different interpretations, and we consider the following: It could mean the individualized graph becomes: (a) discrete, (b) amenable, (c)compact, or (d) refinable. In particular, we study the parameterized versions of these problems where the parameter is the number of vertices individualized. We show a dichotomy: For graphs with color classes of size at most 3 these problems can be solved in polynomial time, while starting from color class size 4 they become W[P]-hard.

Cite As Get BibTex

Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.13

Author Details

Vikraman Arvind
Frank Fuhlbrück
Johannes Köbler
Sebastian Kuhnert
Gaurav Rattan

References

  1. Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. \journalnameAnnals of Pure and Applied LogicAnn. Pure Appl. Logic, 73(3):235-276, 1993. URL: http://dx.doi.org/10.1016/0168-0072(94)00034-Z.
  2. V. Arvind. The parameterized complexity of fixpoint free elements and bases in permutation groups. In \proceedings8thInternational Symposium on Parameterized and Exact ComputationIPEC, pages 4-15. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_2.
  3. V. Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan. The parameterized complexity of fixing number and vertex individualization in graphs. https://arxiv.org/abs/1606.04383, 2016.
  4. V. Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. On the power of color refinement. In \proceedings20thInternational Symposium Fundamentals of Computation TheoryFCT, pages 339-350. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-22177-9_26.
  5. V. Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. On Tinhofer’s linear programming approach to isomorphism testing. In \proceedings40thInternational Symposium on Mathematical Foundations of Computer ScienceMFCS, pages 26-37. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48054-0_3.
  6. László Babai. Graph Isomorphism in quasipolynomial time. https://arxiv.org/abs/1512-03547, 2015.
  7. László Babai and Eugene M. Luks. Canonical labeling of graphs. In \proceedings15thAnnual ACM Symposium on Theory of ComputingSTOC, pages 171-183, 1983. URL: http://dx.doi.org/10.1145/800061.808746.
  8. Robert F. Bailey and Peter J. Cameron. Base size, metric dimension and other invariants of groups and graphs. \journalnameBulletin of the London Mathematical SocietyBull. London Math. Soc., 43(2):209-242, 2011. URL: http://dx.doi.org/10.1112/blms/bdq096.
  9. Kenneth D. Blaha. Minimum bases for permutation groups: The greedy approximation. \journalnameJournal of AlgorithmsJ. Algor., 13(2):297-306, 1992. URL: http://dx.doi.org/10.1016/0196-6774(92)90020-D.
  10. Debra L. Boutin. Identifying graph automorphisms using determining sets. \journalnameElectronic Journal of CombinatoricsElectr. J. Combin., 13:R78, 2006. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r78.
  11. Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. \journalnameCombinatoricaCombin., 12(4):389-410, 1992. URL: http://dx.doi.org/10.1007/BF01305232.
  12. Liming Cai and David Juedes. On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences, 67(4):789-807, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00074-6.
  13. John D. Dixon and Brian Mortimer. Permutation groups. Springer, 1996. URL: http://dx.doi.org/10.1007/978-1-4612-0731-3.
  14. Rodney G. Downey, Vladimir Estivill-Castro, Michael R. Fellows, Elena Prieto, and Frances A. Rosamund. Cutting up is hard to do: The parameterised complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science, 78:209-222, 2003. URL: http://dx.doi.org/10.1016/S1571-0661(04)81014-4.
  15. David Erwin and Frank Harary. Destroying automorphisms by fixing nodes. \journalnameDiscrete MathematicsDiscrete Math., 306(24):3244-3252, 2006. URL: http://dx.doi.org/10.1016/j.disc.2006.06.004.
  16. Gašper Fijavž and Bojan Mohar. Rigidity and separation indices of paley graphs. \journalnameDiscrete MathematicsDiscrete Math., 289(1-3):157-161, 2004. URL: http://dx.doi.org/10.1016/j.disc.2004.09.004.
  17. Martin Grohe. Equivalence in finite-variable logics is complete for polynomial time. \journalnameCombinatoricaCombin., 19(4):507-532, 1999. URL: http://dx.doi.org/10.1007/s004939970004.
  18. Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán. Completeness results for graph isomorphism. Journal of Computer and System Sciences, 66(3):549-566, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00042-4.
  19. Eugene M. Luks. Permutation groups and polynomial-time computation. In Groups and Computation, pages 139-175. American Mathematical Society, 1993. URL: http://www.cs.uoregon.edu/~luks/dimacs.pdf.
  20. Rudolf Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131-136, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90004-8.
  21. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. \journalnameJournal of Symbolic ComputationJ. Symb. Comput., 60:94-112, 2014. URL: http://dx.doi.org/10.1016/j.jsc.2013.09.003.
  22. Joanna Raczek. Distance paired domination numbers of graphs. \journalnameDiscrete MathematicsDiscrete Math., 308(12):2473-2483, 2008. URL: http://dx.doi.org/10.1016/j.disc.2007.05.018.
  23. Omer Reingold. Undirected st-connectivity in log-space. In \proceedings37thAnnual ACM Symposium on Theory of ComputingSTOC, pages 376-385, 2005. URL: http://dx.doi.org/10.1145/1060590.1060647.
  24. Pascal Schweitzer. Isomorphism of (mis)labeled graphs. In \proceedings19thEuropean Symposium on AlgorithmsESA, pages 370-381, Berlin, 2011. Springer. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_32.
  25. Gottfried Tinhofer. A note on compact graphs. \journalnameDiscrete Applied MathematicsDiscrete Appl. Math., 30(2-3):253-264, 1991. URL: http://dx.doi.org/10.1016/0166-218X(91)90049-3.
  26. Luca Trevisan. Non-approximability results for optimization problems on bounded degree instances. In \proceedings33rdAnnual ACM Symposium on Theory of ComputingSTOC, pages 453-461. ACM, 2001. URL: http://dx.doi.org/10.1145/380752.380839.
  27. Viktor N. Zemlyachenko, Nikolay M. Kornienko, and Regina I. Tyshkevich. Graph isomorphism problem. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta, 118:83-158, 1982. Russian. Translation to English: [28]. Google Scholar
  28. Viktor N. Zemlyachenko, Nikolay M. Kornienko, and Regina I. Tyshkevich. Graph isomorphism problem. \journalnameJournal of Mathematical SciencesJ. Math. Sci., 29(4):1426-1481, 1985. English translation of [27]. URL: http://dx.doi.org/10.1007/BF02104746.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact