Eva Jelínková

† Ondřej Suchý
email: suchy@mmci.uni-saarland.de

Petr Hliněný
email: hlineny@fi.muni.cz

Jan Kratochvíl

Parameterized Problems Related to Seidel's Switching

Keywords: Seidel's Switching, Computational Complexity, Parameterized Complexity

Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches.

In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most k edges, to a graph of maximum degree at most k, to a k-regular graph, or to a graph with minimum degree at least k are fixed parameter tractable problems, where k is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is W [1]-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. A consequence of the latter result is the NP-completeness of Maximum Likelihood Decoding of graph theoretic codes based on complete graphs.

Introduction

The concept of Seidel's switching (for a formal definition, see Subsection 2.2) was introduced by a Dutch mathematician J. J. Seidel in connection with regular structures, such as systems of equiangular lines, strongly regular graphs, or the so-called two-graphs. For more structural properties of two-graphs, cf. [START_REF] Seidel | Graphs and two-graphs[END_REF][START_REF] Seidel | A survey of two-graphs[END_REF][START_REF] Seidel | Two-graphs, a second survey[END_REF]. Since then, switching has been studied by many others. Apart from the algebraic structures, consequences of switching arise in other research fields as well; for example, Seidel's switching plays an important role in Hayward's polynomial-time algorithm for solving the P 3 -structure recognition problem [START_REF] Hayward | Recognizing P 3 -structure: A switching approach[END_REF].

As proved by Colbourn and Corneil [START_REF] Colbourn | On deciding switching equivalence of graphs[END_REF] (and independently by Kratochvíl et al. [START_REF] Kratochvíl | On the computational complexity of Seidel's switching[END_REF]), deciding whether two given graphs are switching-equivalent is an isomorphism-complete problem.

Several authors have considered the complexity of deciding if a given graph can be switched to a graph having some particular property. It was noted already in [START_REF] Kratochvíl | On the computational complexity of Seidel's switching[END_REF] that the complexity of such problems is in no correlation with the complexity of the property itself: Kratochvíl et al. [START_REF] Kratochvíl | On the computational complexity of Seidel's switching[END_REF] proved that any graph is switching-equivalent to a graph containing a Hamiltonian path, and it is polynomial to decide if a graph is switching-equivalent to a graph containing a Hamiltonian cycle (as proved also by Ehrenfeucht et al. [START_REF] Ehrenfeucht | Pancyclicity in switching classes[END_REF]). However, the problems to decide if a graph itself contains a Hamiltonian path or cycle are well known to be NP-complete [START_REF] Garey | Computers and Intractability, A guide to the Theory of NP-Completeness[END_REF]. On the other hand, Kratochvíl [START_REF] Kratochvíl | Complexity of hypergraph coloring and Seidel's switching[END_REF] showed NPcompleteness of deciding if a given graph can be switched to a regular one, while deciding if a given graph is regular is obviously polynomial-time solvable. Somewhat surprisingly, the above mentioned switching to a regular graph, and switching to a graph with large clique number remain until today the only nontrivial hard cases.

Polynomial-time algorithms are known for switching to a triangle-free graph [START_REF] Hayward | Recognizing P 3 -structure: A switching approach[END_REF][START_REF] Hage | Euler graphs, triangle-free graphs and bipartite graphs in switching classes[END_REF], to a claw-free graph [START_REF] Jelínková | On switching to H-free graphs[END_REF], to an eulerian graph [START_REF] Hage | Euler graphs, triangle-free graphs and bipartite graphs in switching classes[END_REF], to a bipartite graph [START_REF] Hage | Euler graphs, triangle-free graphs and bipartite graphs in switching classes[END_REF], and to a planar graph [START_REF] Ehrenfeucht | Complexity issues in switching of graphs[END_REF][START_REF] Kratochvíl | Complexity of hypergraph coloring and Seidel's switching[END_REF].

In this paper, we initiate the study of the complexity of Seidel's switching from the Fixed Parameter Complexity point of view. The polynomial algorithm for testing switchability to a planar graph is based on the existence of a vertex of degree at most 5 in any planar graph. This naturally suggests to consider the problem of switching to a k-degenerate graph. For fixed k, the problem is solvable in time O(n k+3 ) [START_REF] Ehrenfeucht | Complexity issues in switching of graphs[END_REF], but the fixed-parameter complexity, when parameterized by k, is still open. We determine the fixed-parameter complexity of several closely related variants: we prove that switching to a graph of maximum degree at most k is fixed parameter tractable, as well as of switching to a graph of minimum degree at least k, and of switching to a k-regular graph. All these results are presented in Section 3.

It is easy to see that every graph with n vertices can be switched to a graph with maximum degree at most n/2. Indeed, consider a switching-equivalent graph with the minimum number of edges; switching a vertex of degree greater than n/2 would reduce the number of edges. This argument also gives an algorithm for constructing a switch with all degrees at most n/2. However, this does not provide a polynomial-time algorithm for constructing the switch with minimum number of edges. And indeed, answering a long standing open problem [START_REF] Hage | Structural Aspects Of Switching Classes[END_REF], we prove in Section 4 that deciding if a given graph can be switched to a graph with at most k edges is NP-complete. We also show a connection to coding theory in Subsection 4.2. Of course, a graph with at most k edges has all vertex degrees also at most k, and hence it is not surprising that from the Fixed Parameter Complexity point of view this question is easy. We will describe an FPT algorithm with a considerably better running time in Subsection 4.3.

Switching to a graph containing a large clique is another computationally difficult problem. It was shown NP-complete in [START_REF] Ehrenfeucht | Complexity issues in switching of graphs[END_REF]. We show in Section 5 that switching to a graph with ω(G) ≥ cn is NP-complete for every constant 0 < c < 1. The more involved case of irrational c is proved by applying the PCP theorem about inapproximability of the 3SAT problem. In Section 6 we show that this question is W[1]-hard when considered parameterized by the size of the clique.

Conference versions of some of the results contained in the present paper have appeared in conference proceedings [START_REF] Jelínková | Three NP-complete optimization problems in seidel's switching[END_REF] and [START_REF] Suchý | Some parametrized problems related to Seidel's switching[END_REF].

Basic Definitions

Preliminaries

In this paper, we use the standard graph theoretic notation. Unless defined otherwise, by n we denote the number of vertices of the currently discussed graph.

If G = (V, E) and A ⊆ V then G[A] denotes the graph (A, E ∩ A
2 ) induced by the vertices in A, and G denotes the complement

(V, V 2 \ E) of the graph G. The graph G = (V, V
2 ) is called a complete graph and denoted by K n . A complete subgraph on k vertices is called a k-clique. A path with n vertices is denoted by P n , and a graph with n vertices and no edges is called discrete and denoted by I n . The symmetric difference of sets A and B is denoted by A B.

A given parameterized problem is fixed-parameter tractable (FPT) with respect to a parameter k, if there is an algorithm solving the problem in f (k)•n c time for some computable function f and a constant c. Similarly, if there is an algorithm running in time n g(k) for some computable function g, then we say that the problem is in the class XP (both these notions were introduced by Downey and Fellows [START_REF] Downey | Parametrized Complexity[END_REF]).

To catch the fundamental difference between f (k) • n c and n g(k) running time, parameterized hardness theory was introduced. A parameterized problem Q is FPT-reducible to a parameterized problem Q if there exists an algorithm of running time

f (k)|x| O(1) that on an instance (x, k) of Q produces an instance (x , g(k)) of Q such that (x, k) is a YES-instance of Q if and only if (x , g(k)
) is a YES-instance of Q , where the functions f and g depend only on k. Downey and Fellows [START_REF] Downey | Parametrized Complexity[END_REF] introduced the class W[1] as the basic class of fixed-parameter intractable problems -W[1]-hard problems are believed not to have algorithms running in time f (k) • n c (otherwise, the "exponential time hypothesis" would fail). [START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for the definition of the class W[1] and more details on parameterized complexity.

A parameterized problem Q is W[1]-hard if every problem in W[1] is FPT-reducible to Q, and W[1]- complete, if it is W[1]-hard and in W[1]. See [DF99,

Seidel's Switching

Definition 2.1 Let G be a graph. Seidel's switch of a vertex v ∈ V G results in the graph called S(G, v) whose vertex set is the same as of G and the edge set is the symmetric difference of E G and the full star centered in v, i. e.,

V S(G,v) = V G E S(G,v) = E G \ {xv : x ∈ V G } ∪ {xv : x ∈ V G , x = v, xv ∈ E G }.
It is easy to observe that the result of a sequence of vertex switches in G depends only on the parity of the number of times each vertex is switched. This allows generalization of switching to vertex subsets of G.

Definition 2.2 Let G be a graph. Then Seidel's switch of a vertex subset A ⊆ V G is called S(G, A) and S(G, A) = (V G , E G {xy : x ∈ A, y ∈ V G \ A}).
We say that two graphs G and H are switching-equivalent From the case of C 4 in Fig. 1, the reader may already deduce some basic observations about Seidel's switching. Various properties, as shown in the following lemma, can be found in [START_REF] Hage | Structural Aspects Of Switching Classes[END_REF].

(denoted by G ∼ H) if there is a set A ⊆ V G such that S(G, A) is isomorphic to H. The set [G] = {S(G, A) : A ⊆ V G } is called the switching class of G.
Lemma 2.3 Let G be a graph and A, B ⊆ V two subsets of its vertices. Then

• S(G, A)[A] = G[A], • S(G, A) = S(G, V \ A), • S(G, ∅) = S(G, V ) = G, • S(S(G, A), B) = S(S(G, B), A) = S(G, A B), • S(S(G, A), A) = G, • S(G, A) = S(G, A).
Lemma 2.4 (Ehrenfeucht et al. [START_REF] Ehrenfeucht | Complexity issues in switching of graphs[END_REF]) Let G = (V, E) be a graph, u ∈ V and X ⊆ V . If u / ∈ X, then there exists a unique graph H ∈ [G] such that the neighbors of u in H are the vertices in X. Namely, it is the graph S(G, N G (v) X).

Optimizing Vertex Degrees

We examine the following problems: SWITCH-k-SMALL-DEGS Input: A graph G = (V, E), an integer k Question: Is there a subset of vertices A ⊆ V such that in the graph S(G, A), the degree of each vertex is at most k?

SWITCH-k-LARGE-DEGS

Input: A graph G = (V, E), an integer k Question: Is there a subset of vertices A ⊆ V such that in the graph S(G, A), the degree of each vertex is at least k?

SWITCH-k-REGULAR

Input: A graph G = (V, E), an integer k Question: Is there a subset of vertices A ⊆ V such that the graph S(G, A) is k-regular?

Note that there are pairs (G, k) that form a YES-instance for both SWITCH-k-SMALL-DEGS and SWITCH-k-LARGE-DEGS but a NO-instance for SWITCH-k-REGULAR, e.g. (C 4 , 1), see Fig. 1.

It is easy to see that, for every fixed k, graphs with all vertices of degrees at most k form a class to which the following general result applies, and k-regular graphs form such a class as well. The Theorem was proved by Ehrenfeucht et al. [START_REF] Ehrenfeucht | Complexity issues in switching of graphs[END_REF] and also independently (in a slightly weaker form) by Kratochvíl [START_REF] Kratochvíl | Complexity of hypergraph coloring and Seidel's switching[END_REF].

Theorem 3.1 Let P be a graph property that can be decided in time O(n a ) for an integer a. Let every graph with P contain a vertex of degree at most d(n). Then the problem if an input graph is switchingequivalent to a graph with P can be decided in time O(n d(n)+1+max(a,2) ).

In particular, Theorem 3.1 implies the existence of an O(n k+3 )-time algorithm for deciding if a given graph can be switched to a graph with all vertex degrees at most k, or to a k-regular graph.

That means that the problem SWITCH-k-REGULAR, which is known to be NP-complete [START_REF] Kratochvíl | Complexity of hypergraph coloring and Seidel's switching[END_REF], is in the class XP when considered parameterized by k. Hence it is natural to examine the parameterized complexity of the problems with respect to this obvious parameter. This is done in Subsection 3.1 for large degrees, in Subsection 3.2 for small degrees, and in Subsection 3.3 for regular graphs.

Parameterized Complexity of SWITCH-k-LARGE-DEGS

The case of SWITCH-k-LARGE-DEGS is simple due to the following folklore lemma. Lemma 3.2 Let G = (V, E) be a graph on n vertices. Then there is a set A ⊆ V G such that in the graph S(G, A), degrees of all vertices are at least n/2 . Proof: Suppose on contrary that there is no such set. Moreover assume that A 0 is such that S(G, A 0 ) has the highest number of edges among all S(G, A). Suppose v is a vertex of degree d < n/2 in S(G, A 0 ). Then switching v in S(G, A 0 ) destroys d edges while introducing nd -1 ≥ n/2 edges. Hence S(G, A 0 {v}) has more edges than S(G, A 0 ), a contradiction.

Note that we can also actually find the appropriate set in cubic time by iteratively switching the vertices of small degree, since each such iteration increases the number of edges and can be done in linear time with a suitable graph representation.

2

Corollary 3.3 SWITCH-k-LARGE-DEGS is fixed-parameter tractable-it can be decided in time O(4 k • k 2 + n).
Proof: If k ≤ n/2, then by Lemma 3.2, any graph on n vertices can be switched to a graph with all vertices of degree at least k. Hence, the answer is trivially yes.

Otherwise n < 2k, and we may solve the instance by trying all possible 2 n-1 switches of the input graph, and this takes time at most n 2 • 2 n-1 ≤ k 2 • 2 2k . We allow linear time for the reading of the whole input. 2

Parameterized Complexity of SWITCH-k-SMALL-DEGS

In this section, we present the best known algorithm for the parameterized version of SWITCH-k-SMALL-DEGS. The ideas of the algorithm are the crucial ones in the proofs of the tractability of problems in further sections of the paper. Before we present the algorithm, we observe that we can assume that the input graph contains an isolated vertex v 0 . If it does not, we can switch the neighborhood of a vertex of minimum degree to obtain an isolated vertex according to Lemma 2.4. As one vertex can be switched in time O(n), we can obtain the isolated vertex in time O(d • n) which is upperbounded by O(m), where d is the minimum degree and m is the number of the edges of the original graph. The answer remains unchanged due to Lemma 2.3.

Let G be the input graph. We seek a set A ⊆ V G such that S(G, A) has all vertex degrees at most k. Since A is a solution if and only if V \ A is, we may assume without loss of generality that v 0 / ∈ A. These two things together give us that

N S(G,A) (v 0 ) = A. Thus necessarily |A| ≤ k.
This means that in total we can switch at most k vertices. During the run of the algorithm, we switch certain vertices one by one, and by l we denote the number of the vertices we can still switch. At the beginning we set l := k. Now we introduce two simple rules that solve the "big" instances:

Lemma 3.4 (Rule 1) We must switch every vertex v of degree greater than k + l in order to obtain a solution.

Proof: By contradiction. Suppose that A determines a switch solving the problem and that v / ∈ A. Vertex v has at least k + l + 1 neighbors in G. By switching v could lose at most |A| of them and thus at most l. So it still has at least k + 1 neighbors. Switching A does not solve the problem, a contradiction. 2 Lemma 3.5 (Rule 2) No vertex v of degree less than nkl can be switched to obtain a solution.

This lemma is proved similarly as the previous one, so we omit the proof.

The following statement is an easy corollary of the previous two lemmas:

Corollary 3.6 (Boundary) If n ≥ 2k + 2l + 1, then at least one of the rules 1 and 2 applies on each vertex.

That means we have already obtained a kernel with 4k vertices (i.e. the instances with more than 4k vertices can be solved efficiently, while only those with at most 4k vertices are really hard) and thus the problem is in FPT.

As we want to give a better bound on the running time of the algorithm, we concentrate on the instances of sizes n = 2k + 2p + 2 or n = 2k + 2p + 1 for some 0 ≤ p ≤ k -1. In this case, after switching kp vertices (i.e., if at most p more vertices can be switched) at least one of the rules applies to each vertex and, hence, it is possible to decide which vertices should be switched and which should not. The algorithm is as follows:

1. Set l := k 2. For every vertex v (except v 0 )
• Check which of the rules 1 and 2 applies on v

• If both rules apply answer NO and quit.

• If rule 1 applies switch v and decrease l • If l < 0 answer NO and quit.

3. If n > 4k then check if all the vertices have degree at most k in this switch and answer.

4. If n ≤ 4k then try all the possibilities A to choose up to lp := l -1 2 (n -2k -1) vertices that can be switched and that were not switched already. For each choice of A switch according to A, apply the rules once again and check whether we obtained the desired solution.

Remark 3.7 The algorithm can be also used to enumerate all the graphs with the desired property.

The correctness of the algorithm follows immediately from Lemmas 3.4, 3.5 and Corollary 3.6. To count the running time of the algorithm we must bound the number

k-p i=0 n-1 i
of the candidate sets in step 4. It is easy to observe that this is always at most 2k+2p+1 k-p

• k, so we have to search for the biggest number among

2k + 1 k , 2k + 3 k -1 , ..., 2k + 2p + 1 k -p , ..., 4k -3 2 , 4k -1 1 .
We compare two neighboring terms

z k (p) := 2k+2p+1 k-p and z k (p + 1) = 2k+2p+3 k-p-1 . Since z k (p) = 2k + 2p + 1 k -p = (2k + 2p + 1) . . . (k + 3p + 5)(k + 3p + 4)(k + 3p + 3)(k + 3p + 2) (k -p)(k -p -1) . . . 2 • 1 , while z k (p + 1) = 2k + 2p + 3 k -p -1 = (2k + 2p + 3)(2k + 2p + 2)(2k + 2p + 1) . . . (k + 3p + 5) (k -p -1) . . . 2 • 1
we know that the term z k (p) is less than (equal, greater than) the term z k (p + 1) if and only if the left side of a cubic equation (k + 3p + 4)

• (k + 3p + 3) • (k + 3p + 2) = (2k + 2p + 3) • (2k + 2p + 2) • (k -p)
is less than (equal, greater than) the right side, respectively. The equation (considered with parameter k) has only one real root

p 0 = 1 93 • (-31k -91 + (30752k 3 + 47616k 2 + 19518k + 1403 + + 186 √ 3 7936k 6 + 23808k 5 + 24352k 4 + 7776k 3 -3541k 2 -3424k -975) 1/3 + (496k 2 + 620k + 469) • (30752k 3 + 47616k 2 + 19518k + 1403 + + 186 √ 3 7936k 6 + 23808k 5 + 24352k 4 + 7776k 3 -3541k 2 -3424k -975) -1/3 ),
which is p 0 = 0.22298k + o(k). Since the term p 3 appears positively on the left side, while negatively on the right side of the equation, the left side is less than the right side if and only if p < p 0 . Hence

z k ( p 0 -1) is less than z k ( p 0 ) while z k ( p 0 ) is already greater than z k ( p 0 + 1). Thus for large k the biggest term is z k ( p 0 ) = 2 1.2230k +1 0.7770k

Parameterized Complexity of SWITCH-k-REGULAR

In an arbitrary k-regular graph, each vertex has degree at most k, which means that we can use our previous algorithm from Subsection 3.2 to decide the problem. We just enumerate all the degree ≤ k graphs and check if some of them is k-regular. But we will slightly improve the algorithm. We always have to switch exactly k vertices in this case. Consider some ordering on V \ {v 0 }. A k-vertex set can contain at most p vertices among the last p in this ordering. Hence it must contain at least kp vertices among the first np -1. In the case of n ≤ 4k, the k-vertex sets determining the solution are searched by trying all size kp vertex subsets and then applying the rules to find the rest of the set. Due to the previous statement, we can find each solution searching the kp subsets only among the first np -1 vertices in the ordering.

Using this idea we can bound the number of candidate tests by n-p-1 k-p

≤ 2k+p+1 k-p
. To find the bound for this, we again compare these terms for 0 ≤ p ≤ k -1. The corresponding quadratic equation is

(k + 2p + 3) • (k + 2p + 2) = (2k + p + 2) • (k -p),

Optimizing the Number of Edges

The number of edges of a graph is another natural quantity to be optimized. We examine the following problems.

SWITCH-FEW-EDGES

Input: A graph G = (V, E), an integer k Question: Is there a subset of vertices A ⊆ V such that in the graph S(G, A), there are at most k edges?

SWITCH-MANY-EDGES

Input: A graph G = (V, E), an integer k Question: Is there a subset of vertices A ⊆ V such that in the graph S(G, A), there are at least k edges?

If k is a constant, there obviously is an O(n k+3 )-time algorithm for SWITCH-FEW-EDGES by Theorem 3.1. The problem SWITCH-MANY-EDGES becomes trivial in view of Lemma 3.2. For a parameter k, we show a significantly better algorithm for SWITCH-FEW-EDGES in Subsection 4.3. We begin by showing the NP-completeness of the problems when k is a part of the input. This is done in Subsection 4.1.

NP-Completeness

In this subsection, we prove the NP-completeness of SWITCH-FEW-EDGES and SWITCH-MANY-EDGES.

Lemma 4.1 The problems SWITCH-FEW-EDGES and SWITCH-MANY-EDGES are polynomially equivalent.

Proof: Let G be a graph. We use the fact that S(G, A) = S(G, A) for any set A ⊆ V G . Thus the graph S(G, A) has at most k edges if and only if its complement S(G, A) has at least n 2k edges. 2

Therefore it suffices to show the NP-completeness of SWITCH-FEW-EDGES only. We use a reduction of the following well-known NP-complete problem [START_REF] Garey | Computers and Intractability, A guide to the Theory of NP-Completeness[END_REF].

SIMPLE-MAX-CUT

Input: A graph G, an integer j Question: Does there exist a partition V 1 , V 2 of V G such that the cut between V 1 and V 2 in G contains at least j edges? Theorem 4.2 SWITCH-FEW-EDGES is NP-complete.

Proof: From an instance (G, j) of SIMPLE-MAX-CUT we create an instance (G , k) of SWITCH-FEW-EDGES in the following way. For each vertex of G we create a corresponding non-adjacent vertex pair in G . An edge in G is represented by four edges completely interconnecting the two pairs, and a non-edge in G is represented by only two edges connecting the two pairs in a parallel way. More formally, we set

V G = {v , v : v ∈ V G } E G = {{u , v }, {u , v } : u, v ∈ V G , u = v} ∪ {{u , v }, {u , v } : {u, v} ∈ E G }.
The following lemma relates cuts in G to switches of G . Proof: For a cut C in G we define a corresponding vertex subset A = A(C) of G . Suppose that C separates a vertex set V 1 from the remaining vertices of G. We set A to be the set {v , v : v ∈ V 1 }. Note that such a set A satisfies the following condition of legality.

Definition 4.4 Let A be a vertex subset of G . We say that a vertex u ∈ V G is broken in A if A contains exactly one vertex of u , u , otherwise, we say that u is sound in A. We say that a vertex-pair (edge or non-edge) {u, v} ⊆ V G is broken in A if at least one of its vertices u, v is broken. Otherwise, we say that {u, v} is sound in A.

If all vertices of G are sound in A, we say that A is legal.

Legality is a desired property, because there is an obvious correspondence between legal sets and cuts in G. Also, the number of edges in S(G , A) is determined by the size of the cut C. The original graph G contains two edges per every vertex-pair of G and two more edges per every edge in G, which is

2 |V G | 2 + 2|E G |
edges altogether. Since A is legal, it can easily be checked that every non-edge {u, v} in G corresponds to two edges in both G and S(G , A), regardless of the cut C. For every edge {u, v} in the cut C we have u , u ∈ A and v , v ∈ A (or vice versa), so switching A destroys all the four corresponding edges and creates none. For an edge not present in the cut C, switching A does not modify the corresponding edges, so there are still four of them in S(G , A). To sum it up, S(G , A) has

2 |V G | 2 + 2|E G | -4|C|
edges. This proves that the statement (a) implies (b). As for the other implication, by reverting the construction of A(C) from a cut C, we get that it holds for legal sets A. It remains to deal with possible illegal switches.

Lemma 4.5 For every illegal set A there is a legal set A such that S(G , A ) contains at most the same number of edges as S(G , A).

Proof: Let A be an illegal set. As can be seen in Fig. 2, a broken non-edge never decreases the resulting number of edges, and thus is no more profitable than a sound non-edge. Therefore, if all broken vertexpairs are non-edges, we can legalize A by removing all vertices of G that correspond to broken vertices of G. After this modification, A is legal and it yields a switch with at most the same number of edges as before.

Assume that there are m broken edges, where m > 0. As shown in Fig. 2, a broken edge could in certain cases decrease the number of edges in G by more than a sound edge not present in the cut would. We create a legal set A from A using the following greedy algorithm.

1. A := A.

Find a vertex v broken in

Go back to step 2.

It remains to prove that the algorithm finds a legal set that is better than A.

In each iteration of step 3, the algorithm makes one vertex sound. It clearly finishes after a finite number of steps and creates a legal set. It does not modify sound vertices nor sound edges, therefore the number of edges in S(G , A ) corresponding to sound vertex-pairs remains unchanged. Also, making a non-edge sound does not increase the number of edges in S(G , A ) in comparison to S(G , A).

As we already know, any legal set gives us a cut in G; consider the cut obtained from A . In each iteration of Step 3, at least half of the involved edges of G became cut edges. Since during the run of the algorithm, each broken edge was made sound exactly once, we know that at least m/2 broken edges became cut edges (and decreased the edge number of S(G , A ) by at least 3), and at most m/2 broken edges became out of the cut (and increased the edge number of S(G , A ) by at most 1). Therefore, the edge number in S(G , A ) is lower by at least 3m/2m/2 = m, which we assumed to be positive. 2

To finish the proof of Lemma 4.3, it remains to prove that (b) implies (a). Let S(G , A) be a switch with at most

2 |V G | v 0 v B A D v 0 v B A Fig. 3:
The graph H in the proof of Lemma 4.8 (left) and Lemma 4.9 (right).

Proof: Having a graph G with edge set E, we set H = C(K n ) (the parity-check matrix of C * (K n )), r = Hχ E , and w = k. Then a vector e is a solution of MAXIMUM LIKELIHOOD DECODING if and only if H(e + χ E ) = 0, which means that the vector e + χ E is an element of the cut space C * (K n ) and its Hamming distance from χ E is at most k. Therefore, by Observation 4.6 there exists a switch of S(G, A) whose characteristic vector is e. Since the Hamming weight of e is at most k, the switch S(G, A) has at most k edges and we are done. (i) 2

Special cases of MAXIMUM LIKELIHOOD DECODING have been studied. It is known that the problem is NP-complete even if we allow unbounded time for preprocessing the code H. This was proven by Bruck and Naor [START_REF] Bruck | The hardness of decoding linear codes with preprocessing[END_REF] by showing that MAXIMUM LIKELIHOOD DECODING is NP-complete for the cut code of a special fixed graph, and therefore no preprocessing can help because this fixed code can be known in advance. Our proof in Subsection 4.1 provides an alternative proof of Bruck and Naor's result by using K n as the fixed graph.

Fixed Parameter Tractability

As we have seen in Subsection 4.1, the problem SWITCH-FEW-EDGES is NP-complete. But since the desired graph has at most k edges, each vertex has degree at most k. So the problem is fixed-parameter tractable by similar arguments to the ones used for SWITCH-k-SMALL-DEGS problem. In the remainder of this subsection, we present a much more efficient algorithm for this problem.

The algorithm works in a very similar way as the algorithm from Subsection 3.2, hence we omit some parts of it. We again suppose, that our graph has an isolated vertex v 0 that is not switched in the sought solution. Again, we switch vertices one by one. We denote by l the upper bound for the number of vertices we can still switch and by B the set of vertices already switched. At the beginning B := ∅ and during the entire algorithm we set l := k -|B|. We introduce two rules. They are more powerful and the proofs of their correctness are different.

Lemma 4.8 (Rule 1)

A vertex v ∈ (V \ B) \ {v 0 } of degree deg S(G,B) (v) > l must be switched in order to obtain a solution. Proof: Suppose that v ∈ (V \B)\{v 0 } is a vertex of degree d = deg S(G,B) (v) > l and A ⊆ (V \B)\{v 0 } is a set, such that its switching in S(G, B) gives a graph H. We show that if v / ∈ A, then the graph H (i)
We remark that if we consider a gain graph with labels from the group Z 2 and an arbitrary underlying graph G, an analogous reasoning yields a generalized result. If we want to switch the gain graph to contain at most k ones, this is also a special case of MAXIMUM LIKELIHOOD DECODING with H being the parity check matrix of the cut code of G. This, however, is out of scope of this paper.

has too many edges. Denote D = A ∩ N S(G,B) (v) (see Fig. 3). Then {{v 0 , x}|x ∈ D ∪ B} and {{v, x}|x ∈ N S(G,B) (v) \ D} are two disjoint sets of edges of the graph H such that the size of their union is

|B| + |D| + |N S(G,B) (v) \ D| = |B| + |N S(G,B) (v)| = d + k -l > k.
Thus the graph H has more than k edges and the switching of the set A does not lead to a solution. 2 Lemma 4.9 (Rule 2) Vertex v ∈ V \ B \ {v 0 } of degree deg S(G,B) (v) < nl -1 cannot be switched in order to obtain a solution.

Proof:

Let again d = deg S(G,B) (v) < n -l -1, A ⊆ (V \ B) \ {v 0 } and H = S(G, A ∪ B). Suppose v ∈ A. Then {{v 0 , x}|x ∈ A ∪ B \ {v}} and {{v, x}|x ∈ (V \ N S(G,B) (v))
\ A} are two disjoint sets of edges of the graph H (see Fig. 3). The size of them together is at least

(|B| + |A| -1) + (n -d -|A|) = k -l -1 + n -d > k -l + n -(n -l -1) -1 = k.
Thus the graph H has more than k edges and the switching of the set A does not lead to a solution. 2

The following boundary lemma is an easy corollary of two previous Lemmas. Lemma 4.10 (Boundary) If n > 2l + 1, then on each vertex either Rule 1 or Rule 2 applies.

The rest of the algorithm remains almost the same as in Subsection 3.2, only the kernel bound is 2k vertices, hence we omit the overview of the algorithm here. Again if n = 2p + 2 or n = 2p + 1 for some 0 ≤ p ≤ k -1, then after switching kp vertices we can decide about each vertex whether it should be switched or not according to Lemma 4.10. Thus we have at most 2p+1 k-p • k candidate sets for p ≥ k/2 and at most 2 2p+1 ≤ 2 k candidate sets for p < k/2. To count the time complexity, we must search for the biggest number among

2 k/2 + 1 k/2 , 2 k/2 + 3 k/2 -1 , ..., 2p + 1 k -p , ..., 2k -3 2 , 2k -1 1 , since for k ≥ 2 it holds that 2 k ≤ k • 2 k/2 +1 k/2
. By comparing again two neighboring terms 2p+1 k-p and 2p+3 k-p-1 we get the cubic equation (3p

-k + 4) • (3p -k + 3) • (3p -k + 2) = (2p + 3) • (2p + 2) • (k -p)
, with parameter k. The equation has again only one real root

p 0 = 1 93 • (31k -91 + (3844k 3 + 11904k 2 + 9579k + 1403 + + 93 √ 3 496k 6 + 2976k 5 + 6088k 4 + 3888k 3 -3541k 2 -6848k -3900) 1/3 + (124k 2 + 310k + 469) • (3844k 3 + 11904k 2 + 9579k + 1403 + + 93 √ 3 496k 6 + 2976k 5 + 6088k 4 + 3888k 3 -3541k 2 -6848k -3900) -1/3 ), which is p 0 = 0.611492k + o(k). Hence, for k large enough, 1.2230k +1 0.3885k
is the biggest term. Again using standard factorial approximation we have:

1.2230k + 1 0.3885k ≤ 1.2231k 0.3885k = 1.2231k e (1.2231) 1.2231k (0.3885) 0.3885k • (0.8346) 0.8346k = = 1.2231k e exp(k(1.2231 ln 1.2231 -0.3885 ln 0.3885 -0.8346 ln 0.8346)) ≤ ≤ 2.1479 k , L of size l K of size pl + p -k Z of size (q -p -1)(l + 1) + k + 1
Fig. 4: The graph Gp,q(ϕ).

Lemma 5.2 Let j be an integer. The graph G p,q (ϕ)[L] contains a clique on j vertices if and only if the formula ϕ contains j clauses that are all satisfiable at the same time.

Proof: If there are j clauses in ϕ that are simultaneously satisfied by a valuation v, then we can pick from each of them one literal which is true in v; these literals correspond to pairwise adjacent vertices -a clique of size j.

On the other hand, assume that G[L] contains a clique of size j. Then the j corresponding literals cover j clauses and all can be true at the same time. Hence all the j clauses are simultaneously satisfiable. 2 Lemma 5.2 immediately gives us the following corollary.

Corollary 5.3 The formula ϕ is satisfiable if and only if G p,q (ϕ)[L] contains a clique of size k (where k is the number of clauses in ϕ).

Let us now consider cliques of size pl + p in the whole graph -either in the original graph G or in its switches. Note that

n = |L ∪ K ∪ Z| = l + (pl + p -k) + ((q -p -1)(l + 1) + k + 1) = ql + q pl + p n = pl + p ql + q = p(l + 1) q(l + 1) = p q = c,
therefore cliques of size pl + p are exactly cn-cliques.

Lemma 5.4 The following statements are equivalent for G = G p,q (ϕ). (c) There exists a set A ⊆ V G such that S(G, A) contains a (pl + p)-clique.

Proof: First we prove that (a) implies (b). Any clique in G[L] forms a larger clique together with all vertices of K.

So, if G[L] contains a k-clique, then G[L ∪ K] contains a clique of size k + (pl + p -k) = pl + p.
Obviously (b) implies (c), because if the graph G contains a (pl + p)-clique, it suffices to take A = ∅ for S(G, A) to contain a (pl + p)-clique as well.

To prove that (c) implies (a), suppose that there is a set A ⊆ V G such that S(G, A) contains a (pl + p)clique; let us denote the vertex set of such a clique by C. The set C does not contain more than two vertices of Z, because they are pairwise non-adjacent in G and in S(G, A) they induce a bipartite graph.

From the assumptions k < l and k ≥ 2 it follows that l > 2. Moreover, p ≥ 1, so pl + p > 2. Therefore C contains some vertices of L or K. But all vertices of Z are non-adjacent in G and have the same neighborhood in G[L ∪ K]; surely all vertices in Z ∩ C have the same neighborhood in S(G, A)[C] (otherwise C would not induce a clique). But then either (Z ∩ C) ⊆ A or (Z ∩ C) ∩ A = ∅, so switching A does not affect edges inside S(G, A)[Z ∩ C] and any two vertices in S(G, A)[Z ∩ C] are non-adjacent. Therefore C contains at most one vertex of Z.

Since 1 + |K| = 1 + (pl + pk) < pl + p, the clique C contains at least one vertex of L. But then it cannot contain both vertices of K and Z, because in the graph G they have the same neighborhood in L and there is no edge between K and Z. Also, the set C cannot consist only of vertices of L, because pl + p > l. Therefore C contains one of the following:

• pl + p -1 (which is at least k) vertices of L and one vertex of Z

• at least k vertices of L and at least one vertex of K.

In both cases, C contains k vertices of L, and a vertex v of K ∪Z. Since C induces a clique in S(G, A), the vertex v is adjacent to all other vertices in C. But in G, by definition, the vertex v is adjacent to all vertices of L, too. So switching A cannot have changed any edge connecting v and the k vertices, which means that either all these k + 1 vertices are in A or none of them is. But then they induce a (k + 1)-clique in G as well, and G[L] contains a k-clique, which we wanted to prove. 2

Corollary 5.3 and Lemma 5.4 together give us that ϕ is satisfiable if and only if there exists a set A ⊆ V G such that S(G, A) contains a (pl + p)-clique. But we have already shown that pl + p = cn; and clearly a graph contains a clique of size exactly cn if and only if it contains a clique of size at least cn. That concludes the reduction. The graph G p,q (ϕ) with q(l + 1) = O(l) vertices and O(l 2 ) edges can surely be constructed in time polynomial in the size of ϕ. Hence the problem SWITCH-cn-CLIQUE is NP-complete for every rational constant c ∈ (0, 1).

To prove the NP-completeness of SWITCH-cn-CLIQUE for irrational numbers c as well, we use a consequence of the PCP theorem of Arora et al. [ALM + 98] (stated analogously to the following statement in [Vaz01, Theorem 29.7]).

Theorem 5.5 There is a constant ε > 0 for which there is a gap-introducing reduction from SAT to MAX-3SAT that transforms a Boolean formula ψ to T (ψ) such that

• If ψ is satisfiable, then T (ψ) is satisfiable.
• If ψ is not satisfiable, then at most 1ε fraction of the clauses of T (ψ) are simultaneously satisfiable.

Our aim is to do a reduction from an instance ψ of SAT. We will use the graph G p,q , like in the previous part of the proof; this time for the transformed formula T (ψ) and for numbers p and q such that p q is sufficiently close to the irrational number c. Then we examine the relationship between cn-cliques and p q -cliques in the resulting graph.

To show that some suitable numbers p and q exist, we will make use of Lemma 5.6. Let {x} denote the fractional part of x. Lemma 5.6 is a special case of the (one-dimensional) Kronecker Theorem which states that for every irrational number α the sequence {nα}, where n = 1, 2, . . . , is dense in the interval [0, 1] (see [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF]; the Theorem was first published in 1884).

Lemma 5.6 For any irrational number α ∈ [0, 1], any ε > 0 and r ∈ R there exists n ∈ N such that n > r and {nα} < ε.

For our purposes we need the following statement: Lemma 5.7 For each irrational c ∈ (0, 1), each ε > 0 and m > 0, there exist p, q ∈ N such that p q ∈ (0, 1), p > m and c ∈ 1 -ε 4p p q , p q .

Proof: We shall find an integer p such that the interval ( p c -ε 4c , p c ) contains another integer q. Then we check that the obtained numbers p and q satisfy the conditions of the Lemma. In order for the interval ( p c -ε 4c , p c ) to contain an integer, p must satisfy the condition

p c < ε 4c . (1)
We also want that p > m (which is given in the statement of the Lemma), and additionally we request that the following condition holds (which will prove useful later):

p > ε 4(1 -c) . (2)
It is true that { p c } = {p{ 1 c }}, the number { 1 c } lies in the interval (0, 1), and surely ε 4c > 0; hence Lemma 5.6 for α = { 1 c }, ε = ε 4c and r = max(m, ε 4(1-c) ) ensures the existence of such a p. Then we set q = p c and verify that it is really an integer in the interval p c -ε 4c , p c . The number p c is irrational, so we have q < p c . The fact that p c = p c -{p{ 1 c }}, and (1) together give us the other inequality q > p c -ε 4c . Moreover, from (2) we obtain p c -ε 4c > p, so any integer q in the interval p c -ε 4c , p c is larger than p. In particular, q is a positive integer, and p q ∈ (0, 1). Also, by rewriting the inequalities q < p c and q > p c -ε 4c we get the desired inequality

1 - ε 4p p q < c < p q .
Let c be an irrational number in (0, 1), let ε be the constant from Theorem 5.5, and p, q the integers given by Lemma 5.7 for ε and c and such that p > 2. We take an instance ψ of SAT and construct the graph G = G p,q (T (ψ)) in the same way as in the previous part of the proof. Let us again denote the number of clauses of T (ψ) by k. The number of occurrences of literals is l, and n stands for the number of vertices of G.

If ψ is satisfiable, we have again by Corollary 5.3 that G[L] contains a k-clique, and by Lemma 5.4 the graph G contains a (pl + p)-clique, which is a p q n-clique. We shall show that if ψ is not satisfiable, then for any set A ⊆ V G the graph S(G, A) does not contain a clique of size larger than (1 -ε 4p ) p q n. We limit ourselves to instances ψ such that (1ε)k > 1 and pl + pεk ≥ 2, which we can do without loss of generality. Let us first show the following lemma.

Lemma 5.8 Let ψ be a formula such that (1ε)k > 1 and pl + pεk ≥ 2. If ψ is not satisfiable, then for any set A ⊆ V G the graph S(G, A) does not contain a clique of size larger than pl + pεk.

Proof: Suppose that for some A ⊆ V G the graph S(G, A) contains a clique C of size larger than pl + pεk. Then (similarly as in the proof of Lemma 5.4) we get that the set C does not contain more than two vertices of Z, because they are pairwise non-adjacent in G and in S(G, A) they induce a bipartite graph.

Since |C| is more than two, C contains some vertices of L or K. But all vertices of Z are non-adjacent in The set C contains at least one vertex of L, because

1 + |K| = 1 + (pl + p -k) < (1 -ε)k + pl + p -k = pl + p -εk.
But then C cannot contain both vertices of K and Z, because in G they have the same neighborhood in L and there is no edge between K and Z.

We have requested that p > 2. Then l < (p -1)l + p < pl + pεk. Hence C cannot consist only of vertices of L. Therefore C consists of one of the following:

• more than pl + pεk -1 (which is larger than (1ε)k) vertices of L, and one vertex of Z

• more than (1ε)k vertices of L, and pl + pk vertices of K.

In both cases, C contains more than (1ε)k vertices of L, and a vertex v from K or Z. Since C induces a clique in S(G, A), the vertex v is adjacent to all other vertices in C. But in G, by definition, v is adjacent to all vertices of L, too. So switching A cannot have changed any edge connecting v and the other vertices, which means that either all the vertices are in A or none of them is. But then they induce a clique of size larger than (1ε)k in G[L] as well. By Theorem 5.5 and Lemma 5.2, the maximum clique size in G

[L] is (1 -ε)k, which is a contradiction. 2
By Lemma 5.8, if ψ is not satisfiable, then the maximum clique size in S(G, A) for any A is pl +p-εk.

But εk n = εk q(l + 1) = εk q(3k + 1) ≥ ε 4q = ε 4p • p q ,
all vertices of G in G , the vertices of C are all contained either in A or in V (G ) \ A. Hence, either A or V (G ) \ A contains the clique C both in S(G , A) and in G , thus G also contains a clique of size 2k.

If the clique C consists solely of the vertices of G, then one of the sets A, V (G) \ A contains at least half of C, and thus there is a clique of size k in G.

2

The problem can be also easily shown to be in W For the proof we use the characterization of W[1] by Nondeterministic Random Access Machines as proposed in [START_REF] Chen | Bounded nondeterminism and alternation in parameterized complexity theory[END_REF].

A nondeterministic random access machine (NRAM) model is based on the standard deterministic random access machine (RAM) model. A single nondeterministic instruction "GUESS" is added, whose semantics is: Guess a natural number less than or equal to the number stored in the accumulator and store it in the accumulator. Acceptance of an input by an NRAM is defined as usually for nondeterministic machines. The steps of computation of an NRAM that execute a GUESS instruction are called nondeterministic steps. Definition 6.3 An NRAM program P is tail-nondeterministic k-restricted if there are computable functions f and g and a polynomial p such that on every run with input (x, k) ∈ Σ * × N the program P • performs at most f (k) • p(n) steps;

• uses at most the first f (k) • p(n) registers;

• contains numbers ≤ f (k) • p(n) in any register at any time; and all nondeterministic steps are among the last g(k) steps of the computation. Here n = |x|.

The following characterization is crucial for our proof: Theorem 6.4 (Flum, Grohe [START_REF] Chen | Bounded nondeterminism and alternation in parameterized complexity theory[END_REF]) A parameterized problem P is in W[1] if and only if there is a tail-nondeterministic k-restricted NRAM program deciding P .

Proof of Proposition 6.2: For the proof we introduce the program SwitchEmbed that takes graphs G and H as an input, and there is an accepting computation of SwitchEmbed on G and H if and only if there is a switch of G containing H as an induced subgraph. We present it in a higher level language that can be easily translated to the NRAM instructions. The program is obviously tail-nondeterministic |H|-restricted. It can easily be modified to handle the non-induced case.

Program SwitchEmbed(G, H)

Open Problems

To conclude, we mention some open problems related to the problems we have solved in this paper.

Switching to a k-degenerated graph An O n k+3 -time algorithm for this problem follows from the results of Ehrenfeucht et al. [START_REF] Ehrenfeucht | Complexity issues in switching of graphs[END_REF]. If k is a part of the input, no polynomial time algorithm is known. The problem is also not known to be NP-complete. Fixed-parameter tractability would be a good alternative.

Parameterization above guaranteed value It is not known whether it is possible to decide in polynomial time whether the input graph is switching-equivalent to a graph having all degrees at least n/2 + k, where k is a fixed constant.

Swiching to an H-free graph The question whether the input graph can be switched to a graph not containing the graph H (which is also part of the input) is not even known to be in NP, it only trivially falls into the class Σ P 2 of the polynomial hierarchy. It is known to be in P for the following fixed graphs H (and their complements): for K 2 (this can be simply proved, see also [START_REF] Hage | Euler graphs, triangle-free graphs and bipartite graphs in switching classes[END_REF]), for K 1,2 ([KNZ92]), for K 3 ([Hay96, HHW02]), P 4 ([Her99]), and K 1,3 ([JK08]). On the contrary, there are infinitely many graphs H in a certain class of graphs called "hedgehogs" for which the problem is NP-complete [START_REF] Jelínková | Switching to hedgehog-free graphs is NP-complete[END_REF]. However, these are the only few exceptions for which the complexity has been determined. It is not even known whether the problem is either polynomial or NP-complete for each fixed graph H.

Fig. 1 :

 1 Fig. 1: Seidel's switches of C4. Switched vertices are drawn left of the vertical line.

Lemma 4. 3

 3 The following statements are equivalent:(a) There is a cut in G having at least j edges, (b) there exists a setA ⊆ V G such that S(G , A) contains at most 2 |V G | 2 + 2|E G | -4j edges.

Fig. 2 :

 2 Fig. 2: The possible legal and illegal switches of non-edges (on the left, in the middle) and edges (on the right) in G and their influence on the number of edges in G .

  A . If there is no such, STOP. 3. Look for sound neighbors of v in G. If there are more such neighbors u having u , u ∈ A than those having u , u ∈ A , then set A := A \ {v , v }, otherwise set A := A ∪ {v , v }.

( a )

 a The graph G[L] contains a k-clique. (b) The graph G contains a (pl + p)-clique.

  G and have the same neighborhood in G[L∪K]; surely all vertices in Z∩C have the same neighborhood in S(G, A)[C] (otherwise C would not be a clique). But then either (Z ∩ C) ⊆ A or (Z ∩ C) ∩ A = ∅, so switching A does not affect edges inside S(G, A)[Z ∩ C], and any two vertices in S(G, A)[Z ∩ C] are non-adjacent. Therefore C contains at most one vertex of Z.

  [1]. Proposition 6.2 The problem SWITCH-EMBED is in W[1].

1.

  Denote k := |H|, V (H) = {h 1 , . . . , h k }; 2. Guess k distinct vertices v 1 , . . . , v k from V (G); 3. Denote S := {v 1 , . . . , v k }; 4. Guess A ⊆ S; 5. Denote f : S → V (H), v i → h i (∀i, 1 ≤ i ≤ k) 6. If f is a graph isomorphism between S(A, G[S]) and H then ACCEPT; else REJECT;

  where one root is The problem SWITCH-k-REGULAR is linear fixed-parameter tractable and can be solved in time O 4.237 k • n + m .

	=	2.1710k e	exp(k(2.1710 ln 2.1710 -0.8291 ln 0.8291 -1.3419 ln 1.3419)) ≤
	≤ 4.2363 k ,
	for k large enough.
	Our results are summarized by the following theorem:
	Theorem 3.9
				p 1 =	-5k -12 +	√ 10 45k 2 + 60k + 24	,
	and the second does not satisfy the condition 0 ≤ p ≤ k -1. Asymptotically p 1 = 0.170821k + o(k), which means that 2.1709k +1 0.8291k is the biggest term. Again using the standard factorial approximation we
	have:
		2.1709k + 1 0.8291k	≤	2.1710k 0.8291k	=	2.1710k e	(2.1710) 2.1710k (0.8291) 0.8291k • (1.3419) 1.3419k =

+ 2|E G | -4j edges. If A is illegal, Lemma 4.5 assures that there is a legal set A such that

Acknowledgements

The authors would like to thank Jiří Sgall for useful suggestions, Martin Klazar for skillful advice, and the anonymous referees for helping to improve the paper.

‡ Most of the work done while on the Dep. of § Supported by grant 1M0545 of the Czech Ministry of Education. ¶ Supported by project 1M0021620838 of the Czech Ministry of Education. 1365-8050

S(G , A

) has even less edges. The legal set yields a partition V 1 = {v : v , v ∈ A } and V 2 = V G \ V 1 such that the cut between V 1 and V 2 contains at least j edges.

2

According to Lemma 4.3, the graph G contains a cut of size at least j if and only if G is switchingequivalent to a graph with at most k = 2 |V G | 2 +2|E G |-4j edges. The size of (G , k) is surely polynomial in the size of (G, j). That concludes the proof of NP-hardness of SWITCH-FEW-EDGES. To prove that SWITCH-FEW-EDGES is in NP, it suffices to note that the positive answer can be certified by a vertex set A that gives us a switch with the desired number of edges. 2

A Connection to Maximum Likelihood Decoding

In this section, we explain how the problem SWITCH-FEW-EDGES may be translated into the language of coding theory, and how it is related to a well-known problem called MAXIMUM LIKELIHOOD DECOD-ING. We derive a consequence of Theorem 4.2. Let V be a fixed set of n vertices. For an edge set E ⊆ V 2 , by χ E we denote the characteristic vector of E, i. e., the element of Z ( n 2 )

2 such that χ E (e) = 1 if and only if e ∈ E. Thus any graph on the vertex set V can be represented by a vector of length n 2 . The following observation expresses how switching works by means of characteristic vectors.

(Note that the summation is done over Z 2 .) Therefore, if we seek a switch of G with the minimum number of edges, we seek a characteristic vector χ E + χ S with the minimum Hamming weight. Or, equivalently, we seek a cut S in K n with the minimum Hamming distance between χ S and χ E .

It is a well-known fact that the cut space C * (G) of a graph G is a vector space, and the cycle space C(G) is also a vector space orthogonal to C * (G). The dimension of C * (G) is |V | -1, and C * (G) can also be viewed as a linear [|E|, |V | -1] code with a parity-check matrix C whose rows are |E| -|V | + 1 linearly independent characteristic vectors of cycles in G. Such a code is called a graph theoretic code; the concept of graph theoretic codes has been introduced by Hakimi and Frank [START_REF] Hakimi | Cut-set matrices and linear codes[END_REF].

The problem of finding a codeword in a linear code that is closest to a given vector is an important problem in coding theory. It can be formulated as a decision problem in the following way.

Problem: MAXIMUM LIKELIHOOD DECODING Input: A binary p × q matrix H, a vector r ∈ Z p 2 , and an integer w > 0. Question: Is there a vector e ∈ Z q 2 of Hamming weight at most w such that He = r?

This problem was proven to be NP-complete by Berlekamp et al. [START_REF] Berlekamp | On the inherent intractability of certain coding problems[END_REF]. Note that SWITCH-FEW-EDGES is indeed its special case, which we formalize in the following lemma.

Lemma 4.7 SWITCH-FEW-EDGES is a special case of MAXIMUM LIKELIHOOD DECODING, where H is the parity check matrix of the code of cuts in a complete graph.

for k large enough.

Our results are summarized by the following theorem:

Theorem 4.11 SWITCH-FEW-EDGES is fixed-parameter tractable and there is an algorithm running in time O 2.148 k • n + m .

5 Searching for a Switch with a cn-Clique

In this section, we consider the following problem. We assume that c is a fixed constant from the interval (0, 1).

SWITCH-cn-CLIQUE

Input: Graph G = (V, E) on n vertices Question: Is there a subset of vertices A ⊆ V such that the graph S(G, A) contains a clique of size at least cn?

Theorem 5.1 The problem SWITCH-cn-CLIQUE is NP-complete for any c ∈ (0, 1).

Proof: We prove the theorem in two steps: first we prove the statement for rational numbers c only; then we extend it to numbers c which are irrational. It is clear that the problem is in NP -a polynomial-size certificate contains vertex subsets A and C such that S(G, A)[C] is a clique of the desired size. In the case of irrational c, we assume that an oracle can be used giving for any n the value of cn in constant time. This ensures that the certificate can be checked in time polynomial in n.

Each step is a reduction of the SAT problem which is known to be NP-complete [START_REF] Garey | Computers and Intractability, A guide to the Theory of NP-Completeness[END_REF]. Suppose that c is rational and equal to p q , where p, q ∈ N, and p < q. We have an instance of SAT: a formula ϕ in CNF with k clauses and l occurrences of literals, and ask if ϕ is satisfiable. Without loss of generality we can assume that k < l and k ≥ 2.

Let G = G p,q (ϕ) be a graph constructed in the way illustrated in Figure 4. The vertices of G are V G = L ∪ K ∪ Z, where L, K, Z are pairwise disjoint and

The edges of G are defined as follows:

• K induces a clique and every vertex in K is adjacent to all vertices in L and no vertex in Z.

• Every vertex in Z is adjacent to all vertices in L and to nothing else.

• Vertices of L represent occurrences of literals in ϕ. Two vertices l 1 , l 2 ∈ L are adjacent if and only if

l 1 and l 2 occur in different clauses and they are not in the form l 1 = ¬l 2 nor l 2 = ¬l 1 . so the maximum clique size divided by n is

We have chosen the numbers p, q so that

hence the maximum clique ratio matches the lower bound of the interval containing c.

To sum it all up, we have shown that

• if ψ is satisfiable, then there exists an A ⊆ V G such that S(G, A) contains a clique of size p q n, which is at least cn,

• if ψ is not satisfiable, then for no set A ⊆ V G the graph S(G, A) contains a clique of size more than

(1 -ε 4p ) p q n, especially of size at least cn.

Hence ψ is satisfiable if and only if G can be switched to contain a clique of size at least cn. The graph G p,q (T (ψ)) with q(l + 1) = O(l) vertices and O(l 2 ) edges can be constructed in polynomial time. That concludes the polynomial-time reduction of 3-SAT to SWITCH-cn-CLIQUE for an irrational constant c, and also the proof that the problem is NP-complete. It has been shown in [START_REF] Ehrenfeucht | Complexity issues in switching of graphs[END_REF] that it is NP-Complete to decide whether a switching class contains a graph with a clique of size at least k. There is also an easy parameterized reduction from CLIQUE showing the problem SWITCH-EMBED is W[1]-hard even if we restrict the input graph H to be complete graph. Proposition 6.1 It is W[1]-hard to decide whether there is a graph that is switching-equivalent to the input graph and contains a clique of size k, k being the parameter of the problem.

Proof: We reduce the CLIQUE problem that is well known to be W[1]-complete [START_REF] Downey | Parametrized Complexity[END_REF]. Let (G, k) be an instance of CLIQUE. Consider a graph G obtained from G by adding a clique K of size k and connecting all its vertices with all the vertices of G. Then the switching class of G contains a graph with a clique of size 2k if and only if G contains such a clique, which is if and only if G contains a clique of size k.

To see this, first assume that some vertices of K are contained in a 2k-clique C in a switch S(G , A) of G . Since the vertices of C are all pairwise adjacent in S(G , A), and the vertices of K are adjacent to


José Cáceres
email: jcaceres@ual.es.

Delia Garijo
email: dgarijo@us.es.

Antonio González
email: gonzalezh@us.es.

Alberto Márquez

María Luz Puertas
email: mpuertas@ual.es.

The determining number of Kneser graphs †

Keywords: Determining set, determining number, Kneser graph, hypergraph

A set of vertices S is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G is the minimum cardinality of a determining set of G. This paper studies the determining number of Kneser graphs. First, we compute the determining number of a wide range of Kneser graphs, concretely K n:k with n ≥ k(k+1) 2 + 1. In the language of group theory, these computations provide exact values for the base size of the symmetric group Sn acting on the k-subsets of {1, . . . , n}. Then, we establish for which Kneser graphs K n:k the determining number is equal to n -k, answering a question posed by Boutin. Finally, we find all Kneser graphs with fixed determining number 5, extending the study developed by Boutin for determining number 2, 3 or 4.

Introduction

The determining number of a graph G = (V (G), E(G)) is the minimum cardinality of a set S ⊆ V (G) such that the automorphism group of the graph obtained from G by fixing every vertex in S is trivial. In this paper, we continue the study on the determining number of Kneser graphs carried out by [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF], introducing a different technique from the tools used in that article.

An automorphism f of G is a bijective mapping of V (G) onto itself such that f (u)f (v) ∈ E(G) whenever uv ∈ E(G). As usual Aut(G) denotes the automorphism group of G. A subset S ⊆ V (G) is said to be a determining set of G if whenever g, h ∈ Aut(G) so that g(s) = h(s) for all s ∈ S, then g(v) = h(v) for all v ∈ V (G). The minimum cardinality of a determining set of G, denoted by Det(G), is the determining number of G; a set of that cardinality is said to be a minimum determining set. Observe that 0 ≤ Det(G) ≤ |V (G)| -1 since any subset of V (G) containing all but one vertex is a determining set of G. It is easy to see that the only connected graphs G with Det(G) = |V (G)| -1 are the complete graphs. A graph G with Det(G) = 0 is called asymmetric or rigid. [START_REF] Erdős | Assymetric graphs[END_REF] proved that almost all graphs are rigid.

The Kneser graph K n:k has vertices associated with the k-subsets of the n-set [n] = {1, . . . , n} and edges connecting disjoint sets. This family of graphs is usually considered for n ≥ 2k but here we shall assume that n > 2k since the case n = 2k gives a set of disconnected edges and its determining number is half the number of vertices.

Determining sets are particular cases of bases which were introduced by [START_REF] Sims | Determining the conjugacy classes of a permutation group[END_REF] in the context of computational group theory. Indeed, a base of a permutation group Γ acting on a set X is a subset B of X such that the pointwise stabilizer of B in Γ is trivial, i.e., the only element of Γ which fixes each point of B is the identity element. The base size of Γ is the minimum cardinality of a base. When X is the vertex-set of a graph G and Γ = Aut(G), a base B is precisely a determining set of G and the base size of Aut(G) is Det(G).

There exists an extensive literature on determining the base sizes of primitive permutation groups. See [START_REF] Bailey | Base size, metric dimension and other invariants of groups and graphs[END_REF] for a number of references on this topic, and also [START_REF] Burness | On base sizes for symmetric groups[END_REF] where primitive actions on symmetric groups are considered. [START_REF] Erwin | Destroying automorphisms by fixing nodes[END_REF] introduced the term fixing set to refer to a base for Aut(G), and Boutin (2006) used the term determining set for the same concept. Here we shall follow the terminology of [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF] (see also [START_REF] Albertson | Using determining sets to distinguish Kneser graphs[END_REF]) since in that paper, a study on Kneser graphs was performed. Concretely, the author proved that their determining number is tightly bound by log 2 (n + 1) ≤ Det(K n:k ) ≤ n -k computing also the exact value Det(K 2 r -1:2 r-1 -1 ) = r. Further, all Kneser graphs with determining number 2, 3 or 4 were provided. The main tools used in [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF] to find determining sets or to bound the determining number of Kneser graphs are based on characteristic matrices and vertex orbits.

This paper contains two main results. In Section 2, we compute the determining number of all Kneser graphs K n:k with n ≥ k(k+1) 2 + 1. Our technique is based on two key ideas. First, every subset of vertices of K n:k has an associated k-regular hypergraph. The fact of being determining is achieved by imposing conditions on the edges of the corresponding hypergraph. Second, the relevant hypergraphs that let us compute Det(K n:k ) for n ≥ k(k+1) 2 + 1 are constructed by using perfect matchings and Hamiltonian cycles in a complete graph. These hypergraphs are, in fact, graphs with loops or they have only one edge of cardinality bigger than 2.

We want to stress that since the automorphism group of the Kneser graph K n:k is the action of the symmetric group S n on the k-subsets of [n] (see [START_REF] Godsil | Algebraic graph theory[END_REF]), our results in Section 2 provide exact values for the base size of S n acting on the k-subsets of [n] for n ≥ k(k+1) 2 + 1. The problem of computing base sizes for the action of S n on k-subsets was first studied in the (unpublished) D. Phil. thesis of [START_REF] Maund | Bases for permutation groups[END_REF]. His approach was given in the context of group theory and ours using the language of graphs, but both approaches obtain similar results. We have also recently learnt of a related result by [START_REF] Halási | On the base size for the symmetric group acting on subsets[END_REF] which provides the values for the base size of S n acting on k-subsets for n = 2k and n ≥ k 2 .

Our second main result concerns the question of whether there exists an infinite family of Kneser graphs K n:k with k ≥ 2 and determining number n -k, which was posed by [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF]. The above approach by hypergraphs is our main tool to answer this question which is done in Section 3. Concretely, we show that K n:1 for any n, K 5:2 and K 6:2 are the only Kneser graphs with determining number n -k.

Finally, as an application of our technique and so following with the series of results presented in [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF] providing all Kneser graphs with fixed determining number 2, 3 or 4, we list all Kneser graphs with fixed determining number 5; this is the content of Section 4. We conclude the paper with some remarks and open problems.

Computing the determining number of Kneser graphs

In this section, we compute the determining number of a wide range of Kneser graphs, obtaining a characterization of their determining sets in terms of hypergraphs. In order to do this, we shall apply the following result from [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF].

Lemma 2.1 (Boutin ( 2006)) The set {V 1 , . . . V r } is a determining set of K n:k if and only if there exists no pair of distinct elements a, b ∈ [n] so that for each i either {a, b} ⊆ V i or {a, b} ⊆ V c i . Observe that the above lemma implies that every determining set of K n:k has to contain all the elements of [n] but at most one.

Recall that a hypergraph is a generalization of a graph, where edges can connect any number of vertices. Formally, a hypergraph H is a pair (V (H), E(H)) where V (H) is the set of vertices, and E(H) is a set of non-empty subsets of V (H) called hyperedges or simply edges. When edges appear only once, the hypergraph is called simple. The order of a hypergraph is the number of its vertices, denoted by |V (H)|, and the size is the number of its edges |E(H)|. A hyperedge containing r vertices is said to be an edge of cardinality r. Thus, given a hypergraph H with n vertices there are edges of cardinality ranging over the set {1, . . . , n}. The edge-cardinality-sequence of H, written as r 1 ≥ ... ≥ r |E(H)| , gives the cardinality r i of the edges of H. The degree δ(v) of a vertex v is the number of hyperedges containing v. A hypergraph is called k-regular if every vertex has degree k. In all the figures in this paper, hyperedges of cardinality bigger than 2 are illustrated as shadowed regions.

For any set of vertices S ⊆ V (K n:k ) denote by H S the k-regular hypergraph obtained as follows: The vertex-set V (H S ) is equal to S, and two vertices belong to the same hyperedge whenever they contain a common element. When an element of [n] appears only once in the vertices of S, we have a loop in the corresponding vertex of H S . Figure 1 shows an instance of a hypergraph associated to a set S ⊆ V (K 6:3 ). The two following results state that the condition of being determining set can be captured from the structure of the associated hypergraph.

Lemma 2.2 A set S ⊆ V (K n:k ) is a determining set of K n:k if and only if the associated k-regular hypergraph H S is simple and has either n or n -1 edges.

Proof: Consider a determining set S of K n:k and the hypergraph H S . By Lemma 2.1, there exists no pair of distinct elements a, b ∈ [n] so that for each vertex V ∈ S either {a, b} ⊆ V or {a, b} ⊆ V c . Hence, H S is simple. Indeed, having multiple edges in H S is equivalent to have at least two elements of [n] in exactly the same vertices of S, which implies that they are not distinguishable by any vertex of S.

It is clear that H S has either n or n -1 edges since Lemma 2.1 says that S has to contain all the elements of [n] but at most one. Thus, elements of [n] in S correspond to edges in H S .

Suppose now that H S is simple and has either n or n -1 edges. + 1, which is done in Theorems 2.6 and 2.7 below. We shall use, as a main tool to construct an appropriate hypergraph, the fact that every complete graph K d has a 1-factorization whenever d is even (i.e., a collection of d -1 pairwise disjoint perfect matchings), and a Hamiltonian decomposition whenever d is odd (i.e., a collection of d-1 2 pairwise disjoint Hamiltonian cycles). (See Lucas (1892) and [START_REF] Baranyai | On the factorization of the complete uniform hypergraph[END_REF] or the recent paper by [START_REF] Bryant | Cycle decompositions of complete graphs[END_REF].) + 1 edges (in this proof hypergraphs will be, in fact, graphs with loops). We distinguish three cases according to the parity of k and d.

Case 1. d even: H k,d is the hypergraph formed by d vertices, a loop attached at each vertex, and the edges of k -1 pairwise disjoint perfect matchings of the complete graph K d (see Figure 2 Our next aim is to extend Theorem 2.6 to Kneser graphs

K n:k where d ≥ k, d > 2 and (d-1)(k+1) 2 < n -1 < d(k+1)

2

. For our purpose, we need to introduce an operation on the edge-set of a hypergraph H.

Let e 1 , e 2 ∈ E(H). We say that e 1 and e 2 are merged obtaining a new hypergraph H if V (H ) = V (H) and E(H ) = (E(H) \ {e 1 , e 2 }) ∪ {e 1 ∪ e 2 }. Now, we can extend this operation to merge a finite set of edges, say {e 1 , e 2 , . . . , e t } obtaining the hypergraph H with E(H ) = (E(H) \ {e 1 , e 2 , . . . , e t }) ∪ {e 1 ∪ e 2 ∪ . . . ∪ e t }. Note that |E(H )| = |E(H)| -t + 1. We shall apply the operation of merging edges in regular hypergraphs and for e i = e j whenever i = j. Observe that if H is k-regular and e 1 , e 2 , . . . , e t are pairwise disjoint edges, i.e., they have no vertex in common, then H is k-regular (see Figure 3). Proof:

Since (d-1)(k+1) 2 < n < d(k+1) 2 then there exists r ∈ N such that n = d(k+1) 2 -r with r ≤ k-1 2
whenever d is odd or d is even and k is odd, and r ≤ k 2 whenever k is even and d is even. We first prove that Det(K n+1:k ) ≤ d by distinguishing four cases according to the parity of d and k. By Lemma 2.3, it suffices to show that there exists a k-regular simple hypergraph with d vertices and n edges. We shall construct hypergraphs (all with only one edge of cardinality bigger than 2) by using the constructions of Theorem 2.6 and the above operation of merging.

Case 1. d even and k even: Consider the hypergraph H k,d constructed in Case 1 of the proof of Theorem 2.6. Since k ≤ d -1 and k and d are even, then k ≤ d -2 and so r ≤ k 2 ≤ d-2 2 < d 2 . Hence we can take r +1 ≤ d 2 edges of any perfect matching on the vertices of H k,d and merge them obtaining the hypergraph H k,d . Since the edges of a perfect matching are disjoint, H k,d is k-regular. Moreover, by construction

d = |V (H k,d )| = |V (H k,d )| and |E(H k,d )| = |E(H k,d )| -r = d(k + 1) 2 -r = n.
Case 2. d even and k odd: Analogous to the previous case but considering,

r ≤ k -1 2 ≤ d -2 2 < d 2
n+1 i=1 r i = v∈V (H) δ(v) = k(d -1).
Note that the number of loops in H is at most d -1, so there are n + 1 -(d -1) = n -d + 2 edges of cardinality at least 2. Hence, we obtain the following inequalities about the sum on the edge cardinalities:

n+1 i=n+1-(d-2) r i ≥ d -1 n+1-(d-2)-1 i=1 r i ≥ 2(n -d + 2)              ⇒ k(d -1) = n+1 i=1 r i ≥ d -1 + 2(n -d + 2) = 2n -d + 3. Therefore, n ≤ (d-1)(k+1) 2 -1 which is a contradiction since (d-1)(k+1) 2 < n. Suppose now that H has n edges. Then, n i=n-(d-2) r i ≥ d -1 n-(d-2)-1 i=1 r i ≥ 2(n -d + 1)            ⇒ k(d -1) = n i=1 r i ≥ d -1 + 2(n -d + 1) = 2n -d + 1. Hence, n ≤ (d-1)(k+1) 2 which contradicts (d-1)(k+1) 2 < n. 2
3 Kneser graphs K n:k with determining number n -k

In this section, we answer a question posed by [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF]: "We know that Det(K n:k ) = n -k for K n:1 for any n, K 5:2 and K 6:2 . However, Det(K 7:2 ) = 4 = 7 -2. Is there an infinite family of Kneser graphs with k ≥ 2 for which Det(K n:k ) = n -k?" Theorem 3.3 below says that K n:1 , K 5:2 and K 6:2 are the only Kneser graphs with that property. edges. Let {v 0 , v 1 , ..., v k-1 } be the vertex-set of H k,k . We distinguish two cases according to the parity of k. Note that all the indices below are taken modulo k.

Case 1. k odd: H k,k is the hypergraph formed by k vertices with one loop attached at each vertex, and a Hamiltonian decomposition of K k (see Case 2 of Theorem 2.6). Assign the following set of k-1 2 edges to each vertex v i ∈ V (H k,k ) (see Figure 4):

E i = {{v i-1 , v i+1 }, {v i-2 , v i+2 }, ..., {v i-k-1 2 , v i+ k-1 2 }}.
Note that the edges of E i are disjoint and two sets E i , E j have no edges in common whenever i = j. Thus, the k-regularity is preserved in the process of merging that we are going to describe next. We consider again two cases.

Case 1.1.

If k(k+1) 2 -k-1 2 + 1 < n < k(k+1) 2 then merge a subset of k(k+1) 2 -n + 1 edges of E 0 , obtaining a k-regular hypergraph H k,k with k(k+1) 2 -( k(k+1) 2 -n + 1) + 1 = n edges. Case 1.2. If 2k ≤ n ≤ k(k+1) 2 -k-1
2 + 1 then we can merge the edges of at least one set E i obtaining a k-regular hypergraph with at least n edges. If the number of edges is equal to n then the process is concluded. Otherwise, suppose that we can merge the edges of s subsets with 0

≤ s ≤ k -1, say E 0 , E 2 , . . . , E s-1 , obtaining a k-regular hypergraph H k,k with k(k+1) 2 -s(k-1) 2 + s edges which satisfies k(k + 1) 2 - (s -1)(k -1) 2 + (s -1) < n < k(k + 1) 2 - s(k -1) 2 + s.
Then the edges of E s cannot be merged since if so the resulting hypergraph would have less than n edges. Hence, we proceed as in Case 1.

1 merging k(k+1) 2 -s(k-1) 2 + s -n + 1 edges of E s .
This process leads to a k-regular simple hypergraph H with k vertices and n edges.

Case 2. k even: H k,k is a hypergraph with k vertices, a loop attached at each vertex, and the edges of a 1-factorization of the complete graph K k (see Case 1 of Theorem 2.6). We distinguish three cases.

Case 2.1. If k(k+1) 2 -k 2 ( k 2 -1) + k 2 ≤ n < k(k+1) 2
then we can follow an analogous process of merging than in Case 1 preserving also the k-regularity, but instead of assigning the sets E i to each vertex v i , we now assign the following set of edges to v i for i = 0, . . . , k 2 -1 (see Figure 5(a)): Note that the assignment is done to half of the vertices since

F i = {{v i-1 , v i+1 }, {v i-2 , v i+2 }, ..., {v i-k 2 +1 , v i+ k 2 -1 }}.
F i = F i+ k 2
because of the parity of k. Observe also that the edges of F i are disjoint and two sets F i , F j have no edges in common whenever i = j.

This process of merging leads to a k-regular simple hypergraph H k,k resulting from merging at most

k 2 -1 i=0 |F i | = k 2 ( k 2 -1) edges in H k,k .
In this case, we obtain a hypergraph with k(k+1)

2 -k 2 ( k 2 -1) + k 2
edges. Note that the edges obtained by this procedure are all of cardinality k -2 except at most one of smaller cardinality.

Case 2.2.

If k(k+1) 2 -k 2 ( k 2 -1) + k 2 -k 2 ( k 2 -2) + k 2 = 3k ≤ n < k(k+1) 2 -k 2 ( k-2 2 -1) then we first merge all the sets of edges F i , obtaining a hypergraph H k,k with k(k+1) 2 -k 2 ( k 2 -1) + k 2 edges.
We now assign the following set of edges to v i for i = 0, . . . , k 2 -1 (see Figure 5(b)):

F i = {{v i-1 , v i+2 }, {v i-2 , v i+3 }, ..., {v i-k 2 +2 , v i+ k 2 -1 }}.
Again, we follow the procedure described in Case 1 which gives a k-regular simple hypergraph that is the result of merging at most

k 2 -1 i=0 |F i | = k 2 ( k 2 -2) edges in H k,k .
In this case, a hypergraph with

k(k+1) 2 -k 2 ( k 2 -1) + k 2 -k 2 ( k 2 -2) + k 2 edges is obtained.
Observe that the edges obtained by this process are all of cardinality k -4 except at most one of smaller cardinality.

Case 2.3. If 2k ≤ n < 3k then merge the sets F i and F i , obtaining a hypergraph with 3k edges. These edges are: k loops, k 2 edges of cardinality k -2, k 2 edges of cardinality k -4 and k edges of cardinality 2 forming the cycle {v 0 , ...v k-1 }. For every vertex v i , consider now the set of edges (see Figure 5(c)):

F i = {{v i }, {v i+1 , v i+2 }}
and merge the required sets F i to obtain a hypergraph with n edges.

2

Remark 3.2 The process of merging described in the proof of Lemma 3.1 leads to hypergraphs which have in most cases a number of edges of cardinality bigger than 2. Now, we can formulate our main result in this section.

Theorem 3.3 Det(K n+1:k ) = n + 1 -k if and only if either k = 1 or k = 2 and n = 4, 5.

Kneser graphs with fixed determining number

As an application of our technique and following the list of cases studied in [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF] characterizing all Kneser graphs with fixed determining number 2, 3 or 4, we provide all Kneser graphs with fixed determining number 5. Our method also works for the cases presented in [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF].

Lemma 4.1 Let H be a k-regular simple hypergraph with d vertices and m edges. Then the following statements hold:

(a) k ≤ 2 d-1 and m ≤ 2 d -1. (b) If m > d + d 2 then kd ≥ 3m -2d -d 2 . (c) If m > d + d 2 + d 3 then kd ≥ 4m -3d -2 d 2 -d 3 .
Proof: Statement (a) follows since the cardinality of the power set P(V (H)) of the vertex-set V (H) is 2 d , and a hyperedge is a non-empty subset of vertices.

To prove Statement (b), assume that m > d + d 2 and consider the edge-cardinality-sequence r 1 ≥ r 2 ≥ . . . ≥ r m-1 ≥ r m of H which satisfies kd = m i=1 r i (see Theorem 2.8 of [START_REF] Duchet | Hypergraphs[END_REF]). Then,

kd = m i=m-d+1 r i + m-d i=m-(d+( d 2 ))+1 r i + m-(d+( d 2 )) i=1 r i ≥ d + 2 d 2 + 3 m -d - d 2 = 3m -2d - d 2 .
Suppose now that m > d , 14, 15, 16, 16, 17, 18, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28 30 15, 16 17, 18 19, 20 20, 21 22, 23 24, 25 26 27 Tab. 1: Values of n for k ≥ 6 for which Det(K n+1:k ) = 5.

+ d 2 + d 3 . Since kd = m i=1 r i we have, kd = m i=m-d+1 r i + m-d i=m-(d+( d 2 ))+1 r i + m-(d+( d 2 )) i=m-(d+( d 2 )+( d 3 ))+1 r i m-(d+( d 2 )+( d 3 )) i=1 r i ≥ d + 2 d 2 + 3 d 3 + 4 m -d - d 2 - d 3 = 4m -3d -2 d 2 - d 3
Proof: Since every Kneser graph K n+1:1 is isomorphic to the complete graph K n+1 then only K 6:1 has determining number 5. 2006)). When k = 5, Lemma 4.1 gives 10 ≤ n ≤ 14. However for n equal to either 10 or 11, we obtain Kneser graphs already studied in [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF], whose determining numbers are equal to 4. The remaining values of n correspond to the Kneser graphs K 13:5 , K 14:5 and K 15:5 whose associated hypergraphs with 5 vertices are illustrated in Figure 6. Table 1 shows the values of n obtained for k ≥ 6 for which Det(K n+1:k ) = 5. In all the cases, it is easy to construct the associated hypergraph. On the other hand, note that for k = 6 and n = 12 or k = 7 and n = 14, the corresponding Kneser graph has determining number 4. For the remaining available values of n and k, we use Statements (b) and (c) of Lemma 4.1 in order to show that the hypergraph H does not exist and hence the determining number in those cases cannot be equal to 5. For instance, if k = 6 and n = 18 then it is straightforward to check that Statement (b) of Lemma 4.1 does not hold when d = 5. 2

Concluding Remarks

We have introduced a new technique to find determining sets and compute the determining number of Kneser graphs. Concretely, we have shown that every subset S of vertices of K n:k has an associated k-regular hypergraph H S . The set S is a determining set if and only if H S is simple and has either n or n -1 edges.

Our main results use perfect matchings and Hamiltonian cycles in a complete graph to construct the appropriate hypergraphs to obtain the determining number of all Kneser graphs K n:k with n ≥ k(k+1) 2 +1. Also, we find all Kneser graphs K n:k with k ≥ 2 and determining number n -k, answering a question posed by [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF]. Finally, as an application of our approach and following with the study developed in [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF], we give all Kneser graphs with fixed determining number 5.

Figure 7 illustrates values of n and k for which Det(K n:k ) has been computed. The determining number of K n:k remains to be computed for the integer points (n, k) on the line n = 2k + 1 with n = 2 r -1 and those in between the line n = 2k + 1 and the curve n = k(k+1) 2 + 1. It appears that our technique should be generalized to be applied for these points, constructing hypergraphs from other structures instead of perfect matchings and Hamiltonian cycles in complete graphs.

Proposition 4.2 gives all Kneser graphs with determining number 5. As was said before, our method can also be applied for determining number 2, 3 or 4 (see Propositions 12, 13 and 14 of [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF]). We believe that our technique lets us go further to determining number 6 or larger, but the list of candidate graphs increases rapidly and so a computational implementation would be required. The integer points (n, k) in the shadowed region correspond to values of n and k for which the determining number is provided by Theorems 2.6 and 2.7. The squared points represent values (2 r -1, 2 r-1 -1) studied in [START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF].

Fig. 1 :

 1 Fig. 1: Hypergraph associated to S = {{1, 2, 3}, {3, 4, 5}, {1, 4, 5}, {4, 5, 6}, {3, 5, 6}}. Number 2 appears only once in S so there is a loop attached to {1, 2, 3}. There are two edges of cardinality 2 determined by numbers 1 and 6, two edges of cardinality 3 since numbers 3 and 4 appear in three vertices of S, and one edge of cardinality 4 determined by number 5.

  Theorem 2.6 Let k and d be two positive integers such that k ≤ d and d > 2. Then, Det K d(k+1) 2 +1:k = d. Proof: We first show that Det(K d(k+1) 2 +1:k ) ≤ d. By Lemma 2.3, it suffices to prove that there exists a k-regular simple hypergraph, say H k,d , with order d and either d(k+1) 2 or d(k+1) 2

Fig. 2 :

 2 Fig.2: Hypergraphs (graphs with loops in both cases) constructed by using perfect matchings and Hamiltonian cycles: (a) H4,6 has 6 vertices, a loop attached at each vertex, and the edges of 3 pairwise disjoint perfect matchings of the complete graph K6, (b) H5,7 has 7 vertices with loops attached at each vertex, and 2 pairwise disjoint Hamiltonian cycles of K7.

Fig. 3 :

 3 Fig. 3: The edge {a, b, c, d, e, f } of the hypergraph in (b) is the result of merging three edges of the hypergraph in (a): {a}, {b, c} and {d, e, f }. Both hypergraphs are 5-regular.

  and so r + 1 ≤ d 2 . Case 3. d odd and k odd: Let H k,d be the hypergraph constructed by considering d vertices with one loop attached at each vertex, and k-1 2 pairwise disjoint Hamiltonian cycles of K d (see Case 2 of the proof of Theorem 2.6). Each cycle has d edges and r ≤ k-1 2 ≤ d-3 2 , then we can merge r disjoint edges of a Hamiltonian cycle, say C = (e 1 , . . . , e d ). Merge those edges with even subindex plus the loop attached at the common vertex of e 1 and e d ; r + 1 disjoint edges in total. Thus, we obtain a k-regular simple hypergraph H k,d with d vertices and n = d(k+1) 2 -r edges. Case 4. d odd and k even: Consider the hypergraph H k,d constructed in Case 3 of the proof of Theorem 2.6. This hypergraph is k-regular, has d vertices and d(k+1)-1 2 edges. Note that we can merge r+1 disjoint edges of a Hamiltonian cycle C of order d since r ≤ kconsider r + 1 pairwise disjoint edges among the odd labeled edges of C. The resulting hypergraph H k,d is simple, k-regular, has d vertices and n = d(k+1) 2 -r edges. It remains to prove that Det(K n+1:k ) = d. Suppose on the contrary that Det(K n+1:k ) ≤ d -1, then by Lemma 2.2 there exists a k-regular simple hypergraph H with d -1 vertices and either n + 1 or n edges. Assume first that H has n + 1 edges. The edge-cardinality-sequence r 1 ≥ ... ≥ r n+1 of H satisfies (see Theorem 2.8 of Duchet (1995)):

Lemma 3. 1

 1 Let k and n be two positive integers such that 2k ≤ n < k(k+1) 2 . Then, Det(K n+1:k ) ≤ k. Proof: By Lemma 2.3, it suffices to prove that there exists a k-regular simple hypergraph H with k vertices and n edges. Consider the k-regular simple hypergraph H k,d constructed in the proof of Theorem 2.6. Recall that, independently of the parity of k and d, the hypergraph H k,d is k-regular, has d vertices and d(k+1) 2 edges. Take k = d and the hypergraph H k,k with k vertices and k(k+1) 2

Fig. 4 :

 4 Fig. 4: The selected edges form the set E0 in H7,7.

Fig. 6 :

 6 Fig. 6: Hypergraphs associated to Kneser graphs with determining number 5: (a) K13:5, (b) K14:5, (c) K15:5.

Fig

  Fig.7: The integer points (n, k) in the shadowed region correspond to values of n and k for which the determining number is provided by Theorems 2.6 and 2.7. The squared points represent values (2 r -1, 2 r-1 -1) studied in[START_REF] Boutin | Identifying graph automorphisms using determining sets[END_REF].

  Then, for every a, b ∈ [n] the corresponding edges in H S are different and at most one element of [n] is contained in no vertex of S. By Lemma 2.1 yields the result.Lemma 2.4 A set S ⊂ V (K n:k ) is a minimum determining set of K n:k with n ≥ 2k + 1 if and only if the hypergraph H S is simple, has either n or n -1 edges and minimum order. The above characterization ensures us that the number of Kneser graphs K n:k with fixed determining number, say d, is finite. Indeed, the hypergraph associated to a minimum determining set must have a fixed number of vertices d which implies that neither k nor n can take infinite values.Lemmas 2.2 and 2.3 let us compute the determining number of all Kneser graphs K n:k with n ≥

	Remark 2.5 k(k+1)
	2

2

Lemma 2.3 For every k-regular simple hypergraph H with either n or n -1 edges and n ≥ 2k + 1, there exists a determining set S of K n:k such that H is isomorphic to H S .

Proof: We first label every edge of H with the elements of either [n] or [n -1] depending on the number of edges. The vertices of H are given the labels of their incident edges, giving rise to |V (H)| different k-subsets of [n]. Take S as the set formed by these k-subsets. Clearly, H is isomorphic to H S and by Lemma 2.2 the result follows. 2 When a determining set S is minimum, Lemma 2.3 guarantees that there does not exist a k-regular simple hypergraph H with either n or n -1 edges and |V (H)| < |S| = |V (H S )|. Thus, we say that among the k-regular simple hypergraphs with either n or n -1 edges, H S is of minimum order. More generally, a k-regular simple hypergraph H with either n or n -1 edges is said to be of minimum order if there does not exist a k-regular simple hypergraph H with either n or n-1 edges and |V (H )| < |V (H)|.

  . The Kneser graphs with determining number 5 are K 6:1 , K 8:2 , K 10:3 , K 11:3 , K 12:4 , K 13:4 , K 13:5 , K 14:5 , K 15:5 , K 16:5 , K 14:6 , K 15:6 , K 16:6 , K 17:6 , K 16:7 , K 17:7 , K 18:7 , K 19:7 , K 17:8 , K 18:8 , K 19:8 , K 20:8 , K 21:8 , K 19:9 , K 20:9 , K 21:9 , K 22:9 , K 21:10 , K 22:10 , K 23:10 , K 24:10 , K 23:11 , K 24:11 , K 25:11 , K 26:11 , K 25:12 , K 26:12 , K 27:12 , K 27:13 , K 28:13 , K 29:14 , and K 31:15 .

	Hence, Statement (c) holds. 6 7 Proposition 4.2 k n 13	8	9	10	11	12	13 14 15	2

  Consider now the graph K n+1:k with k ≥ 2 and suppose that Det(K n+1:k ) = 5. By Lemma 2.4, there exists a k-regular simple hypergraph H with minimum order 5 and either n or n + 1 edges. By Lemma 4.1 it follows that 2k ≤ n ≤ 31 and 2 ≤ k ≤ 16. Thus, we obtain a list of 196 candidate Kneser graphs to have determining number 5. When n ≥ k(k+1) 2 (which happens for 157 graphs among the 196) we can apply Theorems 2.6 and 2.7 obtaining that only K 8:2 , K 10:3 , K 11:3 , K 12:4 , K 13:4 and K 16:5 have determining number 5.Assume now that 2k ≤ n < k(k+1) When k = 4, the possible values of n are 8 or 9 but they correspond to Kneser graphs with determining number 4 (see Proposition 14 of Boutin (

2

which implies that 4 ≤ k ≤ 16.

† Partially supported by the ESF EUROCORES programme EuroGIGA ComPoSe IP04 MICINN Project EUI-EURC-2011-4306 and projects MTM2008-05866-C03-01, JA-FQM164 and JA-FQM305.

Suppose first that there exists Hence, the result follows.