@InProceedings{AFKKR16,
  author =       {V. Arvind and Frank Fuhlbrück and Johannes Köbler
                  and Sebastian Kuhnert and Gaurav Rattan},
  title =        {The parameterized complexity of fixing number and
                  vertex individualization in graphs},
  year =         2016,
  booktitle =    {Mathematical Foundations of Computer Science
                  (Proceedings of MFCS 2016)},
  editor =       {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  series =       {LIPIcs},
  number =       58,
  publisher =    {Leibniz-Zentrum für Informatik},
  location =     {Dagstuhl},
  isbn =         {978-3-95977-016-3},
  pages =        {13:1--13:14},
  doi =          {10.4230/LIPIcs.MFCS.2016.13},
}

The parameterized complexity of fixing number and vertex individualization in graphs.
With V. Arvind, Frank Fuhlbrück, Johannes Köbler, Gaurav Rattan.
Mathematical Foundations of Computer Science (Proceedings of 41st MFCS). LIPIcs 58, 2016.

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.