*BibTeX*

@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.