Marina Groshaus
email: groshaus@dc.uba.ar.

‡ Pavol Hell

Sulamita Klein

¶ Loana
email: loana@ic.uff.br.

Tito Nogueira

Fábio Protti

Cycle transversals in bounded degree graphs †

Keywords: approximation algorithms, cycle-transversals, transversals

In this work we investigate the algorithmic complexity of computing a minimum C k -transversal, i.e., a subset of vertices that intersects all the chordless cycles with k vertices of the input graph, for a fixed k ≥ 3. For graphs of maximum degree at most three, we prove that this problem is polynomial-time solvable when k ≤ 4, and NP-hard otherwise. For graphs of maximum degree at most four, we prove that this problem is NP-hard for any fixed k ≥ 3. We also discuss polynomial-time approximation algorithms for computing C3-transversals in graphs of maximum degree at most four, based on a new decomposition theorem for such graphs that leads to useful reduction rules.

Introduction

The graphs considered in this work are finite and with no loops and multiple edges. Let H be a fixed family of graphs. An H-subgraph of a graph G is an induced subgraph of G isomorphic to a member of H. A graph is H-free if it contains no H-subgraph. An H-transversal of a graph G is a subset T ⊆ V (G) such that T intersects all the H-subgraphs of G. Clearly, if T is an H-transversal of G then G -T is H-free. Moreover, if T is small (minimum) then G -T is a large (maximum) induced H-free subgraph of G. We remark that the term "covering" sometimes appears in the literature with the same meaning as "transversal", see for instance [8].

For a fixed family H, the general decision problem called H-TRANSVERSAL can be formulated as follows: given a graph G and an integer , decide whether G contains an H-transversal T such that |T | ≤ . Yannakakis proved that this problem is NP-complete [START_REF] Yannakakis | Node-and edge-deletion NP-complete problems[END_REF]; in fact, he proved a more general result which says that the problem of finding the minimum number of vertices of a graph G whose deletion results in a subgraph satisfying a property π which is hereditary on induced subgraphs is NP-hard. The following table summarizes some interesting special cases of the H-TRANSVERSAL problem. Problems 1 to 5 are NP-complete due to Yannakakis' result [START_REF] Yannakakis | Node-and edge-deletion NP-complete problems[END_REF]. Problem 1 is precisely the MAXIMUM INDUCED BIPARTITE SUBGRAPH problem. An edge version of this problem (whose goal is to find a maximum induced bipartite subgraph with maximum number of edges) is considered in [START_REF] Cornaz | The maximum induced bipartite subgraph problem with edge weights[END_REF]; still, an O(mn) algorithm is developed in [START_REF] Reed | Finding odd cycle transversals[END_REF] to find odd cycle transversals with bounded size. Problem 2 is the well known VERTEX COVER problem [8]. Problem 3 has an interesting edge version: find the minimum number of edges whose deletion leaves a triangle-free subgraph (see [START_REF] Manic | Packing triangles in low-degree graphs and indifference graphs[END_REF]). Problems 4 and 5 are interesting due to their connections to parameterized edge editing theory (see [START_REF] Dantas Da Silva | Applying modular decomposition to parameterized cluster editing problems[END_REF][START_REF] Gramm | Graph-modeled data clustering: Fixed-parameter algorithms for clique generation[END_REF]). To the best of our knowledge, the complexities of Problems 6 to 10 remain as open questions; in particular, Problem 7 is cited in [START_REF] Fishburn | Interval Orders and Interval Graphs[END_REF] as an important question in order theory (the maximum indifference order contained in an interval order).

Problem

Let k denote a fixed integer, k ≥ 3. In this work we investigate the case H = {C k }. (C k denotes a chordless cycle with k vertices.) We consider the following problem:

C k -TRANSVERSAL INPUT: a graph G, an integer QUESTION: does G contain a C k -transversal of size at most ?

The C k -TRANSVERSAL problem is NP-complete for general graphs as a consequence of Yannakakis' result [START_REF] Yannakakis | Node-and edge-deletion NP-complete problems[END_REF]. A way of dealing with this intractability is to assume some restrictions on the input graph. Restricting its maximum degree turns out to be a widely employed and natural strategy. In particular, we can seek dichotomy results as follows: for a fixed value of ∆ (the maximum degree of the input graph), find an integer p such that C k -TRANSVERSAL is polynomial-time solvable if k ≤ p, and NP-complete otherwise. Alternatively, we can fix k and determine p such that C k -TRANSVERSAL is polynomial-time solvable if ∆ ≤ p, and NP-complete otherwise. The latter approach is well studied in algorithmic graph theory. For example, coloring a graph is polynomial-time solvable for graphs of maximum degree at most three [START_REF] Brooks | On colouring the nodes of a network[END_REF], and NP-complete otherwise [5]. Still in this context, Gallucio, Hell and Nešetřil conjecture that the H-colouring problem for graphs of maximum degree at most three is NP-complete, even when H is a triangle-free graph with chromatic number three [7]. (The H-colouring problem asks, for a fixed graph H, whether an input graph G admits a mapping c :

V (G) → V (H) such that xy ∈ E(G) implies c(x)c(y) ∈ E(H).)
The following table summarizes our results on the boundary between tractability and NP-completeness If ∆ = 2, minimum C k -transversals are trivially obtained in polynomial time for any k, since in this case the input graph is a disjoint union of paths and cycles. In Section 2, we show that C k -TRANSVERSAL for graphs of maximum degree at most three is polynomial-time solvable for k ≤ 4 and NP-complete otherwise. For graphs of maximum degree at most four, we show in Section 3 that C k -TRANSVERSAL is NP-complete for any fixed k ≥ 3. This NP-completeness result trivially extends to ∆ ≥ 5.

In view of the hardness of finding minimum C 3 -transversals (or triangle-transversals) when ∆ = 4, a polynomial-time approximation algorithm for this case is presented in Section 3, based on a new decomposition theorem for graphs of maximum degree at most four and certain reduction rules. Some interesting polynomial cases are also discussed.

As we shall see, the NP-completeness results above are still valid for bipartite graphs and even values of k.

Unless otherwise stated, n stands for the number of vertices of a graph. For a subset S of vertices, define N (S) = (∪ v∈S N (v)) \ S. We use the notation N (u, v) instead of N ({u, v}).

Graphs of maximum degree at most three

The following definition is useful and will be used throughout this paper:

Definition 1 An edge e ∈ E(G) is called a k-free edge if e is contained in no induced C k of G.
The observation below deals with the case k = 3:

Observation 2 Let G be a graph such that ∆ = 3. If e is a 3-free edge then T is a triangle-transversal of G if and only if T is a triangle-transversal of G -e.

Observation 2 leads to a simple polynomial-time algorithm for finding a minimum triangle-transversal of G in a graph of maximum degree at most three.

Theorem 3 TRIANGLE-TRANSVERSAL is polynomial time solvable for graphs of maximum degree at most three.

Proof: Let G be a graph with ∆ = 3. In order to find a minimum triangle-transversal of G, first remove 3-free edges; next, observe that each connected component of the remaining graph can be a triangle, a K 4 or a diamond (K 4 minus one edge). Hence a minimum triangle-transversal consists of one vertex per component (if it is a diamond or a triangle) or two vertices (if it is a K 4 ).

2

We remark that Observation 2 is not true for C k -transversals with k > 3. For instance, consider k = 4 and the graph K 4 -e (a complete graph with four vertices minus one edge). Every edge of this graph is 4-free. In addition, since K 4 -e contains no induced C 4 , the empty set is a C 4 -transversal of it. By removing the edge linking the vertices with degree two in K 4 -e, we obtain a new graph for which a C 4 -transversal must contain at least one vertex. Now we deal with C 4 -transversals in graphs of maximum degree at most three. A C 4 -transversal of G will also be called a square-transversal.

Definition 4 A circular ladder (also called prism) is a cubic graph with vertex set V = {a 1 , . . . , a j } ∪ {b 1 , . . . , b j }, for j ≥ 3, and edge set

E = {a i b i | 1 ≤ i ≤ j} ∪ {a i a i+1 , b i b i+1 | 1 ≤ i ≤ j -1} ∪ {a 1 a j , b 1 b j }.
A Möbius ladder is defined similarly, with edges a 1 b j , b 1 a j instead of a 1 a j , b 1 b j . (See Figure 1.)

A minimum square-transversal of a circular (Möbius) ladder is {a 1 , a 3 , . . . , a j-1 } if j is even, or {a 1 , a 3 , . . . , a j } if j is odd. Theorem 5 Let G be a connected cubic graph graph with n ≥ 6. Then G contains no 4-free edges if and only if G is a circular ladder or a Möbius ladder.

Proof: If G is a circular (Möbius) ladder then G contains no 4-free edges. Conversely, assume that G contains no 4-free edges. Clearly, G has an even number of vertices. We need the following claims: Claim 1: G is either triangle-free or a circular ladder with n = 6.

Proof of Claim 1: Suppose G contains a triangle abc. Since edge ab lies in an induced C 4 , there must exist two new vertices d and e and edges ad, be, de in G. Edge bc must also lie in an induced C 4 . If there exists an induced cycle cbed, by the degree restriction e has a new neighbor f and we get a contradiction, since edge ef cannot lie in an induced C 4 . Thus, cd / ∈ E(G) and there exists a new vertex f and edges cf , ef . If df / ∈ E(G) then edge ac does not lie in an induced C 4 , which is impossible. Therefore, df ∈ E(G) and G is a circular ladder with six vertices. This completes the proof of Claim 1.

Claim 2: If n ≥ 8 then there exists an edge uv ∈ E(G) such that the subgraph induced by N (u, v) is a 2K 2 (a graph formed by two isolated copies of K 2 ).

Proof of Claim 2: Since n ≥ 8, by Claim 1 G is triangle-free. Therefore, for any edge

uv ∈ E(G) we have |N (u, v)| = 4. Let N (u)\{v} = {u 1 , u 2 } and N (v)\{u} = {v 1 , v 2 }, and let u 1 uvv 1 be an induced C 4 . Clearly, u 1 u 2 , v 1 v 2 /
∈ E(G). We have three cases:

Case 1: both edges u 2 v 1 , u 1 v 2 exist. If u 2 v 2 ∈ E(G)
then G is cubic with six vertices (in fact, G is a Möbius ladder with six vertices). This is a contradiction. Hence, u 2 v 2 / ∈ E(G). But then u 2 must have a new neighbor u 3 , and edge u 2 u 3 cannot lie in an induced C 4 . Impossible. Thus Case 1 does not occur.

Case 2:

u 2 v 1 ∈ E(G) but u 1 v 2 / ∈ E(G).
Edge vv 2 must lie in an induced C 4 , which is either vv 2 u 2 u or vv 2 u 2 v 1 , implying u 2 v 2 ∈ E(G). Now, u 1 must have a new neighbor u 3 , and edge u 1 u 3 cannot lie in an induced C 4 . Again, this is impossible. Thus Case 2 does not occur as well.

Case 3: neither u 2 v 1 nor u 1 v 2 is an edge of G. If u 2 v 2 ∈ E(G), nothing remains to prove. Otherwise, u 2 must have a new neighbor u 3 such that uu 1 u 3 u 2 is an induced C 4 , implying u 3 v 1 /
∈ E(G) (otherwise there would be a triangle). Hence, the subgraph induced by N (u, u 1 ) is a 2K 2 . This completes the proof of Claim 2.

We conclude the proof of the theorem by induction. The result is valid for n = 6. Now assume

n ≥ 8. By Claim 2, choose uv ∈ E(G) such that N (u)\{v} = {u 1 , u 2 }, N (v)\{u} = {v 1 , v 2 }, u 1 v 1 , u 2 v 2 ∈ E(G) and u 1 u 2 , v 1 v 2 , u 1 v 2 , v 1 u 2 / ∈ E(G). Construct G = (G -{u, v}) ∪ {u 1 u 2 , v 1 v 2 }. Observe that G is cubic with n-2 vertices. Moreover, in G , N (u, v) induces a connected subgraph; thus G is connected. We show that G contains no 4-free edges. It is clear that edges u 1 u 2 , v 1 v 2 , u 1 v 1 , u 2 v 2 ∈ E(G )
in G must be yu 1 uu 2 , that is, yu 2 ∈ E(G ). Let z be the third neighbor of y. Since yz is not a 4-free edge in G , let yzz z be a C 4 in G containing it, where z , z ∈ {u 1 , u 2 , v 1 , v 2 }. Then N (y) = {u 1 , u 2 , z, z }, contradicting the fact that G is cubic.
Hence, there must exist a common neighbor z of y and v 1 , i.e., u 1 yzv 1 is an induced C 4 both in G and G . Therefore, G contains no 4-free edges. By the induction hypothesis, G is a circular (Möbius) ladder. To conclude the proof of the theorem, observe that G, in this case, is also a circular ladder or Möbius ladder.

2

Theorem 6 Let G be a connected graph with n ≥ 6, ∆ = 3, and containing no 4-free edges. Then G is a subgraph (not necessarily induced) of a circular ladder or Möbius ladder.

Proof: Since G contains no 4-free edges, there are no vertices with degree one (pendant vertices) in G.

Let n 2 (G) be the number of vertices with degree two in G. We use induction on n 2 (G). If n 2 (G) = 0 then the result is true by Theorem 5. Assume then n 2 (G) > 0.

Claim: There exist two nonadjacent vertices with degree two in G.

Proof of the Claim: Suppose the claim is false. Then the subset of vertices with degree two in G is a clique Q. By the degree restriction, Q induces a K j , for some j ∈ {1, 2, 3}. If j = 3, G itself would be a K j , which is impossible. For the case j = 2, assume that G is a graph with minimum number of vertices containing two adjacent vertices x, y with degree two and n -2 vertices with degree three. Let x = y, y = x be neighbors of x, y, respectively. Clearly, x = y . Moreover, vertices x , y must be adjacent, otherwise edge xy would be 4-free, and edge x y is contained in another induced C 4 which misses x, y. By degree arguments, it is easy to see that G must contain at least 8 vertices. Let G = G-{x, y}. Note that G contains two adjacent vertices with degree two (x and y ) and n-4 vertices with degree three, and satisfies 6 ≤ |V (G )| < |V (G)|, a contradiction. Thus the existence of a connected graph G satisfying the hypotheses of the statement and containing two adjacent vertices with degree two and n -2 vertices with degree three is impossible. Finally, if j = 1, let w be the only vertex in G with degree two, and let x, y be its neighbors. Vertices x, y must have a common neighbor z other than w, otherwise edges wx, wy would be 4-free. Suppose that x, y have another common neighbor z 1 / ∈ {z, w}. In this case z 1 is not adjacent to z, otherwise edge zz 1 is 4-free. Let z 2 be the third neighbor of z; the only way to have edge zz 2 contained in a C 4 is to assume the existence of cycles zz 2 z 1 x and zz 2 z 1 y. Again, z 2 must have a third neighbor z 3 ; however, no C 4 can contain edge z 2 z 3 because of the degree restrictions. Thus, the only common neighbor of x, y is z. This means that edges xz, yz are contained in distinct induced C 4 's other than wxzy, say C 1 and C 2 . Consider G = G -w + {xy, ax, by, ab}, where a, b are new vertices. In G , edge xy is not a chord of C 1 , C 2 . Then G is a graph satisfying the hypotheses of the statement and containing two adjacent vertices (a and b) with degree two and |V (G )| -2 vertices with degree three. But this is impossible, as said above. This completes the proof of the claim. Now, let x, y be two nonadjacent vertices in G with degree two. Assume without loss of generality that the distance d between x and y is minimum. Consider a path P linking x and y, isomorphic to P j (the chordless path with j vertices), for j = d + 1 ≥ 3. If j = 3, define a supergraph G of G by creating a new vertex a and new edges ax, ay; and, if j = 4, define G by creating a new edge xy. In both cases, the new edges created are not 4-free, and since n 2 (G ) < n 2 (G), by the induction hypothesis G is a subgraph of a circular (Möbius) ladder, and so is G.

It remains to consider the case j ≥ 5. Write P j = a 1 a 2 . . . a j . We show by induction on j that, in this case, G is isomorphic to a ladder: a circular ladder (or Möbius ladder) minus edges a 1 a j , b 1 b j (or a 1 b j , b 1 a j ) (recall Definition 4). The case j = 5 can be proved by inspection (each a i must have a distinct neighbor b i , and b i cannot be adjacent to a i+1 , for i = 1, 2, 3, 4; this implies that vertices b 1 , b 2 , . . . , b 5 induce P 5 ). For j > 5, let b j be a neighbor of a j such that b j = a j-1 , and let G = G -{a j , b j }. In G , a 1 and a j-1 are linked by a path isomorphic to P j-1 . In addition, a j-1 and b j must have a common neighbor b j-1 = a j . Note that edges a j-2 a j-1 and a j-1 b j-1 must be contained in a same induced C 4 in G. This implies that edge a j-1 b j-1 is contained in a C 4 in G , that is, G contains no 4-free edges. Thus, by the induction hypothesis, G is a ladder formed by vertices a 1 , . . . , a j-1 , b 1 , . . . , b j-1 . Then G is a ladder as well. This completes the proof.

2

Theorem 7 The SQUARE-TRANSVERSAL problem is polynomial time solvable for graphs of maximum degree at most three.

Proof: Remove 4-free edges from G. By Theorem 6, each connected component with at least 6 vertices of the remaining graph is a subgraph of a circular (Möbius) ladder; for such components, square-transversals can be easily obtained. For components with less than 6 vertices, square-transversals can be directly obtained by inspection. 2

To conclude this section, we analyze the C 5 -TRANSVERSAL problem in graphs of maximum degree at most three.

Theorem 8 C 5 -TRANSVERSAL is NP-complete for graphs of maximum degree at most three.

Proof: The problem is clearly in NP. The hardness proof is a reduction from a special version of SAT, denoted here 3SAT 3 : each clause contains at most three literals, and each variable occurs exactly three times, twice positively and once negatively. The NP-completeness of this problem is a consequence of the results in [START_REF] Cerioli | Partition into cliques for cubic graphs: planar case, complexity and an approximation algorithm[END_REF][START_REF] Lichtenstein | Planar formulae and their uses[END_REF].

Let F be a boolean formula of 3SAT 3 with n variables x 1 , x 2 , . . . , x n and m clauses C 1 , C 2 , . . . , C m . Construct a graph G of maximum degree at most three as follows. Create a subgraph G i for each variable x i , 1 ≤ i ≤ n, as in Figure 2. Edges a i b i and a i b i represent the two positive occurrences of x i , whilst edge a i b i represents its negative occurrence.

Next, create a subgraph H j for each clause C j , 1 ≤ j ≤ m, as in Figure 3. Denote W j = {u j , v j , u j , v j , u j , v j }.

Finally, for each clause C j containing variables x h , x i , x k with h ≤ i ≤ k, identify pairs of adjacent vertices as follows: (a) if x h occurs positively in C j then:

a i b i a' i b' i a'' i b'' i d'' d d' i i i Fig. 2: Subgraph Gi corresponding to variable xi. v v' u'' v'' u u' j j j j j j z j,1 z j,2 z j,5 z j,4 z j,3
(a.1) set a h = u j , b h = v j , if x h does not occur positively in some C j with j < j;

(a.2) set a h = u j , b h = v j , otherwise. (b) if x h occurs negatively in C j then set a h = u j , b h = v j .
(c) if x i occurs positively in C j then:

(c.1) set a i = u j , b i = v j , if x i does not occur positively in some C j with j < j;

(c.2) set a i = u j , b i = v j , otherwise. (d) if x i occurs negatively in C j then set a i = u j , b i = v j .
(e) if x k occurs positively in C j then:

(e.1) set a k = u j , b k = v j , if x k does not occur positively in some C j with j < j;

(e.2) set a k = u j , b k = v j , otherwise. (f) if x k occurs negatively in C j then set a k = u j , b k = v j .
Proceed similarly for clauses containing two variables x h , x i (using rules (a) to (d)) and clauses containing only one variable x h (using rules (a) and (b)).

See an example of construction of G in Figure 4. It is important to note that every induced C 5 of G is entirely contained either in a variable subgraph G i or in a clause subgraph H j .

The following observations are useful:

(x 1  x 2  x 4 )  (x 1  x 3  x 4 )  (x 2  x 3  x 4 )  (x 1  x 2 )  (x 3 )
e

Observation 1. Let T i be a C 5 -transversal of G i . Then |T i | ≥ 3. Moreover, if |T i | = 3 then T i cannot contain two vertices t 1 , t 2 such that t 1 ∈ {a i , b i , a i , b i } and t 2 ∈ {a i , b i }. (Note that selecting a i , a i , for example, still leaves two disjoint C 5 's uncovered. Suitable choices are T i = {x, x , d i }, with x ∈ {a i , b i } and x ∈ {a i , b i }; or T i = {x, d i , d i }, with x ∈ {a i , b i }.)
Observation 2. Let T be a C 5 -transversal of G and T j = T ∩ V (H j ). Then |T j \W j | ≥ 5, since the subgraph induced by T j \W j contains five disjoint C 5 's. Moreover, if T ∩ W j = ∅ for some j then one can easily see that five vertices are sufficient in T j \W j ; for instance, if T ∩ W j = {u j } then T j \W j may contain vertices z j,k for k = {1, 2, 3, 4, 5} (see Figure 3).

In what follows, we prove that F is satisfiable if and only if G admits a C 5 -transversal T of size 3n + 5m. Assume first that F is satisfiable. For each 1 ≤ i ≤ n, include in T vertices a i , a i , d i if x i is set to "true", otherwise include in T vertices a i , d i , d i . See Figure 2. Since each clause C j contains at least one true literal, T ∩ W j = ∅, for every j ∈ {1, . . . , m}. By Observation 2, five additional vertices for each H j suffice to complete the construction of T , yielding a C 5 -transversal of G of size 3n + 5m.

Conversely, assume that G admits a C 5 -transversal T of size 3n + 5m. Let T i = T ∩ V (G i ) and T j = T ∩ V (H j ). By Observations 1 and 2, |T i | ≥ 3 and |T j \W j | ≥ 5. As G contains m disjoint copies of H j and n disjoint copies of G i , it follows that W j = ∅, 1 ≤ j ≤ m, and

|T i | = 3, 1 ≤ i ≤ n. By Observation 1 again, T i cannot contain vertices t 1 , t 2 such that t 1 ∈ {a i , b i , a i , b i } and t 2 ∈ {a i , b i }. We can then assume T i = {a i , a i , d i } or T i = {a i , d i , d i }.
In the former case we set x i to "true", otherwise to "false". This shows that F is satisfiable.

2

We can transform the C 5 's of Figure into C k 's, for any k ≥ 6, by conveniently splitting some edges. See an example for k = 6 in Figure 5. This illustrates how one can easily prove the following theorem: Theorem 9 C k -TRANSVERSAL is NP-complete for graphs of maximum degree at most three, for any fixed k ≥ 5. Moreover, the graph G used in the hardness proof is bipartite when k is even. See Figure 6, where k = 6 and V (G) is divided into white and black vertices. Therefore: Theorem 10 C 2k -TRANSVERSAL is NP-complete for bipartite graphs of maximum degree at most three, for any k ≥ 3.

(x 1  x 2  x 4 )  (x 1  x 3  x 4 )  (x 2  x 3  x 4 )  (x 1  x 2 )  (x 3 )
(x 1  x 2  x 4 )  (x 1  x 3  x 4 )  (x 2  x 3  x 4 )  (x 1  x 2 )  (x 3 )
3 Graphs of maximum degree at most four

NP-completeness results

In this subsection we first prove the following NP-completeness result.

Theorem 11 TRIANGLE-TRANSVERSAL is NP-complete for graphs of maximum degree at most four.

Proof: The problem is clearly in NP. The hardness proof is similar to that of Theorem 8. Given an instance F of 3SAT 3 with n variables x 1 , x 2 , . . . , x n and m clauses C 1 , C 2 , . . . , C m , we construct G by creating a subgraph G i for each variable x i , as in Figure 7. Vertices a i and a i represent the two positive occurrences of x i , and vertex a i represents its negative occurrence. Let T i denote a minimum triangle-transversal of G i . Clearly, |T i | = 3. We will assume that

(x 1 ∨ ∨ ∨ ∨ x 2 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 1 ∨ ∨ ∨ ∨ x 3 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 2 ∨ ∨ ∨ ∨ x 3 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 1 ∨ ∨ ∨ ∨ x 2 ) ∧ ∧ ∧ ∧ (x 3 ) x 1 x 1 x 1 x 2 x 2 x 2 x 3 x 3 x 3 x 4 x 4 x 4
T i = {a i , a i , b i } or T i = {b i , b i , a i }. As T i is minimum, it cannot contain {a i , a i } or {a i , a i }.
Now, for each clause C j , 1 ≤ j ≤ m, we create a triangle Z j in G as follows:

-if x i occurs in C j and C j (j ≤ j ) then a i ∈ V (Z j ) and a i ∈ V (Z j );

-if x i occurs in C j then a i ∈ V (Z j ); -if |C j | = 2 then include a new vertex c j in V (Z j ); -if |C j | = 1 then include two new vertices c j , c j in V (Z j ).
See an example of construction of G in Figure 8. We prove that F is satisfiable if and only if G admits a triangle-transversal T of size 3n. If F is satisfiable, for each 1 ≤ i ≤ n include in T vertices a i , a i , b i if x i is set to "true", otherwise include in T vertices b i , b i , a i . Observe that |T | = 3n and every triangle in G is intersected by T .

Conversely, assume that G admits a triangle-transversal T of size 3n.

Let T i = T ∩ V (G i ).
Since each G i contains three disjoint triangles and G contains n disjoint copies of G i , we have |T i | = 3, for every 1 ≤ i ≤ n. Thus T i is a minimum triangle-transversal of G i , and as observed above it cannot contain {a i , a i } or {a i , a i }. We can then assume

T i = {a i , a i , b i } or T i = {b i , b i , a i }.
In the former case we set x i to "true", otherwise to "false". Hence, F is satisfiable.

2 Using the same idea as in the previous section, we can transform the triangles of Figure 8 into C 's, for any k ≥ 4. See an example for k = 4 in Figure 9. Hence we again claim the following result, without

(x 1 ∨ ∨ ∨ ∨ x 2 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 1 ∨ ∨ ∨ ∨ x 3 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 2 ∨ ∨ ∨ ∨ x 3 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 1 ∨ ∨ ∨ ∨ x 2 ) ∧ ∧ ∧ ∧ (x 3 ) x 1 x 1 x 1 x 2 x 2 x 2 x 3 x 3 x 3 x 4 x 4 x 4
(x 1 ∨ ∨ ∨ ∨ x 2 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 1 ∨ ∨ ∨ ∨ x 3 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 2 ∨ ∨ ∨ ∨ x 3 ∨ ∨ ∨ ∨ x 4 ) ∧ ∧ ∧ ∧ (x 1 ∨ ∨ ∨ ∨ x 2 ) ∧ ∧ ∧ ∧ (x 3 ) x 1 x 1 x 1 x 2 x 2 x 2 x 3 x 3 x 3 x 4 x 4 x 4
Fig. 11: Bipartite graph G for the case k = 4; V (G) is divided into white and black vertices.

giving the formal details:

Theorem 12 C k -TRANSVERSAL is NP-complete for graphs of maximum degree at most four, for any fixed k ≥ 3. Also, the subgraph G i corresponding to variable x i is bipartite when k is even. See an example in Figure 10. By slightly modifying the graph G of the reduction, we can make it bipartite: vertex c i (resp., c i , c i ) can be used instead of a i (resp., a i , a i ) to create the C k 's representing the clauses. See Figure 11. Therefore:

Theorem 13 C 2k -TRANSVERSAL is NP-complete for bipartite graphs of maximum degree at most four, for any k ≥ 2.

A decomposition theorem and an approximation algorithm for triangle-transversals in graphs of maximum degree at most four

Consider the following naive k-approximation algorithm for finding C k -transversals in general graphs, for a fixed k ≥ 3. Given a graph G, initially set T = ∅ and C := ∅. At each step: (i) locate an induced C k , say C (which can be found in polynomial time, since k is fixed); (ii) set

T := T ∪ V (C) and C := C ∪ {C}; (iii) remove the vertices in V (C) from G. Repeat (i)-(iii) until there are no more C k 's. Observe that the collection C is a C k -packing, that is, a collection of vertex-disjoint C k 's. Also, T is clearly a C k -transversal. If T * is a minimum C k -transversal, we have |T * | ≥ |C |. Since |T | = k|C |, it follows that |T |/|T * | ≤ k.
The above naive algorithm produces triangle-transversals with size at most three times the optimum. Nonetheless, a better behavior can be achieved by restricting the maximum degree of the input graph. In view of Theorem 11, we describe in this section a polynomial-time approximation algorithm for obtaining a triangle-transversal of a graph G with ∆ = 4.

We need the following definitions. A tie is a graph formed by five vertices a, b, c, d, z where d(z) = 4 and a, b, c, d induce 2K 2 . The vertex z is called a bond. A piece is a connected graph of maximum degree at most four containing no 3-free edges and no bonds. As we shall see, bonds and pieces play a crucial role in the algorithm. The following theorem characterizes pieces.

Theorem 14 Let H be a piece. Then H is one of following graphs: 12).

H n (n ≥ 3), H n (n ≥ 7), H n (n ≥ 8), G 4 , G 5i (1 ≤ i ≤ 5), G 6j (1 ≤ j ≤ 5), G 7 . (See Figure
In Figure 12, the graph H n (n ≥ 3) is formed by two paths u 1 u 2 . . . u n/2 and v 1 v 2 . . . v n/2 , plus the following edges:

u i v i and u i v i+1 , 1 ≤ i ≤ n/2 -1; u n/2 v n/2 ; and, if n is odd, u n/2 v n/2 .
The graph H n (n ≥ 7) is formed by a copy of H n plus the following edges: v 1 u n/2 ; v 1 v n/2 ; and The proof of Theorem 14 is a consequence of the following two lemmas. A piece H is said to be minimal if H -z is not a piece for any z ∈ V (H).

u 1 v n/2 (if n is even) or u 1 v n/2 (if n is odd). The graph H n is formed by a copy of H n plus the edge v 1 v n/2 and a vertex w adjacent to u 1 , v 1 , u n/2 , v n/2 . H' (n  7) n G G G G G G 4 51 52 53 54 55 H (n  3) n G G G G G G
Lemma 15 If H is a minimal piece then H = H 3 , H = H n (n ≥ 7) or H = H n (n ≥ 8). (See Figure 12).

Proof: Observe first that H contains no cut vertex (since there are no 3-free edges in H, such a vertex would necessarily be a bond, a contradiction). Therefore, for an arbitrary vertex z ∈ V (H), H -z is connected and contains no bonds.

Denote by t H (e) the number of distinct triangles of H containing edge e. Since H contains no 3-free edges, t H (e) > 0 for every e ∈ E(H).

Since H is a minimal piece, the observations above imply the existence of a 3-free edge

a 1 b 1 in H -z. Then t H (a 1 b 1 ) = 1 (a 1 b 1 z is the only triangle of H containing e).
If H = H 3 , the lemma follows. Suppose then that H = H 3 . In this case, we must have t

H (a 1 z), t H (b 1 z) > 1, otherwise either H = H 3 or at least one of a 1 , b 1 could be removed to obtain a smaller piece. Let a 1 a 2 z, b 1 b 2 z be new triangles containing a 1 z, b 1 z, respectively. Clearly, a 2 = b 2 , otherwise t H (a 1 b 1 ) > 1. By the same reason, a 1 b 2 , a 2 b 1 /
∈ E(H). Now consider vertex a 1 . We cannot have t H (a 1 a 2 ) = 1, otherwise H -a 1 or H -a 2 would be a piece, contradicting minimality. Let therefore a 3 be a new vertex such that a 1 a 2 a 3 is a triangle containing a 1 a 2 . Observe that a 3 satisfies a 3 z, a 3 b 1 / ∈ E(H). The same arguments above lead to the existence of a new vertex b 3 adjacent to b 1 , b 2 and not adjacent to a 1 , z.

Let us show now that a 2 b 2 / ∈ E(H). Suppose to the contrary. Denote by δ

H (v) the degree of vertex v in graph H. Then δ H (a 2 ) = δ H (b 2 ) = 4 and, consequently, a 2 b 3 , a 3 b 2 / ∈ E(H). If a 3 b 3 ∈ E(H)
, there would exist a new vertex c adjacent to both a 3 and b 3 (since a 3 b 3 cannot be a 3-free edge); but then both a 3 and b 3 would be bonds, a contradiction. Therefore

a 3 b 3 / ∈ E(H) and a 1 , a 2 , a 3 , b 1 , b 2 , b 3 , z induce G 7 .
However, if H = G 7 then H is not minimal; and if H properly contains G 7 then a 3 or b 3 would be a bond. In either case, a contradiction arises. We conclude that a 2 b 2 / ∈ E(H). To complete the proof of the claim, we analyze two cases: Case 1: a 2 b 3 ∈ E(H). In this case, δ H (a 2 ) = 4, and since a 2 b 3 cannot be a 3-free edge, we must have a 3 b 3 ∈ E(H). Observe now that a 3 b 2 ∈ E(H), otherwise b 3 would be a bond. Therefore

a 1 , a 2 , a 3 , b 1 , b 2 , b 3 , z induce H 7 .
Case 2: a 2 b 3 / ∈ E(H). In this case, we must have a 3 b 2 / ∈ E(H), otherwise there should exist a new vertex c adjacent to both a 3 and b 2 , implying δ H (b 2 ) > 4, a contradiction. We consider two subcases:

Case 2.1 a 3 b 3 ∈ E(H). Since a 3 b 3 cannot be a 3-free edge, let c be a new vertex adjacent to both a 3 and b 3 . Then c must also be adjacent to both b 2 and a 2 (otherwise a 3 , b 3 would be bonds). Thus

a 1 , a 2 , a 3 , b 1 , b 2 , b 3 , z, c induce H 8 . Case 2.2 a 3 b 3 / ∈ E(H). Since t H (a 1 a 3 ) = t H (b 1 b 3 ) = 1, we have t H (a 2 a 3 ), t H (b 2 b 3 ) > 1.
This leads to the same situation as in the beginning of the proof of the Lemma, replacing

a 1 , z, b 1 by a 3 , a 2 , a 1 or b 3 , b 2 , b 1 .
Since H is finite, at some point we will have two sequences of vertices a 1 , a 2 , a 3 , . . . , a j and b 1 , b 2 , b 3 , . . . , b k such that either

• Case 1 applies: a j-1 b k , a j b k , a j b k-1 ∈ E(H), i.e., vertices a 1 , . . . , a j , b 1 , . . . , b k , z induce H j+k+1 or • Case 2.1. applies: a j-1 b k , a j b k-1 / ∈ E(H), a j b k ∈ E(H) and there exists c adja- cent to vertices a j-1 , a j , b k-1 , b k , i.e., vertices a 1 , . . . , a j , b 1 , . . . , b k , z, c induce H j+k+2 . 2 Lemma 16 If H is a non-minimal piece then H is one of the graphs H n (n ≥ 4), G 4 , G 5i (1 ≤ i ≤ 5), G 6j (1 ≤ j ≤ 5), G 7 .
(See Figure 12).

Proof: Corollary 17 Let G be a graph of maximum degree at most four containing no bonds. Then a minimum triangle-transversal of G can be obtained in polynomial time.

If
Proof: After removing the 3-free edges of G, each of its connected components is a piece, for which a minimum triangle-transversal is easily obtained.

We analyze now graphs of maximum degree at most four that may contain bonds. We can restrict our analysis to connected graphs without 3-free edges. The following definition is useful.

Definition 18 Let H be a piece in Figure 12, and let v ∈ V (H). If δ H (v) = 2 then v is a connector, otherwise v is an inner vertex.

Next, we describe a decomposition for graphs of maximum degree at most four containing no 3-free edges:

Definition 19 Let G be a connected graph of maximum degree at most four without 3-free edges. The piece decomposition of G is the collection of pieces obtained by splitting each bond of G into two vertices, each having two adjacent neighbors, as shown in Figure 13. Each piece of the collection is also said to be a piece of G.

A piece decomposition of G can be obtained in polynomial time by locating its bonds. Observe that every bond is shared by two pieces of G. If v is a bond of G shared by two pieces H 1 and

H 2 of G then v is a connector both of H 1 and H 2 , since δ H1 (v) = δ H2 (v) = 2.
Pieces have an important property in relation to triangle-transversals:

Property 20 Let G be a graph of maximum degree at most four containing no 3-free edges. Then, for every minimum triangle-transversal T of G and for every piece H of G, the number of inner vertices of H belonging to T is a function only of the number of connectors of H belonging to T . The above property is derived directly from the symmetry of connectors in every piece. Consider, for example, that G contains a piece H isomorphic to G 61 (see Figure 12). If T contains exactly two connectors of H, no matter which of them, then T contains exactly one inner vertex of H. This leads us to the following definition.

Definition 21 Let H be a piece. The template of H is a sequence (t 0 , . . . , t k ) such that:

(1) k is the number of connectors of H;

(2) if H is a piece of a graph G of maximum degree at most four containing no 3-free edges, T is a minimum triangle-transversal of G, and is the number of connectors of H belonging to T , then t is the number of inner vertices of H belonging to T .

For instance, the templates of G 55 and G 61 are, respectively, (1, 1, 1, 0) and (2, 1, 1, 1). The template of H n , for n ≥ 4, depends on the value of n:

if n = 3j then it is ( n 3 , n-3 3 , n-3 3 ); if n = 3j + 1 then it is ( n-1 3 , n-1 3 , n- 4
3 ); and if n = 3j + 2 then it is ( n-2 3 , n-2 3 , n-2 3 ). The piece H 3 is special, since all of its vertices are connectors and the case = 0 cannot occur for it. To be consistent with Definition 21, the template of H 3 is (1, 0, 0, 0).

We remark that a piece with template of the form (α, α, . . . , α) or (α, α -1, . . . , α -1), for some α > 0, will always have α of its vertices belonging to a minimum triangle-transversal T , one of which will be a connector.

Templates will be helpful to describe reduction rules that eliminate almost all types of pieces of an input graph G of maximum degree at most four.

Reduction rules. Let G be a graph of maximum degree at most four. Let T be a minimum triangletransversal of G to be computed, initially empty. The following rules are used to transform G into a unique new reduced graph G r . The rules are applied just once, in the given order. inner vertices of H except the two neighbors v, w of some connector of H; next, link v, w to the other connector of H. This corresponds to replacing H by a copy of H 4 . Again, it is easy to see that there exists a triangle-transversal of the new graph with size q if and only if there exists a triangle-transversal of the previous graph with size q + j -1.

10. For n = 3j (j ≥ 2) the template of H n can be obtained by adding j -1 to each t in the template of H 3 (for ≤ 2). Thus, if H is a piece of G isomorphic to H 3j for some j ≥ 2, remove all the inner vertices of H and create a triangle using the connectors of H together with a new vertex x. This corresponds to replacing H by a copy of H 3 . Since x is a degree-two vertex, we can assume that x / ∈ T . Hence, there exists a triangle-transversal of the new graph with size q if and only if there exists a triangle-transversal of the previous graph with size q + j -1.

11. The only possible pieces of G are now H 3 , H 4 and G 55 . The pieces H 4 and G 55 are called crowns (respectively, 2-crown and 3-crown). Then, for every 2-crown or 3-crown containing a vertex with degree two in G, add one of its inner vertices to T and remove all of its vertices from G, except the ones playing the role of bonds in G. The application of the rules is completed.

We denote by G r the graph obtained from G by the application of rules 1 -11. Graph G r is called the reduced graph of G, which is uniquely defined from G. It will be useful to define an intersection graph P(G r ) as follows: the pieces of G r (triangles or crowns) are the vertices of P(G r ), and two vertices of P(G r ) are adjacent if and only if they share a bond of G r . The vertices representing triangles are called t-vertices, and the vertices representing crowns are called c-vertices. In addition, c-vertices representing 2-crowns (respectively, 3-crowns) are called c 2 -vertices (respectively, c 3 -vertices). Clearly, P(G r ) is a graph of maximum degree at most three. We remark that the graph of maximum degree at most four constructed in the reduction of Theorem 11 contains only triangles and crowns as pieces. Hence, TRIANGLE-TRANSVERSAL remains N P -complete for graphs of maximum degree at most four containing only such pieces. By excluding the crowns, we have the result below.

Theorem 22 TRIANGLE-TRANSVERSAL is polynomial time solvable for graphs G of maximum degree at most four for which G r contains no piece isomorphic to a crown.

Proof: If G r contains no piece isomorphic to a crown then P(G r ) contains only t-vertices. Take a maximum matching M of P(G r ). Let S be the subset of M -unsaturated vertices of P(G r ). An optimal triangle-transversal T of G r is formed as follows: for each edge e ∈ M , include in T the corresponding bond of G r , and for each vertex of S include in T any vertex of the corresponding piece of G r .

2

We now analyze the performance of the following approximation algorithm A : given a graph G of maximum degree at most four, compute G r , and for each crown C of G r whose inner vertices are u C and v C , include u C in T and remove u C , v C from G r ; then apply to the resulting graph the method described in Theorem 22. Let A (G) be the size of the triangle-transversal obtained by the application of algorithm A to G, and denote by OP T (G) the size of an optimal solution for G.

Theorem 23 Let G be a graph of maximum degree at most four. Extended reduction rules. Let G be a graph of maximum degree at most four. Set G = G r . It is clear that two adjacent t-vertices in P(G) represent two triangle-pieces sharing exactly one bond in G. In addition, if a t-vertex x is adjacent to a c-vertex y in P(G) then the corresponding pieces in G also share exactly one bond (otherwise we would have the configuration of G 65 ).

12. If two adjacent c-vertices y 1 , y 2 in P(G) correspond to two crowns C 1 , C 2 sharing more than one bond in G then include in T two inner vertices, one for each crown. (Recall that T denotes a minimum triangle-transversal being computed.) Remove from G all the inner vertices of C 1 , C 2 . At this point, there is a one-to-one correspondence between edges of P(G) and bonds of G. From now on, we do not distinguish a t-vertex x in P(G) and the corresponding triangle-piece in G. The same applies to c-vertices in P(G) and corresponding crowns in G. For two adjacent vertices in P(G), we also refer to the bond shared by them in G.

13. If a t-vertex x is a pendant vertex of P(G) then we can include in T the bond v of G corresponding to the edge incident to x in P(G). Let X be the subset of vertices of G belonging to the t-vertex x.

Remove X from G.

14. A c 3 -vertex y with degree strictly less than three in P(G) can be disregarded by including in T one of its inner vertices and removing from G all of its inner vertices. The same procedure can be applied to a c 2 -vertex with degree one in P(G).

15. Suppose that P(G) contains a chordless cycle C of t-vertices isomorphic to C k , such that exactly one of the t-vertices of C, say x, has degree three in P(G). Let v be the bond of x corresponding to the edge incident to x in P(G) which does not belong to E(C), and let Z be the subset of vertices of G belonging to the t-vertices forming C. To conclude this section, we present another case that can be solved in polynomial time. A graph H of maximum degree at most three is a pseudo-tree if every induced subgraph H of H satisfies at least one of the following properties: H contains a pendant vertex; H is a disjoint union of chordless cycles; H contains a chordless cycle where exactly one vertex of the cycle has degree three. Using iteratively the rules above, we have the following result, stated without proof.

  for the C k -TRANSVERSAL problem, with respect to the values of k and ∆.

Fig. 1 :

 1 Fig. 1: (a) Circular ladder; (b) Möbius ladder.

Fig. 3 :

 3 Fig. 3: Subgraph Hj corresponding to clause Cj.

8 Fig. 4 :

 84 Fig. 4: Proof of Theorem 8. Graph G constructed from an instance of 3SAT3. Two edges with the same label ej are identical.

8 Fig. 5 :

 85 Fig. 5: Transforming C5's into C6's.

8 Fig. 6 :

 86 Fig. 6: Bipartite graph G for the case k = 6; V (G) is divided into white and black vertices.

Fig. 7 :

 7 Fig. 7: Subgraph Gi corresponding to variable xi.

Fig. 8 :

 8 Fig. 8: Example of construction of G.

Fig. 9 :Fig. 10 :

 910 Fig. 9: Transforming triangles into C4's.

Fig. 12 :

 12 Fig. 12: All the possible pieces.

Fig. 13 :

 13 Fig. 13: Piece decomposition.

  (a) If G r contains no 2-crowns then A (G) ≤ 4 3 OP T (G). (b) If G r contains no 3-crowns then A (G) ≤ 3 2 OP T (G).

  (a) if k is even, include in T k suitable vertices of G belonging to alternating t-vertices of C, and remove Z\{v} from G. (b) if k is odd, include in T the vertex v plus k suitable vertices of G belonging to alternating t-vertices of C, and remove Z from G. Rule 15 can be generalized in the following way: 16. Let H be an induced subgraph of P(G) such that exactly one of the vertices of H, say x, has a neighbor outside H. Let Z be the subset of vertices of G belonging to t-vertices or c-vertices of H, and let G = G[Z]. Finally, let v be the bond of G corresponding to the edge incident to x in P(G) which does not belong to E(H). Then: (a) If OP T (G ) = k and OP T (G -v) = k then OP T (G) = OP T (G -(Z\{v}) ) + k; (b) if OP T (G ) = k and OP T (G -v) = k -1 then OP T (G) = OP T (G -Z) + k.

  are not 4-free edges. In addition, any edge xy ∈ E(G ) such that x, y / ∈ {u 1 , u 2 , v 1 , v 2 } is not a 4free edge as well. It remains to show that any edge of the formxy ∈ E(G ) with x ∈ {u 1 , u 2 , v 1 , v 2 } and y / ∈ {u 1 , u 2 , v 1 , v 2 }is not a 4-free edge. Suppose without loss of generality that x = u 1 . If y and v 1 have no common neighbor in G , the only C 4 containing edge yu 1

  H is a non-minimal piece with n vertices then there exists z ∈ V (H) such that H = H -z is a piece with n -1 vertices. Since H 3 is the only piece with three vertices, H 4 and G 4 are the only possible pieces with four vertices. In general, by taking a piece H with n -1 vertices, one can try to obtain pieces with n vertices by adding one vertex to H in all possible ways. For instance, from H 4 we obtain H 5 , G 51 , G 55 ; and from G 4 we obtain G 52 , G 53 , G 54 . Along this process, some maximal pieces (i.e., pieces not properly contained in pieces with one more vertex) are generated, such as G 53 , G 54 , G 55 . To conclude the proof, we observe that, for n ≥ 6, the only piece that can be generated from H n by adding one vertex to it is H n+1 .2A direct consequence of Theorem 14 is:

Acknowledgments

The authors are very grateful to the two anonymous referees for providing us with constructive comments and suggestions, which greatly improved the presentation of this work.

Partially supported by CNPq and FAPERJ. Partially supported by CNPq and FAPERJ. 1365-8050

Proof: We present only the proof of (a); the proof of (b) is similar.

We first observe that there exists an integer c G ≥ 0 such that OP T (G) = OP T (G r ) + c G and A (G) = A (G r ) + c G . Thus, it suffices to show that A (G r ) ≤ 4 3 OP T (G r ). Let T * be an optimal triangle-transversal for G r , and let T be a triangle-transversal obtained by apply-

Define subsets A, B ⊆ T * as follows:

Let G 1 (respectively, G 2 ) be a graph formed by k disjoint copies of the graph in Figure 14(a) (respectively, Figure 14 We remark that running algorithm A on G r and converting the triangle-transversal of G r into a triangletransversal of G yields an α(G)-approximation algorithm with α ∈ [ 4 3 , 3 2 ]. The value of α(G) depends on the ratio between the number of 3-crowns and the number of 2-crowns in G r . In general, we have:

Theorem 24 Let G be a graph of maximum degree at most four. Then there exists a 3 2 -approximation algorithm for computing a triangle-transversal of G that runs in polynomial time. 2

Extending the reduction rules

We can extend the reduction rules presented in the previous subsection in order to obtain some additional polynomial cases.

Theorem 25 TRIANGLE-TRANSVERSAL is polynomial time solvable for graphs G of maximum degree at most four for which P(G r ) is a pseudo-tree. 2

Conclusions

In this paper we have studied the problem C k -TRANSVERSAL for graphs of maximum degree at most ∆, for all values k and ∆. We have shown that the problem is polynomial-time solvable for k ≤ 4 and ∆ = 3, and NP-complete otherwise; in particular, we have characterized graphs of maximum degree at most three containing no 4-free edges in terms of circular/Möbius ladders. A polynomial-time approximation algorithm for finding C k -transversals, for k = 3, in graphs of maximum degree at most four was presented, based on a new decomposition theorem and reduction rules for such graphs. An interesting question is to devise approximation algorithms for other values of k.