Gaurav Rattan

In this paper we study the algorithmic complexity of the following problems: (1) Given a vertex-colored graph X = (V,E,c) , compute a minimum cardinality set of vertices S⊆ 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 ≤ Sym( n ) given by generators, i.e., a minimum cardinality subset S ⊆ [ 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 related to fixing is individualization, which is a useful technique combined with the Weisfeiler-Leman procedure in algorithms for Graph Isomorphism. We explore the complexity of individualization: the problem of computing the minimum number of vertices we need to individualize in a given graph such that color refinement results in a graph with useful structural properties in the context of Graph Isomorphism and the Weisfeiler-Leman procedure.