The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

ACM Transactions on Computation Theory, vol. 14, pp. 1–26

Abstract

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.

Authors 5

1. V. Arvind

   Institute of Mathematical Sciences

   Affiliation as printed

   Institute of Mathematical Sciences (HBNI), Taramani, Chennai, India

2. Frank Fuhlbrück

   Humboldt-Universität zu Berlin

   Affiliation as printed

   Humboldt-Universität zu Berlin, Berlin, Germany

3. Johannes Köbler

   Humboldt-Universität zu Berlin

   Affiliation as printed

   Humboldt-Universität zu Berlin, Berlin, Germany

4. Sebastian Kuhnert

   Humboldt-Universität zu Berlin

   Affiliation as printed

   Humboldt-Universität zu Berlin, Berlin, Germany

5. Gaurav Rattan Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany