Emeric Gioan
email: gioan@lirmm.fr

Chi Ho Yuen

ON THE NUMBER OF CIRCUIT-COCIRCUIT REVERSAL CLASSES OF AN ORIENTED MATROID

The first author introduced the circuit-cocircuit reversal system of an oriented matroid, and showed that when the underlying matroid is regular, the cardinalities of such system and its variations are equal to special evaluations of the Tutte polynomial (e.g., the total number of circuit-cocircuit reversal classes equals t(M ; 1, 1), the number of bases of the matroid). By relating these classes to activity classes studied by the first author and Las Vergnas, we give an alternative proof of the above results and a proof of the converse statements that these equalities fail whenever the underlying matroid is not regular. Hence we extend the above results to an equivalence of matroidal properties, thereby giving a new characterization of regular matroids.

Introduction

The cycle-cocycle reversal system of a graph, introduced in [START_REF] Gioan | Enumerating degree sequences in digraphs and a cycle-cocycle reversing system[END_REF], consists of equivalence classes of orientations of the graph with respect to the cycle-cocycle reversal relation, that is, two orientations are equivalent if they differ by successive reversals of directed (co)cycles. As proven in the same paper, the number of cycle-cocycle reversal classes of G equals the evaluation t(G; 1, 1) of its Tutte polynomial, which is also the number of spanning trees of G. This result can be thought as a "linear algebra free" formulation of Kirchhoff's Matrix-Tree Theorem. In particular, the cycle-cocycle reversal system is related to various combinatorial objects associated to the graph Laplacian, notably the sandpile group (also known as the critical group or Jacobian group in the literature). The notion of chip-firing (related to the abelian sandpile model) can also be partially interpreted by cycle-cocycle reversals. We refer the reader to [7, Section 5] and [START_REF] Backman | Riemann-Roch theory for graph orientations[END_REF] for details.

The above setup, and further results involving Tutte polynomial evaluations for related reversal classes, were generalized to regular matroids in [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF] (in terms of a circuit-cocircuit reversal system). This provides an approach to generalize the theory of sandpile groups and chip-firing to regular matroids (different from the approach in [START_REF] Merino | Matroids, the Tutte polynomial and the chip firing game[END_REF]). Such topic has been investigated since then in [START_REF] Backman | Geometric bijections for regular matroids, zonotopes, and Ehrhart theory[END_REF] in a unifying way.

Date: November 5, 2018.

The circuit-cocircuit reversal system is actually defined for general oriented matroids, and it was shown in [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF] that the aforementioned Tutte polynomial evaluations are not available for U 2,k , k ≥ 4. Since U 2,4 is the excluded minor for the class of regular matroids within oriented matroids, it was expected that these enumerative results are not available when the oriented matroid is not regular; we will prove this rigorously in this note. In particular, we extend the results in [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF] to an equivalence of (oriented) matroid properties. We use a noteworthy general relation between circuit-cocircuit reversal classes and activity classes of (re)orientations, which are known to be enumerated using the same Tutte polynomial evaluations, and have been introduced in the context of active bijections [START_REF] Gioan | Correspondance naturelle entre bases et réorientations des matroïdes orientés[END_REF][START_REF] Gioan | Activity preserving bijections between spanning trees and orientations in graphs[END_REF][START_REF] Gioan | The active bijection for graphs[END_REF][START_REF] Gioan | The Active Bijection 2.b -Decomposition of activities for oriented matroids, and general definitions of the active bijection[END_REF]. We also use this to give a short proof of results in [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF].

Preliminaries

We assume that the reader is familiar with the basic theory of oriented matroids [START_REF] Björner | Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications[END_REF]. Given an oriented matroid M on E, we identify the set of its reorientations with 2 E via the bijection associating A ⊆ E with -A M.

Let M be an oriented matroid on E. Following [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF], let us write M ∼ -C M if C is a positive circuit or cocircuit of M (we say that -C M is obtained from M by a circuit or cocircuit reversal, respectively). Applying the same rule to reorientations -A M for A ⊆ E (i.e., writing -A M ∼ -C△A M when C is a positive circuit or cocircuit of -A M) and taking the transitive closure of the relation, we obtain an equivalence relation, whose equivalence classes are called circuit-cocircuit reversal classes of reorientations of M. Allowing only the use of positive circuits, resp. positive cocircuits, yields by the same way the circuit reversal classes, resp. the cocircuit reversal classes. As observed in [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF], circuit reversals act on the totally cyclic part of M (the union of positive circuits of M) and cocircuit reversals act on the acyclic part of M (the union of positive cocircuits of M).

It was shown and geometrically illustrated in [8, Proposition 2 and Figure 1] that, for any integer k, the number of acyclic cocircuit reversal classes of a uniform oriented matroid U 2,k equals 1, or 2, if k is even, or odd, respectively. On the other hand, it is well-known that an oriented matroid M is regular if and only if U 2,4 is not a minor of M. Indeed, regular matroids are precisely the orientable binary matroids [4, Theorem 7.9.3], so the claim follows from [START_REF] James | Matroid theory[END_REF]Theorem 6.5.4]. Now, let M be an oriented matroid on a linearly ordered set E. Consider a reorientation -A M of M such that A does not contain the minimum element of a positive circuit or cocircuit of -A M, we call such a reorientation circuitcocircuit minimal (with respect to M); the terminology here is from [START_REF] Backman | Riemann-Roch theory for graph orientations[END_REF], and it is called active fixed and dual-active fixed in [START_REF] Gioan | The active bijection for graphs[END_REF][START_REF] Gioan | The Active Bijection 2.b -Decomposition of activities for oriented matroids, and general definitions of the active bijection[END_REF]. Similarly, we can define a circuit minimal (or active-fixed ), resp. a cocircuit minimal (or dual-active-fixed ), reorientation -A M of M when A does not contain the minimum element of a positive circuit, resp. cocircuit. Let us denote by t(M; x, y) the Tutte polynomial of M. From the works on active bijections [START_REF] Gioan | Correspondance naturelle entre bases et réorientations des matroïdes orientés[END_REF][START_REF] Gioan | Activity preserving bijections between spanning trees and orientations in graphs[END_REF][START_REF] Gioan | The active bijection for graphs[END_REF][START_REF] Gioan | The Active Bijection 2.b -Decomposition of activities for oriented matroids, and general definitions of the active bijection[END_REF], we have: Let us explain this briefly; details can be found in [START_REF] Gioan | Correspondance naturelle entre bases et réorientations des matroïdes orientés[END_REF][START_REF] Gioan | Activity preserving bijections between spanning trees and orientations in graphs[END_REF][START_REF] Gioan | The active bijection for graphs[END_REF][START_REF] Gioan | The Active Bijection 2.b -Decomposition of activities for oriented matroids, and general definitions of the active bijection[END_REF]. The active partition of M is a partition of its ground set induced by taking differences of unions of positive circuits/cocircuits whose the minimum element is greater than a given element. Therefore, the minimum elements of the parts are precisely the minimum elements of some positive circuits/cocircuits (called active/dual-active elements). Activity classes of reorientations are the sets of reorientations obtained from a given reorientation by arbitrarily reorienting parts of its active partition. It turns out that all reorientations obtained by this way share the same active partition. Hence activity classes partition the set of reorientations. By choosing a suitable reorientation for each part, each activity class contains a unique circuitcocircuit minimal reorientation, which can be thought of as a representative of the class. Finally, using a classical formula of the Tutte polynomial in terms of orientation activities [START_REF] Las | The Tutte polynomial of a morphism of matroids. II. Activities of orientations[END_REF], one enumerates activity classes and gets the above evaluations.

Results

We first give a noteworthy property relating reversal classes and activity classes. Proposition 3.1. Let M be an oriented matroid on a linearly ordered ground set. Every circuit-cocircuit reversal class of M contains at least one circuit-cocircuit minimal reorientation.

The following proof is essentially given in [START_REF] Backman | Partial graph orientations and the Tutte polynomial[END_REF] for graphs, but for the sake of interest and completeness, we include it here. A corollary of the proof is that a minimal reorientation can be obtained greedily. Moreover, we note that there is an interpretation using combinatorial commutative algebra [2, Section 4].

Proof. Start with an arbitrary reorientation of M, and greedily reorient any positive (co)circuit whose minimal element is in the set of reoriented elements with respect to M. Once the procedure stops, we will have a circuit-cocircuit minimal reorientation equivalent to the starting reorientation, so it suffices to show the procedure always terminates. If this is not the case, then, since the number of reorientations is finite, without loss of generality, we must return to the starting reorientation. Let e be the minimal element that was reoriented (which must occur at least twice) in the process. When e was reoriented for the first time, we must have reoriented it to remove it from the set of reoriented elements with respect to M, so the second reorientation is not valid, a contradiction. By combining Theorem 2.1 and Proposition 3.1, we can use the set of circuitcocircuit minimal reorientations (and variations thereof) as an intermediate object, and get the following corollary concerning the enumeration of reversal classes in terms of the Tutte polynomial.

Corollary 3.2. Let M be an oriented matroid on a linearly ordered ground set. The number of circuit-cocircuit reversal classes is at most t(M; 1, 1), with equality if and only if no two circuit-cocircuit minimal reorientations are contained in the same class. The number of acyclic cocircuit reversal classes is at most t(M; 1, 0), with equality if and only if no two acyclic cocircuit minimal reorientations are contained in the same class. Analogous statements hold for each of the other settings in Theorem 2.1.

Proof. The first statement follows from comparing Equation (1) of Theorem 2.1 and Proposition 3.1. The variations follow from comparing the other equations of Theorem 2.1 and the corresponding counterparts of Proposition 3.1, since circuit and cocircuit reversals preserve the acyclic and totally cyclic parts of reorientations. Now we prove the main theorem of this note, which includes the original results of [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF] (the enumerations when M is regular, with a new proof) and their converses. Theorem 3.3. Let M be an oriented matroid. Consider the following six statements:

(1) M is regular, (2) t(M; 1, 1) = # circuit-cocircuit reversal classes of M, (3) t(M; 1, 2) = # cocircuit reversal classes of M, (4) t(M; 2, 1) = # circuit reversal classes of M, (5) t(M; 1, 0) = # acyclic (circuit-)cocircuit reversal classes of M, (6) t(M; 0, 1) = # totally cyclic circuit(-cocircuit) reversal classes of M.

Then we have the following implications: (1) implies all other statements; (2), (3), (4) each implies (1); ( 5) implies ( 1) if M has no loops; (6) implies (1) if M has no coloops. In particular, if M has no loops nor coloops, then all statements are equivalent. Moreover, if any of the equalities fail, then the left hand side is larger.

Proof. Let us separate implications.

• (1) ⇒ (2). We give an alternative proof to that of [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF]. By Corollary 3.2, it suffices to show that every circuit-cocircuit reversal class contains a unique circuitcocircuit minimal reorientation. We claim that any two reorientations within a reversal class differ by a disjoint union of positive circuits and cocircuits, which will imply that at most one of them can be minimal, thus proving the implication.

By induction and restricting to the totally circuit part (the acyclic part follows from duality), it suffices to show that if C is a positive circuit of M and D is a positive circuit of -C M, then C△D is a disjoint union of positive circuits of M. By [4, Corollary 7.9.4], we may assume that some totally unimodular matrix Q realizes M. By total unimodularity, if C is a positive circuit of M, then the characteristic vector χ C ∈ {0, 1} E of C is in the kernel ker(Q) of Q; similarly, since D is a positive circuit of -C M, χ D\C -χ C∩D ∈ ker(Q). Since their sum χ C△D is in ker(Q), C△D is a positive vector and contains some positive circuit

C 1 of M, thus χ (C△D)\C 1 = χ C△D -χ C 1 ∈ ker(Q).
Proceeding by induction, we can write C△D as a disjoint union of positive circuits.

• (1) ⇒ (3), ( 4), ( 5), [START_REF] Gioan | Activity preserving bijections between spanning trees and orientations in graphs[END_REF]. Alternatively to [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF], the proofs are similar to the above one by restricting to circuit reversals only, then restricting to totally cyclic reorientations only, and then taking duals.

• (5) ⇒ (1) assuming M has no loops. Suppose M is not regular. Then it has a minor M/A \ B that is isomorphic to U 2,4 . By Corollary 3.2, it suffices to show that there are two cocircuit minimal acyclic orientations in the same (circuit-)cocircuit reversal acyclic class. Up to enlarging A, we can assume that M/A is loopless and that the rank of M/A equals 2. Since M is loopless, up to reorientation, we can assume that M and M/A are acyclic. Let C and D be the two positive cocircuits of M/A (which are also cocircuits of M). Thus, -C M and -D M are in the same acyclic reversal class. Denote S = C△D. Since the rank of M/A is 2, any cocircuit of M/A is the union of all parallel classes but one. Since S is the union of two parallel classes (C \ D and D \ C) of M/A, no cocircuit of M is contained in S (otherwise, the complement of S is a parallel class in M/A, and reducing parallel classes of M/A yields U 2,3 , a contradiction). Choose a linear ordering of E such that elements of S are greater than elements of E \ S, then S does not contain the minimum element of a cocircuit (otherwise it would contain a cocircuit), thus -C M and -D M are both cocircuit minimal.

• (2) ⇒ (1). Suppose M is not regular. Then M ′ , the oriented matroid obtained from removing all loops of M, is also not regular. By the implication (5) ⇒ (1) for M ′ , there exist distinct acyclic reorientations -A M ′ and -B M ′ that are (circuit-)cocircuit reversal equivalent and both (circuit-)cocircuit minimal. Now -A M and -B M are circuit-cocircuit reversal equivalent reorientations of M that are both circuit-cocircuit minimal. The implication follows from Corollary 3.2.

• (3) ⇒ (1). The proof is the same as for (2) ⇒ (1) except that, at the end, -A M and -B M are cocircuit reversal equivalent reorientations of M that are both cocircuit minimal. The implication again follows from Corollary 3.2.

• (4) ⇒ (1), and ( 6) ⇒ (1) assuming M has no coloops. The two implications are the dual statements of (3) ⇒ (1) and ( 5) ⇒ (1), respectively.

Finally, let us mention that the relations between the implication (5) ⇒ (1) and the other ones could also be handled from the decomposition into acyclic and totally cyclic parts, along with the convolution formula for the Tutte polynomial, similarly as in [START_REF] Gioan | Circuit-cocircuit reversing systems in regular matroids[END_REF].

We end with an open question. By direct computation, the number of circuitcocircuit reversal classes and the number of bases differ by a rather large margin for small non-regular oriented matroids. So, does there exist an absolute constant K > 1 such that the number of bases of a non-regular oriented matroid is at least K times the number of circuit-cocircuit reversal classes?

Theorem 2 . 1 .

 21 Let M be an oriented matroid on a linearly ordered set. Then (1) t(M; 1, 1) = # circuit-cocircuit minimal reorientations of M, (2) t(M; 1, 2) = # cocircuit minimal reorientations of M, (3) t(M; 2, 1) = # circuit minimal reorientations of M, (4) t(M; 1, 0) = # (circuit-)cocircuit minimal acyclic reorientations of M, (5) t(M; 0, 1) = # circuit(-cocircuit) minimal totally cyclic reorientations of M.

Acknowledgements

The second author, Chi Ho Yuen, would like to thank Matthew Baker for suggesting the problem, and Spencer Backman for introducing him the work of the first author, Emeric Gioan. The role of the first author of this paper has been to simplify and extend a preprint written at the initiative of the second author.


Marthe Bonamy

Oscar Defrain

Meike Hatzel

Jocelyn Thiebaut

Jocelyn Thiebaut Avoidable

Avoidable paths in graphs

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A graph G is chordal if every induced cycle is of length three. A classical result of Dirac [START_REF] Andrew | On rigid circuit graphs[END_REF] states that every chordal graph has a simplicial vertex, that is, a vertex which neighbourhood is a clique. However, not all graphs exhibit the nice structure of chordal graphs, and the statement does not extend to general graphs.

From simplicial vertices to avoidable paths

One way to generalise Dirac's result is through the following more flexible notion.

Definition 1.1 (Avoidable vertex). A vertex v in a graph G is avoidable if every induced path on three vertices with middle vertex v is contained in an induced cycle in G.

Note that in a chordal graph, every avoidable vertex is simplicial. The next theorem can be inferred from [START_REF] Ohtsuki | Minimal triangulation of a graph and optimal pivoting order in a sparse matrix[END_REF][START_REF] Berry | Separability generalizes Dirac's theorem[END_REF][START_REF] Aboulker | Vertex elimination orderings for hereditary graph classes[END_REF]; see also [BCG + 19] for a nice introduction.

Theorem 1.2. Every graph has an avoidable vertex.

Recently in [BCG + 19], the authors considered a generalisation of the concept of avoidable vertices to edges, and extended Theorem 1.2 to that notion.

Definition 1.3 (Avoidable edge

). An edge uv in a graph G is avoidable if every induced path on four vertices with middle edge uv is contained in an induced cycle in G. This notion naturally generalises to paths, as follows.

Definition 1.5 (Extension). Given an induced path P in a graph G, an extension of P is an induced path xP y in G for some vertices x, y.

Definition 1.6 (Failing). An induced path P in a graph G is failing if there is no induced cycle of G containing P .

Definition 1.7 (Avoidable). A path P in a graph G is avoidable if it is induced and has no failing extension. Given a subgraph G of G, we say that

P is an avoidable path of G in G if it is avoidable in G and V (P ) ⊆ V (G ).
A graph G is P k -free if it does not contain a P k , that is, an induced path on k vertices. In [BCG + 19] the authors conjecture that for every positive integer k, every graph either is P k -free or contains an avoidable path on k vertices. This conjecture is motivated by the following result of Chvátal et al. [START_REF] Chvátal | Dirac-type characterizations of graphs without long chordless cycles[END_REF], which generalises Dirac's theorem. A C p -free graph is a graph where every induced cycle has at most p -1 vertices. The C 4 -free graphs are exactly the chordal graphs. Unless specified otherwise, we consider cycles to be induced.

Theorem 1.8 (Chvátal et al. [START_REF] Chvátal | Dirac-type characterizations of graphs without long chordless cycles[END_REF]). For every positive integer k, every C k+3 -free graph either is P k -free or contains an avoidable path on k vertices.

In fact, Theorem 1.8 originally states the existence of a simplicial path in the class of C k+3 -free graphs. A simplicial path is an induced path with no extension: it is avoidable by vacuity. Note that these two definitions coincide in such a class, as no cycle on at most k + 2 vertices can contain the extension of an induced path on k vertices.

Here, we confirm the aforementioned conjecture [BCG + 19, Conjecture 1], as follows.

Theorem 1.9. For every positive integer k, every graph either is P k -free or contains an avoidable P k .

In fact, we prove Theorem 1.9 using a stronger induction hypothesis, in the exact same flavour as [START_REF] Chvátal | Dirac-type characterizations of graphs without long chordless cycles[END_REF], see Theorem 2.4 in Section 2.

Consequences

We point out that the proof of Theorem 1.9 is self-sufficient, thus this supersedes the arguments for theorems 1.2, 1.4 and 1.8.

By using ingredients of Theorem 2.4 (namely Lemma 2.3), we obtain a way to build more than one avoidable P k .

Corollary 1.10. For every positive integer k, graph G and subset

X ⊆ V (G) such that G[X] is connected, either G-N [X] is P k -free or there is an avoidable P k of G in G-N [X].
Corollary 1.11. For every positive integer k and graph G, either G does not contain two non-adjacent P k , or it contains two non-adjacent avoidable P k .

Since Corollary 1.11 is not as straightforward as its predecessor, we include a proof.

Proof. Let Q 1 and Q 2 be two non-adjacent P k . By Corollary 1.10, either G -N [Q 1 ] is P k -free or there is an avoidable P k of G in G -N [Q 1 ]. The first outcome is ruled out by the existence of Q 2 . Let Q 2 be an avoidable P k of G in G -N [Q 1 ].
We repeat the argument with Q 2 instead of Q 1 , and obtain an avoidable

P k of G in G -N [Q 2 ], call it Q 1 .
The two paths Q 1 and Q 2 are two non-adjacent avoidable P k , as desired.

We can also wonder: Question 1.12. For every positive integer k, does every graph G either not contain two disjoint P k , or contain two disjoint avoidable P k ?

We know the answer to be positive in the case k ∈ {1, 2}, due to [BCG + 19, Theorems 3.3 and 6.4]. The answer turns out to be negative in all other cases, as exhibited in the following counter-example for k 3, which consists of a cycle on 2k -1 vertices with an added vertex adjacent to two consecutive vertices on the cycle (see Figure 1 for the case k = 3). This graph contains two disjoint P k , and it has 2k vertices, so any two disjoint P k are in fact complementary in the graph. Suppose that it contains two disjoint avoidable P k , and note that each intersects the triangle (otherwise the complement would not be a path). Since there are three vertices in the triangle, there is an avoidable P k containing a single vertex in the triangle. This P k has a failing extension, a contradiction. Figure 1: A graph that contains two disjoint P 3 (in blue and in red) but no two disjoint avoidable P 3 (there is a unique partition into two disjoint P 3 , up to symmetry). In green, a failing extension of the blue path.

In Section 3, we present a concise algorithm which follows the proof of Theorem 2.4. As discussed there, the algorithm has complexity O(n k+2 ) which, while naive, is the right order of magnitude under ETH.

A stronger induction hypothesis

All graphs considered in this paper are finite, simple and loopless. Given a graph G, we denote by V (G) its set of vertices, and by E(G) ⊆ {{x, y} | x, y ∈ V (G), x = y} its set of edges. Edges are denoted by uv (or vu) instead of {u, v}. If uv is an edge, then we say that u and v are adjacent. Given a vertex u, the neighbourhood N (u) of u is the set of vertices of G that are adjacent to u. The closed neighbourhood N

[u] of u is the set N (u) ∪ {u}. If X ⊆ V (G), then we define N [X] := x∈X N [x] and N (X) := N [X] \ X. The subgraph of Claim 2.6. Every P k in G -N [u] dominates N (u).
Proof. Assume towards a contradiction that there is a P k in G -N [u], call it Q, which is not adjacent to some vertex v ∈ N (u). Then G -N [{u, v}] contains a P k . Let G be the graph obtained from G by merging u and v into a vertex u . Since G has fewer vertices than G, the property H R (G , k, u ) holds by minimality of G. By Lemma 2.3, the property H R (G, k, u) holds, a contradiction.

Let G := G -N [u].
Then G contains a P k . As G contains fewer vertices than G, the property H B (G , k) holds. Let Q be an avoidable P k of G . By assumption, Q is not an avoidable P k of G. So there is a failing extension xQy of Q in G. Since Q has no failing extension in G , we can assume without loss of generality that y ∈ N (u). It follows that x ∈ N (u): otherwise the cycle xQyu contradicts the fact that xQy is failing. By definition of an extension, xQy is an induced path. Let z be the only neighbour of y in Q, and let us now consider the path xQ -z. It is a P k , and it does not intersect N [u]. However, no vertex in it is adjacent to y which lies in N (u), contradicting Claim 2.6.

Lemma 2.7. The property H B (G, k) holds for every k.

Proof. Assume towards a contradiction that for some k, the property H B (G, k) does not hold. By Lemma 2.5, the property H R (G, k, u) holds for every vertex u ∈ V (G). In other words, the graph G contains a P k but no avoidable P k , and for every vertex

u ∈ V (G), either G -N [u] is P k -free or there is an avoidable P k of G in G -N [u].
We derive the following claim.

Claim 2.8.

Every P k in G dominates V (G).
Proof. Suppose there is a P k , call it Q, that does not dominate some vertex u of G. Since H R (G, k) holds, either G -N [u] is P k -free or there is an avoidable

P k of G in G -N [u].
The first case contradicts the existence of Q, and the second contradicts the fact that H B (G, k) does not hold.

Since H B (G, k) does not hold, G contains a P k , say Q, that is not avoidable. So it has a failing extension xQy. Let z be the only neighbour of y in Q, and consider the path xQ -z. It is an induced P k and none of its vertices is adjacent to y. This contradicts Claim 2.8. Finally, lemmas 2.5 and 2.7 together contradict G being a counter-example. Theorem 1.9 directly follows from Theorem 2.4.

An algorithm for Theorem 2.4

By going through the proof and extracting the key ingredients, we obtain a straightforward algorithm verifying both properties (see Algorithm 1).

The algorithm uses the subprocedure InducedPath that, given a graph G and a positive integer k, decides whether G contains a P k . If it does, the procedure returns one, otherwise it returns null. The naive algorithm for that (testing all subsets of size k) has complexity O(n k ). However, this is nearly optimal. Indeed, the problem of finding a P k in a given graph is W[1]-hard1 when parametrised by k (see [CFK + 15, Ex. 13.16, p. 460]).

Algorithm 1 finds an avoidable path of given length in a given graph, if any.

1: procedure FindAvoidablePathRefined(G, k, u)

2:

for all v ∈ N (u) do for all u ∈ V (G) do

9: if InducedPath(G -N [u], k) = null then 10:
return FindAvoidablePathRefined(G, k, u)

11:

return InducedPath(G, k)

In fact, the hinted reduction has a linear blow-up, so it follows that there is no f (k) • n o(k) algorithm under ETH.

Let k be a positive integer, and let B(n) (resp. R(n)) be the worst case complexity of FindAvoidablePath (resp. FindAvoidablePathRefined) on an n-vertex graph with parameter k. We have

B(n) n•n k +max(R(n), n k ), and R(n) n•n k +max(R(n- 1), B(n -2))
. We obtain R(n) n k+2 and B(n) n k+2 + n k+1 . While this may well be improved, the known limitations for finding an induced path on k vertices also apply for an induced avoidable path on k vertices (by Theorem 1.9, if the first exists, then so does the second). Therefore, the order of magnitude of this naive algorithm is correct.

Note that there is a yet more naive algorithm blindly checking for every subset of size k if it corresponds to an avoidable path. That algorithm has comparable complexity to ours (though slightly worse, at least at first sight). However, we wanted to emphasise that our proof of Theorem 2.4 is constructive and yields an elementary algorithm. Also, we believe that it provides an outline of the proof which might be helpful to the reader.

Conclusion

Given the discussions in Section 1.2, it is tempting to ask when a graph admits three (or more) disjoint (resp. pairwise non-adjacent) avoidable paths. Note that though Corollary 1.10 arms us with sufficient conditions for there to be more than two avoidable P k , we do not believe that the corresponding sufficient conditions are necessary. However, it seems the picture is murky already for chordal graphs.

It is tempting to wonder whether we can obtain another avoidable structure. Though in some cases the very notion of extension becomes unclear (what should an extension of a clique be?), it does not seem like any other structure survives the test of chordal graphs or simple ad hoc constructions-even when allowing a family of graphs instead of fixing a single pattern (like a path on k vertices). This motivates us to formulate the following question.

Question 4.1. Does there exist a family H of connected graphs, not containing any path, such that any graph is either H-free or contains an avoidable element of H?

The notion of avoidability in this context is deliberately left up to interpretation.

  Theorem 1.4 (Beisegel et al. [BCG + 19]). Every graph has an avoidable edge.

if

  InducedPath(G -N [{u, v}], k) = null then 4: G ← G with u and v merged into u 5: return FindAvoidablePathRefined(G , k, u ) 6: return FindAvoidablePath(G -N [u], k) 7: procedure FindAvoidablePath(G, k) 8:

see e.g. [CFK+ 15] for definitions around complexity

Acknowledgements

We gratefully acknowledge support from Nicolas Bonichon and the Simon family for the organisation of the 4 th Pessac Graph Workshop, where this research was done. We are indebted to Michał Pilipczuk for providing helpful references regarding the complexity of finding an induced path of given length. Last but not least, we thank Peppie for her unwavering support during the work sessions.

* The first author has been supported by the ANR project GrR ANR-18-CE40-0032. The second author has been supported by the ANR project GraphEn ANR-15-CE40-0009. The third author was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (ERC Consolidator Grant DISTRUCT, grant agreement No 648527).

G induced by X, denoted by G[X], is the graph (X, E(G) ∩ {{x, y} | x, y ∈ X, x = y}), and G -X is the graph G[V (G) \ X]. Given two adjacent vertices u 1 and u 2 of G, the graph obtained by merging u 1 and u 2 is the graph obtained from G by replacing u 1 and u 2 with a new vertex u such that N (u) = N ({u 1 , u 2 }). Given a graph G and two subsets X and Y of V (G), we say that

We first define two useful properties.

Definition 2.1 (Basic property H B ). Given a positive integer k and a graph G, the property H B (G, k) holds if either G is P k -free or there is an avoidable P k in G.

Given a positive integer k and a graph G, the property

Note that property H R does not directly imply property H B . We also emphasise the fact that an avoidable path in a subgraph is not necessarily an avoidable path in the whole graph.

We now prove a form of heredity in H R .

Lemma 2.3. Let k be a positive integer, G a graph and u 1 u 2 an edge of G. Let G be the graph obtained from G by merging the two vertices u 1 and

Proof. Suppose G -N [u] contains a P k , and that H R (G , k, u) holds but not H R (G, k, u 1 ). Since G -N [u] is not P k -free, there is an avoidable

Since H R (G, k, u 1 ) does not hold, Q is not an avoidable P k of G. Thus, there is a failing extension xQy of Q in G. Note that x, y, u 1 , and u 2 are all pairwise distinct. Hence, xQy is an extension of Q in G , and there is an induced cycle C in G containing the path xQy. If u ∈ C, then the cycle C is also an induced cycle in G containing xQy, a contradiction. Therefore, u ∈ C. By replacing u with either u 1 , u 2 or the edge u 1 u 2 as appropriate, we obtain an induced cycle in G containing xQy, a contradiction.

We are now ready to prove the main technical result of this paper.

Theorem 2.4. For every positive integer k and every graph G, both properties H B (G, k) and H R (G, k) hold.

Proof. Suppose the statement is false and consider a counter-example G which is minimal with respect to the number of vertices.

Lemma 2.5. The property H R (G, k) holds for every k.

Proof. We proceed by contradiction. Suppose that H R (G, k, u) does not hold for some k and some vertex u ∈ V (G), that is, there exists a P k in G -N [u], and every P k in G -N [u] has a failing extension. We prove the following.


Julien Baste
email: julien.baste@lip6.fr

Didem Gözüpek
email: didem.gozupek@gtu.edu.tr

Mordechai Shalom
email: cmshalom@telhai.ac.il

Dimitrios M Thilikos

Minimum Reload Cost Graph Factors Graphs 1

Keywords: Parameterized Complexity, Graph Factors, Reload Costs

The concept of Reload cost in a graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the two edges. This concept has various applications in transportation networks, communication networks, and energy distribution networks. Various problems using this model are defined and studied in the literature. The problem of finding a spanning tree whose diameter with respect to the reload costs is smallest possible, the problems of finding a path, trail or walk with minimum total reload cost between two given vertices, problems about finding a proper edge coloring of a graph such that the total reload cost is minimized, the problem of finding a spanning tree such that the sum of the reload costs of all paths between all pairs of vertices is minimized, and the problem of finding a set of cycles of minimum reload cost, that cover all the vertices of a graph, are examples of such problems. In this work we focus on the last problem. Noting that a cycle cover of a graph is a 2-factor of it, we generalize the problem the the problem of finding an r-factor of minimum reload cost of an edge colored graph. We prove several NP-hardness results for special cases of the problem. Namely, bounded degree graphs, planar graphs, bounded total cost, and bounded number of distinct costs. For the special case of r = 2, our results imply an improved NP-hardness result. On the positive side, we present a polynomial-time solvable special case which provides a tight boundary between the polynomial and hard cases in terms of r and the and the maximum degree of the graph. We then investigate the parameterized complexity of the problem, prove W[1]-hardness results and present an FPT-algorithm.

Introduction

Edge-colored graphs can be used to model optimization problems in diverse fields such as bioinformatics, communication networks, and transportation networks. Reload cost in an edge-colored graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the two edges.

The reload cost concept has various applications in transportation networks, communication networks, and energy distribution networks. For instance, a multi-modal cargo transportation network involves different means of transportation, where the (un)loading of cargo at transfer points is costly [START_REF] Galbiati | The complexity of a minimum reload cost diameter problem[END_REF]. In energy distribution networks, transferring energy between different carriers cause energy losses and reload cost concept can be used to model this situation [START_REF] Galbiati | The complexity of a minimum reload cost diameter problem[END_REF]. In communication networks, routing often requires switching between different technologies such as cable and fiber, where data conversion incurs high costs. Switching between different service providers in a communication network also causes switching costs [START_REF] Galbiati | The complexity of a minimum reload cost diameter problem[END_REF]. Recently, dynamic spectrum access networks, a.k.a. cognitive radio networks, received a lot of attention in the communication networks research community. Unlike other wireless networks, cognitive radio networks are envisioned to operate in a wide range of spectrum; therefore, frequency switching has adverse effects in delay and energy consumption [START_REF] Arkoulis | On the optimal, fair and channel-aware cognitive radio network reconfiguration[END_REF][START_REF] Celik | Green cooperative spectrum sensing and scheduling in heterogeneous cognitive radio networks[END_REF][START_REF] Gözüpek | A spectrum switching delay-aware scheduling algorithm for centralized cognitive radio networks[END_REF]. This frequency switching cost depends on the frequency separation distance; hence, it corresponds to reload costs.

The reload cost concept was first introduced by Wirth and Steffan [START_REF] Wirth | Reload cost problems: minimum diameter spanning tree[END_REF] who focused on the problem of finding a spanning tree whose diameter with respect to the reload costs is smallest possible. Other works also focused on numerous optimization problems regarding reload costs: the problems of finding a path, trail or walk with minimum total reload cost between two given vertices [START_REF] Gourvès | The minimum reload s-t path, trail and walk problems[END_REF], numerous path, tour, and flow problems [START_REF] Amaldi | On minimum reload cost paths, tours, and flows[END_REF], the minimum changeover cost arborescence problem [START_REF] Galbiati | On minimum changeover cost arborescences[END_REF][START_REF] Gözüpek | Parameterized complexity of the MINCCA problem on graphs of bounded decomposability[END_REF][START_REF] Gözüpek | Constructing minimum changeover cost arborescenses in bounded treewidth graphs[END_REF][START_REF] Gözüpek | On the complexity of constructing minimum changeover cost arborescences[END_REF], problems about finding a proper edge coloring of a graph such that the total reload cost is minimized [START_REF] Gözüpek | Edge coloring with minimum reload/changeover costs[END_REF], and the problem of finding a spanning tree such that the sum of the reload costs of all paths between all pairs of vertices is minimized [START_REF] Gamvros | Reload cost trees and network design[END_REF].

An r-factor of a graph is an r-regular spanning subgraph. A 2-factor is also called a cycle cover and has many applications in areas such as computer graphics and computational geometry [START_REF] Meijer | An algorithm for computing simple k-factors[END_REF], for instance for fast rendering of 3D scenes. In an edge-weighted graph, the problem of finding a cycle cover with minimum cost can be solved in polynomial-time [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]. Its reload cost counterpart was studied by Galbiati et.al. in [START_REF] Galbiati | On minimum reload cost cycle cover[END_REF]. In particular, they proved that the minimum reload cost cycle cover problem is NP-hard even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. In this work, we build on this work by studying the minimum reload cost r-factor problem, which is a more generalized version of the minimum reload cost cycle cover problem. In particular, we prove several NP-hardness results for the special cases of this problem. Namely, bounded degree graphs, planar graphs, bounded total cost, and bounded number of distinct costs. For the special case of r = 2, we prove an NP-hardness result stronger than the one in [START_REF] Galbiati | On minimum reload cost cycle cover[END_REF]. On the positive side, we present a polynomial-time solvable special case. We then investigate the parameterized complexity of this problem, prove W [START_REF] Amaldi | On minimum reload cost paths, tours, and flows[END_REF]-hardness results and present a fixed parameter tractable algorithm.

Preliminaries

Sets, vectors: Given a non-negative integer n, we denote by N ≥n the set of all integers x such that x ≥ n. If n 1 , n 2 ∈ N ≥0 , we denote by [n 1 , n 2 ] the set of integers x such that n 1 ≤ x ≤ n 2 . We also use [n] instead of [1, n]. Given a finite set X and an integer s ∈ N ≥0 , we denote by X s the set of all subsets of A with exactly s elements. For a set X and an element x we use X + x and X -x as shorthands for X ∪ {x} and X \ {x}, respectively. For two vectors u = (u 1 , . . . , u d ) and v = (v 1 , . . . , v d ) over the reals, we write

u ≤ v if u i ≤ v i for every i ∈ [d].
Graphs: All graphs we consider in this paper are undirected, finite, and without self loops or multiple edges. Given a graph G, we denote by V (G) the set of vertices of G and by E(G) the set of edges of G. We say that a vertex v ∈ V (G) and an edge e ∈ E(G)

are incident if v ∈ e, that is, v is an endpoint of e. Given a vertex v ∈ V (G), we denote by E G (v) the set of edges of G that are incident to v. The degree of v in G, denoted by deg G (v) is |E G (v)|. We also define the maximum degree of G as ∆(G) = max{deg G (v) | v ∈ V (G)}, the minimum degree of G as δ(G) = min{deg G (v) | v ∈ V (G)},
and the average degree of G as deg(G). For a subset X of V (G), we denote by G[X] the subgraph of G induced by X. A graph is r-regular if all its vertices have degree r.

We say that a graph H is a factor of a graph G when V (H) = V (G) and E(H) ⊆ E(G). An r-regular factor of G is termed an r-factor of G.

Parameterized complexity: We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions. A parameterized problem is a language L ⊆ Σ * × N. For an instance

I = (x, k) ∈ Σ * × N, k is called the parameter.
A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f , and a constant c such that given an instance I = (x, k), A (called an FPT algorithm) correctly decides whether

I ∈ L in time bounded by f (k) • |I| c .
A parameterized problem is in XP if there exists an algorithm A and two computable functions f and g such that given an instance I = (x, k), A (called an XP algorithm) correctly decides whether

I ∈ L in time bounded by f (k) • |I| g(k) .
A parameterized problem with instances of the form I = (x, k) is para-NP-hard if it is NP-hard for some fixed constant value of the parameter k. Note that, unless P = NP, a para-NP-hard problem cannot be in XP, hence it cannot be FPT either.

Within parameterized problems, the class W [START_REF] Amaldi | On minimum reload cost paths, tours, and flows[END_REF] may be seen as the parameterized equivalent to the class NP of classical optimization problems. Without entering into details (see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for the formal definitions), a parameterized problem being W [START_REF] Amaldi | On minimum reload cost paths, tours, and flows[END_REF]-hard can be seen as a strong evidence that this problem is not FPT. To transfer W [START_REF] Amaldi | On minimum reload cost paths, tours, and flows[END_REF]-hardness from one problem to another, one uses an FPT reduction, which given an input I = (x, k) of the source problem, computes in time f (k) • |I| c , for some computable function f and a function c, an equivalent instance I = (x , k ) of the target problem such that k is bounded by a function depending only on k. The following problem is a W [START_REF] Amaldi | On minimum reload cost paths, tours, and flows[END_REF]-hard problem that we will use in our reductions.

Multicolored Clique

Input: A graph G, an integer k, a coloring function χ : V (G) → [k].
Parameter: k. Question: Does G contain a clique on k vertices with one vertex from each color class?

Multicolored Clique is known to be W [START_REF] Amaldi | On minimum reload cost paths, tours, and flows[END_REF]-hard on general graphs, even in the special case where all color classes have the same number of vertices [START_REF] Pietrzak | On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems[END_REF]. Clearly, we can also assume that every color class is an independent set since the problem is indifferent to edges within the same color class.

Tree decompositions: A tree decomposition of a graph G = (V, E) is a pair D = (T, X ), where T is a tree and X = {X t | t ∈ V (T )} is a collection of subsets of V (G) such that:

• t∈V (T ) X t = V ,
• for every edge uv ∈ E, there is a t ∈ V (T ) such that {u, v} ⊆ X t , and

• for every {x, y, z} ⊆ V (T ) such that z lies on the unique path between x and y in T , X x ∩X y ⊆ X z .

We call the vertices of T nodes of D and the sets in X bags of D. The width of D is max t∈V (T ) |X t |-1.

The treewidth of G, denoted by tw(G), is the smallest integer w such that there exists a tree decomposition of G of width w. A tree decomposition in which the tree T is restricted to be a path is called a path decomposition. The pathwidth of G, denoted by pw(G), is the smallest integer w such that there exists a path decomposition of G of width w.

A tree decomposition is rooted if we distinguish in T some specific vertex r, and consider T as a rooted (on r) tree. We denote such a tree decomposition by a triple D = (T, X , r).

Nice tree decompositions: Let D = (T, X , r) be a rooted tree decomposition of G, and G = {G t | t ∈ V (T )} be a collection of subgraphs of G. We say that the ordered pair (D, G) is nice if the following conditions hold:

• X r = ∅ and G r = G,
• every node of D has at most two children in T ,

• for each leaf t ∈ V (T ), X t = ∅ and G t = (∅, ∅). Such a node t is called a leaf node,

• if t ∈ V (T ) has exactly two children t and t , then X t = X t = X t , G t = G t ∪ G t , and E(G t ) ∩ E(G t ) = ∅.
The node t is called a join node.

• if t ∈ V (T ) has exactly one child t , then exactly one of the following holds.

-X t = X t + v for some v / ∈ X t and G t = (V (G t ) + v, E(G t )). The node t is called vertex-introduce node and the vertex v is the introduced vertex of X t .

-X t = X t and G t = (G t , E(G t ) + e) where e is an edge of G with endpoints in X t . The node t is called edge-introduce node and the edge e is the introduced edge of X t .

-X t = X t -v for some v ∈ X t and G t = G t . The node t is called forget node and v is the forget vertex of X t .

The notion of a nice pair defined above is essentially the same as the one of nice tree decomposition in [START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF] (which in turn is an enhancement of the original one, introduced in [START_REF] Kloks | Computations and Approximations[END_REF]). As already argued in [START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF][START_REF] Kloks | Computations and Approximations[END_REF], given a tree decomposition, it is possible to transform it in polynomial time to a tree decomposition D of the same width and construct a collection G such that (D, G) is nice.

Reload cost model: For reload costs, we follow the notation and terminology defined by [START_REF] Wirth | Reload cost problems: minimum diameter spanning tree[END_REF]. We consider an edge-colored graph G where edge colors are taken from a finite set X and the coloring function is χ : E(G) → X. The reload costs are given by a function c : X 2 → N ≥0 where c(x 1 , x 2 ) = c(x 2 , x 1 ) for each (x 1 , x 2 ) ∈ X 2 . The cost of traversing two incident edges e 1 , e 2 of G is tc(e 1 , e 2 ) = c(χ(e 1 ), χ(e 2 )). Given a subgraph H of G and a vertex v ∈ V (H), we define the reload cost of v in H as rc χ,c (H, v) = {e 1 ,e 2 }∈( E H (v)

2

) tc(e 1 , e 2 ) and the reload cost of H as rc χ,c (H) = v∈V (H) rc χ,c (H, v). When χ and c are clear from the context, we write rc(v) and rc(H) instead.

Problem statement:

The problem we study in this paper can be formally defined as follows for every r ∈ N ≥2 :

Minimum Reload Cost r-Factor (r-MRCF) Input: A graph G, an edge-coloring χ, a reload cost function c, and a non-negative integer k. Output: Is there an r-factor H of G with reload cost at most k, i.e., rc(H) ≤ k?

Given an instance (G, χ, c, k) of r-MRCF we consider the following parameters:

• the maximum degree ∆(G) of G, • the treewidth tw(G) of G,
• the number of colors q = |X|,

• the number of distinct costs:

d = |{c(x 1 , x 2 ) | (x 1 , x 2 ) ∈ X 2 }|,
• the minimum traversal cost c min = min{c(x 1 , x 2 ) | (x 1 , x 2 ) ∈ X 2 }, and

• the total cost k.
Clearly, we can assume that ∆(G) ≥ r + 1, and also δ(G) ≥ r since otherwise the instance is trivial.

Let k min = c min • |V (G)| • r 2 .
Note that the reload cost of every r-factor is at least k min . Therefore, we can also assume that k ≥ k min .

A summary of the results regarding the classical and parameterized complexity of the r-MRCF problem is shown in Table 1 andTable 2

pw(G) 2 k min < r + 4 if r = 2 4/3 otherwise. W[1]-hard (Theorem 4) tw(G) + min{q, ∆(G)} FPT(Theorem 5)
Table 2: Summary of parameterized complexity results for the r-MRCF problem.

Classical Complexity of r-MRCF

The following construct will be used in our reductions. A diamond is a graph on four vertices and five edges, that is obtained by adding one chord to a cycle on four vertices. Clearly, a diamond contains two vertices of degree two and two vertices of degree three. The degree two vertices are termed as the tips of the diamond. A joker is a monochromatic diamond, that is, a diamond whose edges have the same color. In our reductions, every a joker J will have exactly one vertex adjacent to other vertices of the graph. This vertex will always be a tip of J, and we will term it as the connecting tip of J. Given a joker J and a 2-factor F , it is easy to see that exactly one of the following happens:

• F ∩ E(J) is the 4-cycle of J, and F \ E(J) does not contain any edges incident to J.

• F ∩ E(J) is a triangle of J, F \ E(J) contains exactly two edges incident to J both of which are incident its connecting tip.

Furthemore, since our cost functions satisfy c(λ, λ) = 0 for every color λ, and F ∩ E(J) is always a cycle, the joker edges do not affect the cost of F . When we describe a 2-factor F , these properties allow us to leave the edges F ∩ E(J) unspecified since they are implied by the edges of F \ E(J). Such a partial description is valid if and only if the connecting tip have degree zero or two. Finally, a 5-joker is a cycle on five vertices with an added chord. This graph has one triangle with one degree 2 vertex that we will refer to as the tip of the 5-joker. Note that a 5-joker has all the properties of a joker.

Another construct that we use in our reductions is a graph Q that is obtained from the clique on + 1 vertices by subdividing -2 arbitrary edges twice (into three edges) and removing the middle edge of each one. Clearly, Q contains + 1 vertices of degree and 2( -2) vertices of degree one. In total G has 3 -3 vertices.

Galbiati et.al. proved in [START_REF] Galbiati | On minimum reload cost cycle cover[END_REF] that 2-MRCF, a.k.a. the minimum reload cost cycle cover problem, is NP-hard even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. In the following, we obtain a hardness result for r-MRCF, which in particular implies a stronger hardness result for the special case of r = 2.

Theorem 1. r-MRCF is NP-hard for every r ≥ 2 even when ∆(G) ≤ r + 2, d = 2, k = k min = 0 and q = min{r, 3}.

Proof. We start by proving the claim for r = 2, that is, we prove that 2-MRCF is NP-hard when ∆(G) ≤ 4, d = q = 2, k = k min . The proof is by reduction from the Monotone 1 in 3-SAT problem which is known to be NP-hard [START_REF] Thomas | The complexity of satisfiability problems[END_REF]. An instance of Monotone 1 in 3-SAT is an expression φ that consists of n boolean variables x 1 , . . . , x n and m clauses c 1 , . . . , c m . Every clause c j consists of three literals j,1 , j,2 , j,3 , each of which is either an occurrence of some variable x i or its negation xi . A clause is satisfied by a truth assignment if exactly one of its literals is satisfied by it, and φ is satisfied if all its clauses are satisfied. Monotone 1 in 3-SAT is the problem of determining whether a given expression φ has a satisfying assignment.

Given an instance φ as described above, we construct an instance (G, χ, c, k) of 2-MRCF. The set of colors is X = {red, blue}, thus q = 2. The traversal cost between two identical colors is zero and the traversal cost between red and blue is 1, thus d = 2. Furthermore, k = 0. We have c min = 0, which implies that k min = 0 = k. To complete the reduction, we construct a graph G with ∆(G) = 4 whose edges are colored with colors from X.

The graph G is the union of n vertex disjoint variable gadgets with vertex sets X 1 , . . . , X n , m vertex disjoint clause gadgets with vertex sets C 1 , . . . , C m , and 3m + 4n vertex disjoint jokers, that is, four jokers

J (u) i , J (v) i , J (2)
i , J (4) i for every variable x i and a joker J i,k for every occurrence of it. In our construction, every edge will join two vertices of the same gadget. However, we will allow a vertex to appear in two (but not more) of the above gadgets. Every gadget will have maximum degree 4, where vertices shared with another gadget have degree only 2 inside the gadget. This will ensure that ∆(G) = 4. We now proceed with the description of the individual gadgets.

u i,0 u i,1 u i,2 u i,3 u i,4 u i,p-1 v i,0 v i,1 v i,2 v i,3 v i,4 v i,p-1 v i,p u i,p z + i,1 z - i,2 z + i,3 z - i,4 z + i,p z - i,1 z + i,2 z - i,3 z + i,4 z - i,p w i,1 w i,3 w i,4 wi,2
Let x i be a variable that has p occurrences in φ. Consult Figure 1 for the description of the corresponding variable gadget. We set

X i = U i ∪ V i ∪ W i ∪ Z + i ∪ Z - i where U i = {u i,0 , u i,1 , . . . , u i,p }, V i = {v i,0 , v i,1 , . . . , v i,p }, W i = {w i,1 , w i,2 , w i,3 , w i,4 } Z D i = {z D i,1 , . . . , z D i,p } for D ∈ {+, -}.
The edge set induced by X i is the disjoint union of p red triangles, p blue triangles, a blue cycle on the four vertices u i,0 , w i,1 , w i,2 , w i,3 and a red cycle on the four vertices v i,0 , w i,1 , w i,4 , w i,3 as depicted in Figure 1. Note that every vertex of Z + i (resp. Z - i ) has degree two, and both its incident edges are red (resp. blue).

For every clause c j , the gadget C i has six vertices a j , b j , d j , s j,1 , s j,2 , s j,3 connected with blue edges as depicted in Figure 2.

We identify each of the vertices w i,2 , w i,4 , u i,k and v i,k with a tips of the jokers J

i , J

i , J

i , and J (v) i , respectively. Finally, for every literal j,k that is the k -th occurrence of some variable x i we identify the vertex s j,k with the vertex z + i,k (resp. z - i,k ) if the occurrence is positive (resp. negative) and we identify the vertex z - i,k (resp. z + i,k ) with a tip of the joker that corresponds to this literal.

To complete this part of the proof, it remains to show that φ has a satisfying assignment if and only if G contains a 2-factor H with zero reload cost. We suppose that φ has a satisfying assignment and provide a partial description of the 2-factor H incrementally. Recall that a partial description is valid if and only if every vertex has degree two, except possibly some connecting tips that are isolated. Let x i be a variable assigned true by the assignment. H[X i ] consists of all the blue edges of G[X i ]. Clearly, the traversal cost between these edges is zero. It is also easy to see that all the vertices of H[X i ] have degree two except the vertices Z + i , w i,4 and one of u i,p , v i,p (depending on the parity of p) all of which are isolated. Note that u i,p , v i,p , w i,4 and all the vertices of Z + i corresponding to negative occurrences of x i are connecting tips of some joker. We remain with the vertices of Z + i corresponding to positive occurrences of x i that are isolated but should have degree two in order to make (the partial description of) H valid. Proceeding in the same way for the variables assigned false, we get a subgraph H in which all the vertices of the variable gadgets which are not connecting tips have degree two, except the vertices of Z + i corresponding to positive occurrences of variables assigned true and the vertices of Z - i corresponding to negative occurrences of variables assigned false. In other words, these are exactly the vertices of Z + i ∪ Z - i that correspond to literals satisfied by the assignment. By adding to H the cycle a j d j b j s j,p for every clause c j (where j,p is its unique literal satisfied by the assignment), we get a 2-factor H of zero cost.

a j b j d j s j,1 s j,2 s j,3
Conversely, suppose that G contains a 2-factor H of zero reload cost. Consider the vertices U i of the gadget X i . Since every such vertex has two incident blue edges and two incident red edges, H contains either the two blue edges or the two red edges. We conclude that the vertices of U i -u i,0 are covered either by all the red triangles incident to them or all the blue ones. By symmetry, the same holds for the vertices of V i -v i,0 . However, we note that the choice of the color (blue or red) must be identical in both U i and V i since otherwise a positive traversal cost is incurred at each of the vertices w i,1 , w i,3 . Therefore, H[X i ] is the subgraph of G[X i ] that consists of all the blue (or all the red) edges. We assign true to x i if H[X i ] contains the blue edges and false otherwise. It remains to show that this assignment satisfies φ. Consider a clause gadget C j . H must contain the two edges d j a j and d j b j . Furthermore, since every vertex s j,k is identified with a z vertex, H contains either both edges of the clause gadget incident to s j,k or none of them. Since a j has degree 2 in H, exactly one of these three vertices, say s j,1 , has both incident edges of the clause gadget in H. Then, the two edges incident to s j,1 in the corresponding variable gadget are not in H. This implies that either j,1 is a positive occurrence of a positive variable, or a negative occurrence of a negative variable. In other words, j,1 is satisfied. The vertices s j,2 and s j,3 must have in H their incident (red or blue) edges in their corresponding variable gadgets. Then, each one of them is either a positive occurrence of a negative variable, or a negative occurrence of a positive variable. In other words, their corresponding literals are not satisfied. We conclude that C j is satisfied, and thus φ is satisfied.

We now prove the claim for any r ≥ 3. We need to show that r-MRCF is NP-hard even when t = 2, q = 3, k = k min = 0 and ∆ ≤ r + 2. Given an instance (G, χ, c, k) of 2-MRCF with ∆ ≤ 4, t = q = 2 and k = k min = 0, we construct an instance (G , χ , c , k ) of r-MRCF as follows. By eventually adding a monochromatic cycle of size 3, we may assume that G has an even number of vertices. The color set X is X ∪ {white} where white is not a color of X. Thus, q = 3. White edges are precisely the edges E(G ) \ E(G). The traversal cost c between white and every color is zero, and for any two colors of X, the traversal cost c is the same as c. Thus, t = 2 and c min = 0, implying that k min = 0 = k. Let P be a partition of the vertices V (G) into pairs. G is obtained from G by adding to G a Q r for every pair {u, v} ∈ P and identifying r -2 of its degree one vertices and u altogether with each other as well as identifying the remaining r -2 vertices and v with each other. Note that the pair {u, v} is not necessarily an edge of the graph. Every vertex of V (G ) ∩ V (G) has r -2 white incident edges and at most 4 other incident edges since ∆(G) ≤ 4, for a total of at most r + 2 edges. The degree of every vertex of V (G ) \ V (G) is r. Therefore, ∆(G ) ≤ r + 2. Let H be an r-factor of G . As the vertices of V (G ) \ V (G) are of degree exactly r in G , H contains all the edges incident to the vertices of V (G ) \ V (G), i.e. all the white edges. By removing these edges from H we get a 2-factor H of G. Moreover, rc(H) = rc(H ) since the white edges do not introduce a traversal cost. We conclude that (G, χ, c, k) has a 2-factor of zero cost if and only if (G , χ , c , k ) has an r-factor of zero cost.

The value of the parameter t in Theorem 1 is clearly tight. When t = 1, that is, when there is only one traversal cost, all the r-factors have the same reload cost. In this case the problem reduces to determining the existence of an r-factor. This problem is known to be polynomial-time solvable [START_REF] Pulleyblank | Faces of Matching Polyhedra[END_REF]. The following theorem states that the parameter ∆(G) of Theorem 1 is also tight.

Theorem 2. For every r ∈ N ≥2 , if ∆(G) = r + 1, then r-MRCF can be solved in polynomial time.

Proof. Recall that we assume δ(G) ≥ r. Let R be the vertices of degree r of G and R + = V (G) \ R the vertices of degree r + 1. Let also H be an r-factor of G. We observe that H is obtained by removing a perfect matching M of G[R + ] from G. Every edge e ∈ M reduces the reload cost by the sum of the traversal costs with all its incident edges. Therefore, rc(H) = rc(G) -e∈M w(e) where Both the result in [START_REF] Galbiati | On minimum reload cost cycle cover[END_REF] and Theorem 1 are for general graphs and hence leave the complexity of the problem open for special graph classes. In the following (in Theorem 3), we prove hardness of r-MRCF in planar graphs even under restricted cases. We need the following Lemma.

Lemma 1. Let G be a planar graph with an even number of vertices and δ(G) ≥ 2. There is a partition M of V (G) into pairs such that the multigraph G obtained by adding to G an edge between every pair of M is planar. Moreover, such a partition can be found in polynomial time.

Proof. We construct M incrementally, starting from M = ∅. At any given point of the execution of the algorithm M is a set of vertex-disjoint pairs of vertices. We add pairs to

M until ∪M = V (G), implying that M is a partition of V (G). A vertex v is paired (resp. unpaired ) if v ∈ ∪M (resp. v /
∈ ∪M ). We use a sweep line algorithm 1 that scans the embedding from left to right. Whenever the sweep line encounters a new inner face F , it pairs all the unpaired vertices of F , except possibly one vertex in case the number of unpaired vertices is odd. The pairing is done such that the pairs are non-crossing, i.e. such that one can add edges to G between the pairs while preserving planarity. Such a pairing can be easily obtained as follows. Let v 1 , v 2 , . . . , v 2 be the vertices to be paired, in the clockwise order they appear on the face F . The pairing, {{v 1 , v 2 } , . . . , {v 2 -1 , v 2 }} is a non-crossing pairing. If the number of unpaired vertices of F is odd, the rightmost unpaired vertex of F is left unpaired. When the sweeping phase is terminated, all the unpaired vertices are on the outer face, and their number is even. The algorithm terminates after processing the outer face exactly in the same way as an inner face was processed.

Theorem 3. For every r ∈ [2, 5], r-MRCF is NP-hard even when the input graph G is planar,

∆(G) ≤ r + 4, d = 2, k = k min , and q = 6 if r = 2 7 otherwise.
Proof. We start by proving the theorem for r = 2 by reducing an instance (G, χ, c, k

) of 2-MRCF with ∆(G) ≤ 4, d = 2, k = k min , q = 2 to an instance (G , χ , c , k ) of 2-MRCF, with ∆(G ) ≤ 6, d = 2, k = k min , q = 6
, and G is planar. We rename the colors of the original graph as 1 and 2, and we add four colors X C = {red,blue, green, yellow}. Therefore, q = 6. As for the cost function we use the following function c that is an extension of c and uses only costs from {0, 1}, i.e. d = 2.

c (λ, λ ) =        0 if λ = λ 0 if yellow ∈ {λ, λ } and {1, 2} ∩ {λ, λ } = ∅ 0 if 1 ∈ {λ, λ } and 2 / ∈ {λ, λ } 1 otherwise.
We consider a planar embedding of G where all crossings are polynomial on |V (G)| and no three edges cross the same point. G is obtained by replacing every crossing point of two edges e, e of G by a copy of the gadget depicted in Figure 3, and 9 jokers such that one tip of each joker is identified with a distinct vertex of the gadget. We observe that ∆(G ) ≤ 6, as required. For a gadget under consideration, the set of vertices that contain the index L (resp. R) are its left (resp. right) vertices, and the remaining vertices are its middle vertices. The left part (resp. right part) of the gadget is the subgraph induced by the left (resp. right) and middle vertices together. We refer to a four cycle m P a P,T t P a P,B for P ∈ {L, R} as a green cycle, to the triangle t T t L t R as the middle triangle, to a triangle that consists of an m-vertex, a t-vertex and an a-vertex as a blue or red triangle, and to the 8-cycle induced by the four c-vertices together with the four m-vertices as the yellow rectangle. Note that all these cycles have zero reload cost, though (despite their names) they are not monochromatic.

The two parts of the edge e (resp. e ) inherit their color from e (resp. e ). Clearly, V (G) ⊆ V (G ). Finally, k = 0.

It remains to show that G has a 2-factor with zero reload cost if and only if G has one. Suppose that G has a 2-factor F with zero cost. We construct a 2-factor F of G as follows.

A part of an original edge is in F if and only if the original edge is in F . Since F is a 2-factor of zero cost, all the original vertices have degree 2 in F and they incur a zero reload cost. Recall that we allow for the vertex of a gadget that is the connecting tip of a joker to be isolated in our description of F since such a vertex will be in a cycle of the joker in F . For every gadget that corresponds to a crossing point of two edges e and e , we proceed as follows to ensure that F incurs a zero cost in every gadget.

c L,T c R,T c L,B c R,B m T m B m L m R t L t T t R a L,T a R,T a L,B a R,B 1
• {e, e } ∩ F = ∅: In this case F contains the yellow rectangle and the middle triangle. Then F incurs a zero cost in this gadget.

• {e, e } ⊆ F : In this case F contains the two green cycles and the two paths c L,H m H c R,H for H ∈ {T, B}. Combining with the two parts of e and e incident to this gadget, the degree of every vertex of this gadget in F is 2. We recall that c (1, yellow) = c (2, yellow) = 0 and conclude that F incurs a zero cost in this gadget.

• |{e, e } ∩ F | = 1: Assume without loss of generality that e ∈ F and e / ∈ F . In this case F contains the left blue triangle, the right green cycle, and the two adjacent edges of the yellow rectangle, namely the path c L,T m L c L,B m B c R,B . Combining with the two parts of e incident to this gadget, the degree of every vertex of this gadget in F is 2. We note that c (χ(e), yellow) = 0 and conclude that F incurs a zero cost in this gadget.

Conversely, suppose that G has a 2-factor F with zero cost. Recall that for any two distinct colors λ, λ ∈ {red, blue, green, yellow} we have c (λ, λ ) = 1. Therefore, for every m-vertex the 2factor F contains two edges of the same color. If F contains two adjacent blue (resp. red) edges, it must contain the third edge colored 1 that completes the blue (resp. red) triangle because otherwise an a-vertex incurs a positive cost, since c (green, red) = c (green, blue) = 1. If F contains two adjacent green edges, then for the same reason, F contains the corresponding green cycle.

Consider one of the parts, say the left part of a gadget. Since t L is common to the blue, red and green cycles of this part, at most one of these cycles are in F . We consider two cases:

• F contains none of the cycles on the left part: Then the edges t L t R and t L t T are in F , implying that none of the cycles on the right part are in F . Since all the m vertices have degree 2 in F and none is covered by the inner cycles, F must contain the yellow rectangle.

Then none of the parts of e and e are in F .

• F contains one cycle on the left part: In this case, since the degree of t R must be 2 in F , F contains one cycle of the right part. Every cycle saturates one of the m vertices, for a total of two m vertices saturated. Then, the remaining two m vertices are saturated by four yellow edges that together form two edges of the yellow rectangle. We consider two sub-cases -F contains two non-adjacent edges of the yellow rectangle. In this case all the four yellow edges have degree 1. Therefore, both parts of e and both parts of e are in F .

-F contains two adjacent edges of the yellow rectangle. In this case two opposite corners of the yellow cycle, say c L,T and c R,B have one incident yellow edge, while the other two corners have either two or zero incident yellow edges. Then both parts of e (in the symmetric case, of e ) are in F , and none of the parts of the other edge is in F .

We conclude that for every edge e of G, either all its parts or none are in F . Then F implies a subgraph F of G. Since all the original vertices have degree 2 in F , they have degree 2 in F , i.e. F is a 2-factor of G. Furthermore, the cost at every original vertex is zero since c extends c. Now for any r ∈ [START_REF] Mark De Berg | Computational Geometry: Algorithms and Applications[END_REF][START_REF] Celik | Green cooperative spectrum sensing and scheduling in heterogeneous cognitive radio networks[END_REF], we have to reduce an instance (G, χ, c, k) of 2-MRCF where ∆(G) ≤ 6, d = 2, k = k min , q = 6, to an instance (G , χ , c , k ) of r-MRCF, where ∆(G ) ≤ r + 4, d = 2, k = k min , q = 7 and G is planar. Note that, since whenever G is planar, we have δ(G) ≤ 5, it does not make sense to consider other values of r.

If G is odd, we subdivide an edge and add a 5-joker whose tip is identified with the newly created vertex. We color all the edges with the color of the original edge. This creates an equivalent instance having all the properties assumed for G. By Lemma 1, there is a pairing M of the vertices of G such that edges can be added between each pair of vertices while still preserving planarity. For every pair {u, v} ∈ M we will add a gadget that will have the desired properties of Q r , and in addition will preserve planarity. Namely, the gadget will have 2(r -2) vertices of degree one, all the remaining vertices of degree r, and will have a planar embedding in which all the degree one vertices are in the outer face. Half (i.e., (r -2)) of the degree one vertices of the gadget are identified with u and the remaining half are identified with v. Now every new vertex has degree r and the degree of every original vertex increased by r -2. The new edges are colored with a new color λ such that for every color λ we have c (λ , λ) = 0. (G , χ , c , k ) has an r-factor F such that rc(F ) = 0 if and only if (G, χ, c, k) has a 2-factor F with rc(F ) = 0. We omit the proof of this fact since it is identical to the non-planar case.

We now describe the gadget depending on the value of r.

• r = 3. In this case the gadget is a Q 3 which has the desired planarity properties.

• r = 4. In this case the gadget is a Q 4 . However, in order to get the planarity properties, the subdivided edges of the K 5 should constitute a matching.

• r = 5. In this case we use the gadget depicted in Figure 4. Proof. The proof is by an FPT reduction from Multicolored Clique. We first note that Multicolored Clique is W[1]-hard even when the number of colors k is restricted to be odd. Indeed, the problem can be reduced to its special case as follows. Let (H, c, k) be an

G, χ, c, k) of 2-MRCF. Let V (H) = V 1 V 2 • • • V k , where V i is the set of vertices of V (G) that are colored i, for i ∈ [k]. Notice that |V (G) ≥ t • k.
Let W be an Eulerian circuit of the complete graph K k , which exists since k is odd. We assume that V (K k ) = [k]. We also assume, for ease s 3,1 of exposition, that W starts with the sequence of vertices 1, 2, . . . , k, where every vertex i of this sequence is considered as the first occurence of i in W . We also assume that the last vertex of W (i.e. the vertex before the first occurence of 1) is 3. Clearly, every i ∈ [k] appears in W exactly k def = (k -1)/2 times. The vertex set of G is the disjoint union of three sets U, S, and T where

s 3,1 U 1,1 U 2,1 U k,1 U i,i ′ U j,j ′ U 3,k ′ u 1,1,1 u 2,1,1 u k,1,1 u i,i ′ ,1 u j,j ′ ,1 u 3,k ′ ,1 u 1,1,|V 1 | u 2,1,|V 2 | u k,1,|V k | u i,i ′ ,|V i | u j,j ′ ,|V j | u 3,k ′ ,|V 3 | s 1,2 s i,j
• U consists of k copies U i,1 , . . . , U i,k of V i for every i ∈ [k],
for a total of k 2 sets. For every i ∈ [k], we number the vertices of V i from 1 to |V i |, and we number the vertices of every copy U i,j accordingly, as u i,j,1 , . . . u i,j,|V i | .

• S consists of k 2 vertices s i,j , one for every arc ij of W , We proceed with the description of the edge set of G, which contains three types of edges depending on their endpoints. Every edge has one endpoint in U and the other endpoint is in one of U, S or T .

• T = T 1 ∪ T 2 ∪ • • • ∪ T k ,
• S -U edges: Let e = ij be an arc of W such that e is incident to the i -th (resp. j -th) occurence of i (resp. j) in W . Then s i,j is adjacent to every vertex of U i,i and to every vertex of U j,j (see Figure 5).

• U -U edges: The U -U edges form |V (H)| vertex-disjoint paths, one path on k vertices for every v ∈ V (H). The path corresponding to the -th vertex of V i is is u i,1, u i,2, . . . u i,k , (see Figure 7).

• T -U edges: For every i ∈ [k] and every ∈ [|V i | -1], the vertex t i, is adjacent to u i,1, , u i,1, +1 , u i,k , and u i,k , +1 (see Figure 7).

We prove two properties of G that are necessary to conclude the lemma. We now proceed with the calculation of |E(G)|. Every U -S edge is incident to a vertex of U , and every vertex of U has two incident U -S edges. Therefore, the number of U -S edges is 2k • |V (H)|. The total number of U -U and U -T edges is (k + 1)(V (H)), since for every vertex v ∈ V (H) we have a cycle that contains k + 1 vertices, namely all the copies of v and a t vertex. Thus, |E(G)| = (3k + 1)

Claim 1. deg(G) < 6α. t i,1 u i,1,1 u i,2,1 t i,1 u i,2,1 u i,3,1 t i,1 u i,k ′ -1,1 u i,k ′ ,1 t i,1 u i,1,2 u i,2,2 t i,1 u i,2,2 u i,3,2 t i,1 u i,k ′ -1,2 u i,k ′ ,2 t i,|V i |-1 u i,1,|V i | u i,2,|V i | u i,2,|V i | u i,3,|V i | u i,k ′ -1,|V i | u i,k ′ ,|V i | t i,2 t i,2 t i,2 t i,|V i |-1 t i,|V i |-1
• |V (H)|. As |V (G) ≥ t • k ⇒ |V (G)|/(V (G) -k) ≤ t/(t -1) = α, we conclude that deg(G) is 2|E(G)| |V (G)| < 2(3k + 1) • |V (H)| (k + 1) • (|V (H)| -k) < 6 • |V (H)| |V (H)| -k < 6α. Claim 2. pw(G) ≤ k 2 + 3. Proof of Claim 2. Clearly, pw(G) ≤ pw(G \ S) + |S| = pw(G \ S) + k 2 .
We observe that the edge set of G \ S consists of U -U and T -U edges that form connected components T i ∪ ∪ k j =1 U i,j as depicted in Figure 7. Every such component has a path decomposition of k • |V i | bags with at most 4 vertices in a bag, as depicted in Figure 6. Therefore, pw(G \ S) ≤ 3 and the claim follows.

We proceed with the description of the coloring function χ and the traversal cost function c. The color set is V (H) ∪ {white}. In other words, the vertices of H corresponds to colors in the constructed instance H ; that is, there is a color in H corresponding to each vertex in H. All the U -U and T -U edges are colored white, and the S -U edges are colored upon their endpoint in U as follows. For every S -U edge e with endpoint u i,j, , we define χ(e) = v i, . The traversal cost cost c(v i, , v i, ) = 0, and the two edges incident to a vertex s i,j incur a zero cost since the adjacent vertices are u i,i ,1 and u j,j ,1 that correspond to the vertices v i,1 and v j,1 of K, which are adjacent in H.

Conversely, suppose that H contains a 2-factor F with rc(F ) = 0. Every vertex s i,j is adjacent to two distinct vertices of U that correspond to two distinct vertices v, v of V (H). Furthermore, since the cost at vertex s i,j is zero, we conclude that v and v are adjacent in H. In particular, v and v are in different color classes. Therefore, s i,j is adjacent to one vertex from each of U i,i and U j,j . The second edge incident to these vertices in F is not white, since otherwise it incurs a positive traversal cost. Thus, the other edge is also a U -S edge. We conclude that the k 2 vertices S are all in one cycle C K that also contains k 2 vertices from U , one from every set U i,i . Furthermore, two consecutive vertices of U in C K correspond to two adjacent vertices of H.

All the remaining cycles must be in G \ S, which consists of k connected components

T i ∪ ∪ k i =1 U i,i , for every i ∈ [k].
The result is now apparent from Figure 7 that depicts this connected component. If a vertex u i,i , is in one of the remaining cycles, then all the vertices u i,i , for i ∈ [k ] are in the same cycle as u i,i , . Therefore, if a vertex u i,i , is in C K , then all the vertices u i,i , for i ∈ [k ] are in C K . Recall that C K contains one vertex u i,i , from every set U i,i . We conclude that these vertices correspond to the same vertex v i, of V i . We recall that consecutive U -vertices of C K correspond to two adjacent vertices of H. Therefore, the vertices U ∩ C K correspond to the vertices of a clique of H.

Given a graph G on n-vertices where n is even, a pairing collection of G is a collection M of pairs of vertices in G that forms a partition of V (G). We denote G + M = (V (G), E(G) ∪ M ). Notice that G + M can be a multi-graph as the pairings in M might already be edges of G. We prove the following lemma that will prove useful in our proof. Lemma 3. Let G be a n-vertex graph where n is even where pw(G) ≤ k for some k ≥ 1. Then G has a pairing collection M such that pw(G + M ) ≤ k + 1.

Proof. We say that a vertex v of a graph is k-simplicial if its neighbourhood induces a complete graph on k vertices. Proper k-paths are recursively defined as follows: A complete graph on k + 1 vertices is a proper k-path. A graph H on more than k + 1 vertices is a proper k-path if it contains a k-simplicial vertex v such that the removal of v results to a proper k-path with a simplicial vertex that belongs in the neighbourhood of v in H. Notice that this recursive definition gives rice to sequence of simplicial vertices where every two successive vertices are adjacent and such that all vertices of G appear in this sequence. Therefore every proper k-tree H has a hamiltonian path, which, in case H has an even number of vertices, implies that H contains a perfect matching. It was proved in [START_REF] Takahashi | Mixed searching and proper-path-width[END_REF] (see also [START_REF] Kaplan | Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques[END_REF]) that every graph G of pathwidth ≤ k is a spanning subgraph of a proper (k + 1)-path H. As a perfect matching in H is a pairing collection in G, the lemma follows. Proof. For r = 2 the Theorem is equivalent to Lemma 2. For r > 2 we present an FPT reduction from the base case, i.e. r = 2. using the same technique as in the proof of Theorem 1. Namely, given an instance (G, χ, c, k) of 2-MRCF with d = 2 and k = k min = 0 where deg(G) < 6, we λ of E t,v is the number of edges of E Gt (v) colored λ. Clearly, the sum of the entries of this vector, denoted by E t,v is |E Gt (v)|. The encoding of a single edge e colored χ(e) = λ, incident to v is the vector u λ that has a 1 in entry λ and zero elsewhere. We now define the set of all vectors encoding a subset of |E Gt (v) consisting of at most r edges. In other words, these are the sets of edges incident to v in G t that can be part of an r-factor of G: T k (E t ) ← ∞ for every E t ∈ E t . else if t is a leaf node then 6:

E t,v def = {E | E ≤ E t,v , E ≤ r}.
T t (()) = 0. The dynamic programming algorithm whose pseudo code is given in Algorithm 1 performs a bottom-up traversal of T and updates the tables T t at every node, and finally returns the result by inspecting the value T r (()) (recall that E r = {()}.

As for the running time of the algorithm, we observe that the dominant running time for a node is obtained in the case of a join node, in which case the running time is

O(|E t | • |E t |) = O * q+r

Figure 2 :

 2 Figure 2: The clause gadget corresponding to the clause c j .

e

  ∈E G (u)-e c(e, e ) + e ∈E G (v)-e c(e, e ) for every edge e = uv of G. Then, minimizing rc(H) boils down to the problem of finding a maximum weight perfect matching M of G[R + ] with the edge weight function w, which can clearly be solved in polynomial time.

Figure 3 :

 3 Figure 3: The planar gadget that replaces two crossing edges of G. The vertices marked with a circle are identified with a tip of a joker.

Figure 4 :

 4 Figure 4: The planar gadget used for the case r = 5.

4 2 .

 2 Parameterized Complexity of r-MRCF Lemma For every α > 1, 2-MRCF, parameterized by pw(G), is W[1]-hard even when d = 2, k = k min , and deg(G) < 6 • α.

Figure 5 :

 5 Figure 5: The S -U edges of G. A sample clique cycle appears in bold.

Figure 6 :

 6 Figure 6: A path decomposition of a connected component of G \ S.

Theorem 4 .

 4 For every r ∈ N ≥2 , r-MRCF, parameterized by pw(G), is W[1]-hard even when d = 2, k = k min and deg(G) is less than r + 4 if r = 2 4/3 otherwise.

  Note that |E t,v | ≤ q+r r . Let E, E ∈ E t,v encode two disjoint sets of edges incident to v. Each of E, E has an associated reload cost on v. The reload cost of their union E + E is the sum of their individual reload costs, plus the reload costs incurred by the traversals between the two sets, whichis c v (E, E ) def = λ λ c(λ, λ ) • E λ • E λ .Algorithm 1 DynProgRequire: An instance (G, χ, c, k) of r-MRCF Require: A nice pair D, G where D = (T, r, X ) is a tree decomposition of G.

1 :

 1 for t ∈ T (using a bottom-up traversal) do 2:

3 :t = r then 4 :

 34 if return T r (()) ≤ k. T r = ∅, E r = {()} 5:

r 2 (

 2 tw(G)+1) , ignoring polynomial factors. Alternatively, we can encode the vectors of E t,v using a binary vector of length ∆(G). In this case |E t | = ∆(G)+r r , implying the running time in the statement of the Theorem.

Table 1 :

 1 , respectively. Summary of classical complexity results for the r-MRCF problem.

	G	∆(G)	d	k	q
		≤ r + 2 2 k min min{r, 3} NP-hard (Theorem 1)
		r + 1				Polynomial (Theorem 2)
	Planar ≤ r + 4 2 k min	7	NP-hard (Theorem 3)
	Parameter	d	k		average degree

  Figure1: The variable gadget in Theorem 1 corresponding to a variable x i having p occurrences in φ. The solid edges are blue, the dashed edges are red. Every vertex surrounded with a circle is the connecting tip of a joker. For every k ∈ [p] exactly one of z + i,k , z - i,k is a connecting tip. The gadget contains p + 4 connecting tips.

  instance of Multicolored Clique where k is even. Let (H , c , k + 1) be an instance of Multicolored Clique, where (H , c ) is obtained by adding a universal vertex v colored k + 1 to H. It is easy to see that H contains a clique on k vertices with one vertex from each color class if and only if H contains one. Also, by adding dummy vertices, we can also assume that each chromatic class in the input graph of Multicolored Clique has at least t vertices, where t = α α-1 . Given an instance (H, c, k) of Multicolored Clique with k odd, we construct an instance (

  where every set T i consists of |V i | -1 vertices t i,1 , t i,2 , . . . , t i,|V i |-1 .

  for E t ∈ E t do Partial r-factors that do not contain e 18: T t (E t ) ← T t (E t ) 19: for E t ∈ E t \ E t do Partial r-factors that contain e 20:E t ← E t -(u χ(e) , u χ(e) , 0, . . . , 0) T t (E t ) ← T t (E t ) + c u (E t , u χ(e) ) + c v (E t , u χ(e))for E t = (e v , E t ) ∈ E t do 24:if e v = r and T t (E t ) < T t (E t ) then t is the cartesian product × v∈Xt E t,v , i.e. every element of E t is a vector of |X t | vectors that encodes a set of edges incident to X t that is possibly part of an r-factor of G. Clearly, |E t | ≤ For every t ∈ T we maintain a function T t : E t → N ≥0 that returns for any given E t ∈ E t , the minimum cost of a partial r-factor whose edges incident to X t are encoded by E t .

	21: 22: 23: 25: T q+r else r |Xt| ≤ q+r r w+1 .	t is a forget node that forgets v and has child t

7:

else if t is a join node with children t , t then 8: for E t ∈ E t do 9: for E t ∈ E t do 10: if E t + E t ∈ E t then 11: cost ← T t (E t ) + T t (E t ) + c Xt (E t , E t ). 12: if cost < T t (E t + E t ) then T t (E t + E t ) ← cost 13: else if t introduces the vertex v and has child t then 14: for E t ∈ E t do 15: T t ((0, E t )) = T t (E t ). w.l.o.g. v is the first vertex of X t . 16: else if t introduces the edge e = uv and has child t then E t ⊆ E t . 17: t (E t ) ← T t (E t ) We extend this definition to any subset X of vertices as c X (E, E ) def = x∈X c x (E, E ). E

A well known technique in computational geometry[START_REF] Mark De Berg | Computational Geometry: Algorithms and Applications[END_REF].

 [START_REF] Cygan | Parameterized Algorithms[END_REF]Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010) and by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.

c(v, white) is 1 for every v ∈ V (H) and c(white, white) = 0. Finally, for every v, v ∈ V (H)

Finally, we set k = 0. This completes the construction of (G, χ, c, k), which can be clearly performed in polynomial time. We now prove that H has a k-clique with one vertex from every color class if and only if G has a 2-factor F with rc(F ) = 0. Assume that H has a clique K with exactly one vertex from every color, and suppose without loss of generality that K consists of the first vertices of each color class. Let F be the 2-factor of G consisting of the following cycles.

It is easy to see that every vertex is in exactly one of these cycles. Furthermore, the edges of the vertex cycles are all white, incurring a reload cost of zero. It remains to show that that the edges of the clique cycle also incur a zero cost. Indeed, the two edges incident to a vertex u i,j, ∈ U incur a construct an instance (G , χ , c , k ) of r-MRCF where d = 2 and the average degree of G is less than r + 4/3 by adding to G a pair collection, and replacing every new edge by the gadget Q r . By the last part of the proof of Theorem 1, G has an r-factor of zero cost if and only if G has a 2-factor of zero cost.

We conclude that the average degree of G is less than

Proof of Claim 4. According to Lemma 3, there is a pairing collection

The operation of replacing each pair of M by a Q r can be reflected in the path decomposition as follows. Each bag has k + 1 vertices and among the edges with endpoints in this bag, at most (k + 1)/2 of them can be pairs that belong in M . This means that after the insertion of at most (k + 1)/2 copies of Q r in each bag the new path decomposition will have width at most k + 1 + (k + 1)/2 • (r + 1) = (pw(G) + 1)

Finally, we note that r is a constant of the problem. Therefore, the function proven in Claim 4, is a function of pw(G) as required.

We conclude with the following algorithmic result. Proof. We assume that the graph G is given together with a nice pair (D, G) where D = (T, X , r). Indeed, by using for instance the algorithm of Bodlaender et al. [START_REF] Hans | A c k n 5-approximation algorithm for treewidth[END_REF], we can compute in time 2 O(tw(G)) • n a tree decomposition of G of width at most 5tw(G). Note that this running time is clearly dominated by the running time stated in Theorem 5. Recall also that, by [START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF][START_REF] Kloks | Computations and Approximations[END_REF], given a tree decomposition, it can be transformed in polynomial time into a nice pair.

We first introduce some notation. Let t ∈ T , v ∈ X t , and F an r-factor of G. The graph F t = F [V (G t )] is a partial r-factor of G. We encode the edges E Gt (v) incident to v in G t as a vector E t,v of non-negative integers indexed by the colors of the instance. The value of the entry