Can I read The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs on EtoBox?

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs by Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Kuhnert, Sebastian; Rattan, Gaurav is a scholarly article available to read on EtoBox.

What is The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs about?

In this paper we study the complexity of the following problems: Given a colored graph X=(V,E,c), compute a minimum cardinality set S of vertices 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 on [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. 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 t

Author

Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Kuhnert, Sebastian; Rattan, Gaurav

Published

2016

Language

EN