Katrin Casel
email: katrin.casel@hpi.de

Henning Fernau
email: fernau@uni-trier.de

Khosravian Mehdi

Jérôme Ghadikolaei

Florian Monnot

Sikora

Khosravian Ghadikolaei
email: mehdi.khosravian-ghadikolaei@lamsade.dauphine.fr

Jérôme Monnot
email: jerome.monnot@lamsade.dauphine.fr

Florian Sikora
email: florian.sikora@lamsade.dauphine.fr

Extension of some edge graph problems: standard, parameterized and approximation complexity

Keywords: Extension problems, Edge Cover, Matching, Edge Domination, NP-completeness, Parameterized Complexity, Approximation 2020 MSC: 68Q17, 68Q25, 68Q27

We consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems and generalizations thereof. Given a graph G = (V, E) and an edge set U ⊆ E, it is asked whether there exists an inclusion-wise minimal (or maximal, respectively) feasible solution E which satisfies a given property, for instance, being an edge dominating set (or a matching, respectively) and containing the forced edge set U (or avoiding any edges from the forbidden edge set E \ U , respectively). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counter-balance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation and inapproximability results.

Introduction

We consider extension problems related to several classical edge optimization problems in graphs, namely Edge Cover, Maximum Matching and Edge Dominating Set. Informally, in an extension version of an edge optimization problem, one is given a graph G = (V, E) as well as a subset of edges U ⊆ E, and the goal is to extend U to a minimal (or maximal) solution (if possible). More precisely, for a minimization problem like Edge Dominating Set, given G = (V, E) and U ⊆ E, we ask if there is some inclusion-wise minimal edge dominating set D in G with U ⊆ D. In contrast, for a maximization problem like Maximum Matching, on input G = (V, E) and U ⊆ E, we ask if there is some inclusion-wise maximal matching M in G with M ⊆ U .

The notion of extension might sound somewhat counter-intuitive in the case of maximization problems, but can be understood better in a more general setting, considering optimization problems in NPO with an additionally specified set of partial solutions which we call pre-solutions (including the set of solutions) and a partial order on those. The partial order reflects not only the notion of extension but also of minimality as follows. For a pre-solution U and a solution S, S extends U if U S. A solution S is minimal if there exists no solution S = S with S S. The resulting extension problem is formally defined as the task to decide, for a given pre-solution U , if there exists a minimal solution S which extends U . In the cases considered in this paper, we always have the power-set 2 E of the set of edges E of a given graph defining the set of pre-solutions, and is either ⊆ in the case of minimization problems, and ⊇ in the case of maximization problems. Different orderings are considered in [START_REF] Casel | On the complexity of solution extension of optimization problems[END_REF], where also a general setting for extension problems is described.

In general, extension variants of combinatorial problems are interesting for efficient enumeration algorithms or for branching algorithms in general, as efficient algorithms for extension problems would allow to cut off search tree branches at an early stage of the branching. In branching algorithms, solutions are often built gradually; the partial or pre-solutions U can then be associated to the nodes of the search tree. A quick "no" to the extension question would avoid diving deeper into a branch where no solution can be found. Also, this could help develop enumeration algorithms with polynomial delay, relating to so-called flashlight algorithms [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF]. There are further intimate relations to greedy strategies and (in this way) also to approximation algorithms. More details of these applications are described in [START_REF] Casel | On the complexity of solution extension of optimization problems[END_REF][START_REF] Casel | On the complexity of solution extension of optimization problems[END_REF].

Clearly, the idea of extensions is not restricted to edge optimization problems. Extension versions have been studied for classical optimization problems, for example, the minimal extension of 3-Hitting Set [START_REF] Boros | Dual subimplicants of positive Boolean functions[END_REF], minimal Dominating Set [START_REF] Bazgan | The many facets of upper domination[END_REF][START_REF] Bonamy | Enumerating Minimal Dominating Sets in Triangle-Free Graphs[END_REF] or Vertex Cover [START_REF] Bazgan | On the Complexity Landscape of the Domination Chain[END_REF]. Extension of Hitting Set was also discussed recently in the context of database theory, see [START_REF] Bläsius | Efficiently enumerating hitting sets of hypergraphs arising in data profiling[END_REF].

Another area where extension problems show up is linked to Latin squares [START_REF] Colbourn | The complexity of completing partial Latin squares[END_REF] (and similar combinatorial questions), or also coloring extensions in graphs [START_REF] Biró | Precoloring extension. I. Interval graphs[END_REF]. In this context, also a connection to graph drawing is worth mentioning considering the problem to lay out a graph after having fixed the positions of certain vertices [START_REF] Chimani | Inserting multiple edges into a planar graph[END_REF]. The difference of this type of extension problems to the ones considered in this paper lies in the fact that with the mentioned settings, it is asked if there is any valid solution that contains the pre-set part of the solution: is there any way to fill in the cells of a square-of-numbers where certain cells are already pre-filled, so that the whole square is a Latin square, is there any valid coloring that obeys the given assignment of some colors to vertices, is there any way to find a planar drawing of a graph where certain vertices are already positioned, etc.

In contrast, we assume a certain partial order provided on the solution space, and we are interested in finding an extension that is minimal with respect to this ordering. In [START_REF] Casel | On the complexity of solution extension of optimization problems[END_REF][START_REF] Casel | On the complexity of solution extension of optimization problems[END_REF], we provide a systematic study of this type of problems, giving quite a number of different examples of extension problems, based on different partial orders. In [START_REF] Casel | Extension of vertex cover and independent set in some classes of graphs[END_REF], we investigated the complexity of extension versions of Vertex Cover and Independent Set, i.e., classical vertex graph problems, while this paper focuses on edge problems. For extension variants of automata-theoretic problems, see [START_REF] Fernau | Extensions to minimal synchronizing words[END_REF].

An extended abstract of this paper appeared in [START_REF] Casel | Extension of some edge graph problems: Standard and parameterized complexity[END_REF]. Since its appearance as a conference paper, some of the results that are proven in this paper have been also obtained independently in the literature. For instance, in [START_REF] Kobayashi | Polynomial-delay and polynomial-space enumeration of large maximal matchings[END_REF], it was shown that a problem called Maximal Matching Extension is NP-complete. Notice that our results are more general; more specifically, the mentioned problem is called Ext 1-DCPS in this paper. As explained in [START_REF] Kobayashi | Polynomial-delay and polynomial-space enumeration of large maximal matchings[END_REF], also the extension complexity results concerning cliques as established in [START_REF] Conte | On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms[END_REF] relate to the questions studied in this paper: Ext Clique is clearly equivalent to Ext IS (referring to the extension variant of Independent Set), so that Ext Matching can be viewed as a variation thereof in the context of edge problems.

Organization of the paper. Aside from general notation, Section 2 contains the formal definitions of the extension problems discussed in this paper. Specifically, we introduce extension problems related to generalized versions of matching, edge cover and edge domination. Also, that section summarizes the main results of the paper. In Section 3 we show that these problems remain NP-complete, even in bipartite graphs of bounded degree and with some constraints on the forced set of edges. Having a planar embedding does not help much either, as we show in Section 4 that these problems remain hard on subcubic bipartite planar graphs. Motivated by these negative results, we study the parameterized complexity of these problems in Section 5 and the approximability of a natural optimization version in Section 6.

Definitions

In the following, we collect all definitions that we need in this paper. The graphtheoretic notions that we are using are standard and may be consulted by the reader if doubts arise at any point, but the problem definitions are rather specific to our setting.

Graph definitions. We consider simple undirected finite graphs only, to which we refer to as graphs. A graph can be specified by the set V of vertices and the set E of edges; every edge has two endpoints and these two endpoints are called adjacent; if v is an endpoint of e, we also say that e and v are incident and two edges e and e are adjacent if they share a common endpoint. Let G = (V, E) be a graph and

S ⊆ V ; N G (S) = {v ∈ V : ∃u ∈ S, vu ∈ E} denotes the neighborhood of S in G and N G [S] = S ∪ N G (S)
denotes the closed neighborhood of S. For singleton sets S = {s}, we simply write

N G (s) or N G [s], even omitting G if clear from context. The cardinality of N G (s) is called degree of s, denoted d G (s).
Vertices of degree zero are called isolates. If three upper-bounds the degree of all vertices, we speak of subcubic graphs. For a subset S of edges, V (S) denotes the vertices incident to S. A vertex set S induces the graph G[S] with vertex set S and e ∈ E being an edge in G[S] if and only if both endpoints of e are in S. If S ⊆ E is an edge set, then S induces the graph G[V (S)], while G S = (V, S) denotes the partial subgraph induced by S; in particular, G S = (V, E \ S) with S = E \ S. If G is a graph, we also refer by V (G) to its set of vertices and by E(G) to its set of edges. A vertex set S of the graph G = (V, E) is independent if the induced graph G[S] constitutes of isolated vertices, or equivalently, if S is a set of pairwise non-adjacent vertices. An edge set S is called an edge cover if for each vertex v ∈ V , there is an edge e ∈ S that is incident to v, i.e., that has v as one of its endpoints, and it is a matching if S is a set of pairwise non-adjacent edges. An edge set S is minimal (or maximal, respectively) with respect to a graph property Π if S satisfies the graph property and any proper subset S ⊂ S of S (or any proper superset S ⊃ S of S, respectively) does not satisfy Π. A graph G = (L ∪ R, E) is called bipartite if its vertex set decomposes into two independent sets L and R. The line graph L(G) = (V , E ) of a graph G = (V, E) is a simple graph where each vertex of L(G) represents an edge of G and two vertices of L(G) are adjacent if and only if their corresponding edges share a common vertex in G. Hence, it is exactly the intersection graph of the edges of G. It is well known the class of line graphs is a subclass of claw-free graphs (i.e., not possessing the claw K 1,3 , a star with three rays, as an induced subgraph).

Problem definitions. Let G = (V, E) be a graph where the minimum degree is at least r ≥ 1. We assume r is a fixed constant (but all results given here hold even if r depends on the graph). An r-degree constrained partial subgraph is defined by an edge subset S ⊆ E such that none of the vertices in V is incident to more than r edges in S. The problem of finding such a set S of size at least k is termed r-Degree Constrained Partial Subgraph, abbreviated as r-DCPS. An r-degree edge-cover1 is defined as a subset S of edges such that each vertex of G is incident to at least r ≥ 1 distinct edges e ∈ S, leading to the decision problem r-Degree Edge-Cover, or r-EC for short, which asks for determining if such a set of size at most k exists in a given graph. For the particular cases of r = 1, 1-DCPS corresponds to the famous Matching problem and 1-EC is also known as the Edge Cover problem. Inclusion-wise minimal r-degree edge-covers are also called tight r-tolerant edge-covers in [START_REF] Harutyunyan | On the complexity of the upper r-tolerant edge cover problem[END_REF].

The optimization problem associated to r-DCPS, denoted Max r-DCPS, consists of finding an edge subset E of maximum cardinality that is a solution to r-DCPS. Max r-DCPS is known to be solvable in polynomial time even for the edge weighted version (here, we want to maximize the weight of E ) [START_REF] Gabow | An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems[END_REF]. When additionally the constraint r is not uniform and depends on each vertex (i.e., at most b(v) = r v edges incident to vertex v), Max r-DCPS is usually known as Simple b-Matching and remains solvable in polynomial time even for the edge-weighted version (Theorem 33.4, Chapter 33 of Volume A in [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]).

A well-studied optimization version of a generalization of r-EC, known as the Min lower-upper-cover problem (MinLUCP), is the following. Given a graph G = (V, E) and two functions a, b :

V → N such that for all v ∈ V , 0 ≤ a(v) ≤ b(v) ≤ d G (v), find a subset M ⊆ E such that the partial subgraph G M = (V, M ) induced by M satisfies a(v) ≤ d G M (v) ≤ b(v) (such
a solution will be called a lower-upper-cover), minimizing its cardinality |M | among all such solutions (if any). Hence, an r-EC solution corresponds to a lower-upper-cover with a(v) = r and b(v) = d G (v) for every v ∈ V . MinLUCP is known to be solvable in polynomial time even for edge-weighted graphs (Theorem 35.2 in Chapter 35 of Volume A in [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]).

We are considering the following extension problems associated to r-DCPS and r-EC.

Ext r-DCPS

Input: A graph G = (V, E) and U ⊆ E. Question: Does there exist an edge set S ⊆ E with S ⊆ U such that the partial subgraph G S has maximum degree at most r and is maximal in G?

Ext r-EC Input: A graph G = (V, E) and U ⊆ E. Question: Does there exist an edge set S ⊆ E with S ⊇ U such that the partial subgraph G S has minimum degree at least r and is minimal in G?

An r-edge dominating set S ⊆ E of a simple graph G = (V, E) is a set S of edges such that for any edge e ∈ E of G, at least r edges of S are incident to e (by definition, an edge dominates itself one time). The Minimum r-Edge Dominating Set problem (Min r-EDS for short) consists in finding an r-edge dominating set of minimum size. Notice that there is a feasible solution if and only if r ≤ min xy∈E (d G (x) + d G (y) -1). Obviously, 1-EDS is the classical Edge Dominating Set problem (EDS), which is NP-hard in general graphs (problem [GT2] in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]). The generalization to r-EDS has been studied in [START_REF] Berger | Approximability of the capacitated b-edge dominating set problem[END_REF][START_REF] Berger | Linear time algorithms for generalized edge dominating set problems[END_REF] (under the name b-EDS) from an approximation point of view. However, to the best of our knowledge, r-EDS for every r ≥ 2 was not proved NP-hard so far. As associated extension problem, we formally study the following problem.

Ext r-EDS Input: Given a simple graph G = (V, E) and U ⊆ E. Question: Is there a subset S ⊆ E such that U ⊆ S and S is a minimal r-edge dominating set?

For an edge extension problem π, ext π (G, U ) denotes the set of extremal extensions of U (i.e., minimal or maximal depending on the context). For a minimization version, U corresponds to a subset of forced edges (i.e., each minimal solution has to contain U ) while for a maximization version, E \ U corresponds to a subset of forbidden edges (i.e., each maximal solution has to contain no edges from E \ U ), while we could call U the set of permitted edges. Sometimes, the set ext π (G, U ) is empty, which makes the question of the existence of such extensions interesting. Hence, for π ∈ {Ext r-DCPS, Ext r-EC, Ext r-EDS}, the extension problems ask if ext π (G, U ) = ∅. We call |U | the standard parameter when considering these problems as parameterized. We may drop the subscript π if clear from context.

Summary of important results

After we have defined the combinatorial problems, we can now summarize our most important results on these problems in the sequence of their presentation. Notice that we can further restrict our instances by putting additional constraints to the pre-solutions, but we refrain from making this explicit in this summary. Also, from our results concerning "edge problems", we can mostly also derive results for "vertex problems" when restricted to line graphs. We make this more explicit throughout the paper, but not in this summary.

Ext r-DCPS (Theorem 1) NP-complete in bipartite graphs with maximum degree max{3, r+ 1} for any fixed r ≥ 1.

Ext r-EC (Theorem 4) NP-complete in bipartite graphs with maximum degree r + 2 for any fixed r ≥ 1.

Ext 1-DCPS and Ext 1-EC (Theorems 8 and 7) NP-complete for planar bipartite subcubic graphs.

Ext r-EDS (Theorem 5) NP-complete for planar bipartite graphs of maximum degree r + 2 for any fixed r ≥ 1.

These hardness results motivated us to study these extension problems with the toolboxes of parameterized complexity and approximation.

Ext r-DCPS (Theorem 14) FPT (parameterized by the number of forbidden edges collected in U ) for any fixed r ≥ 1.

Ext r-DCPS (Proposition 15) FPT with respect to the number of isolated edges in U for r ≥ 2 and on graphs with maximum degree r + 1; even polynomial-time decidable when r = 1.

Ext r-EC (Theorem 10) FPT (with standard parameter) for any fixed r ≥ 1.

Ext r-EDS (Theorem 16) W [1]-hard (with standard parameter) for any fixed r ≥ 1, even when restricted to bipartite graphs.

Notice that the parameterization by the size of the set U of forbidden edges can be seen as the dual of the standard parameter |U |. By cycling through all subsets of U , it is clear that Ext r-DCPS is also FPT with the standard parameter. A similar trivial argument shows that Ext r-EC and Ext r-EDS are FPT with the dual parameter |U |.

As indicated above, we could also prove some non-approximability results and occasionally also give some approximation algorithms, but these approximation problems will only formally introduced in Section 6, so that we refrain from explaining them here.

Complexity results

The results given in this section are based on a reduction from 2-balanced 3-SAT, or (3, B2)-SAT for short. An instance (C, X ) of (3, B2)-SAT is given by a set C of CNF clauses defined over a set X of Boolean variables such that each clause has exactly three literals and such that each variable appears exactly twice as a negative and twice as a positive literal in C. (3, B2)-SAT is NP-hard by [24, Theorem 1].

Theorem 1. For every fixed r ≥ 1, Ext r-DCPS is NP-complete in bipartite graphs with maximum degree max{3, r + 1}, even if U is an induced matching for r ≥ 2, or G[V (U )] is a collection of paths of length at most two for r = 1.

Proof. Let us first consider the case when r = 1. Consider an instance of (3, B2)-sat with clauses C = {c 1 , . . . , c m } and variables X = {x 1 , . . . , x n }. We build a bipartite graph G = (V, E) of maximum degree three as follows : 6

H(c) for c = x ∨ y ∨ z x c y c z c 1 c 2 c 3 c H(x)
1 x 1 c1 x 1 c2 x x c1 x c2 2 x 2 c3 x 2 c4
x ¬x c3 ¬x c4 • For each variable x, introduce 12 new vertices. They induce the subgraph H(x) = (V x , E x ) illustrated in Figure 1. The vertex set V x contains four special vertices x c1 , x c2 , ¬x c3 and ¬x c4 , where it is implicitly assumed that variable x appears as a positive literal in clauses c 1 , c 2 and as a negative literal in clauses c 3 , c 4 . Finally, there are two sets of free edges (non-forbidden edges):

F x = {e x } ∪ {2 c3 x ¬x c3 , 2 c4
x ¬x c4 } and F ¬x = {e ¬x } ∪ {1 c1

x x c1 , 1 c2 x x c2 }. Hence, the forbidden edges U x in H(x) are given by U x = E x \ (F x ∪ F ¬x ).

• We interconnect H(x) and H(c), where x is a literal of clause c, by adding edge

x c x c if x appears as a positive literal and edge x c ¬x c if x appears as a negative literal. We call these edges crossing edges.

We set

U = E \ ( c∈C U c ) ∪ ( x∈X U x )
. This construction is computable within polynomial time and G is a bipartite graph of maximum degree three. Gadget H(c) is designed such that any maximal matching excluding U has to find other edges to match each of the literal-vertices 1 c , 2 c , 3 c , and such that only two of them can be matched within H(c) with an edge in U . This in turn means, at least one literal-vertex needs to be matched by a crossing edge, indicating that the corresponding literal is satisfied by the variable assignment. Gadget H(x) ensures that either x c1 and x c2 or ¬x c3 and ¬x c4 have to be matched within H(x). Consequently, all crossing-edges connecting to H(x) are either to only positive (x c1 and x c2 ) or to only negated occurrences (¬x c3 and ¬x c4 ) of x; thus the set of all crossing-edges to the sets H(x) properly corresponds to a valid variable assignment.

We claim that there is a truth assignment of I which satisfies all clauses if and only if there is a maximal matching S ⊆ U of G.

If T is a truth assignment of I which satisfies all clauses, then we add the set of edges x c x c and F x if T (x) = true; otherwise, if T (x) = false, we add the edge x c ¬x c and all edges in F ¬x . For each clause c, we choose one literal l c which satisfies the clause; then, we add two edges saturating vertices 1 c , 2 c and 3 c and which are not incident to the edge of U c saturating l c . For instance, assume it is y; then, we add two edges saturating vertices 1 c and 3 c and the white vertices in the gadget clause H(c). The resulting matching S is maximal with S ∩ U = ∅.

Conversely, assume the existence of a maximal matching S with S ⊆ U . Hence, for each variable x ∈ X exactly one edge between e x and e ¬x is in S (in order to block edge 3 x 4 x ). If it is e x ∈ S (or e ¬x ∈ S, respectively), then F x ⊂ S (or F ¬x ⊂ S, respectively). Hence, S does not contain any crossing edges saturating ¬x c (or x c , respectively). Now for each clause c = x ∨ y ∨ z, at least one vertex among x c , y c , z c must be adjacent to a crossing edge of S. In conclusion, by setting T (x) = true if at least one vertex x c1 or x c2 of H(x) is saturated by S and T (x) = false otherwise, we get a valid assignment T satisfying all clauses.

Assume now r ≥ 2. The construction is an adaptation of the previous proof. A main building block of our construction is a subgraph, denoted B k (v) with k < r, containing (kr) + 1 vertices which are arranged as a tree of depth two with root v such that v has k children within this gadget, and each child w of v has r children. For each child w of v one edge connecting w to a leaf in B k (v) will be forbidden in our construction, and we will use

F B k (v) to denote a fixed set of k edges in B k (v) such that each child of v is adjacent to an edge in F B k (v) and v is not adjacent to an edge in F B k (v)
. The left part of Figure 2 gives an illustration of B k (v). The purpose of this construction is that the root v will connect to other parts of the graph, and the structure of B k (v) with the forbidden edges will make sure that a maximum r-degree constrained partial subgraph contains all edges between v and its children in B k (v), and can consequently only contain r -k edges connecting v to a vertex outside B k (v). Namely, if one edge e would be missing from the edges incident to v in B k (v) in any maximal edge set E , say, e = vv , then E would have to include the forbidden edge incident to v by maximality.

Consider now an instance I of (3, B2)-SAT with clauses C = {c 1 , . . . , c m } and variables X = {x 1 , . . . , x n }. We build a bipartite graph G = (V, E) of maximum degree r +1, together with a set U of permitted edges (among which a maximal partial subgraph of degree at most r should be chosen) as follows:

• For each clause c ∈ C, build a clause gadget H(c) = (V c , E c ) which is a B (r-2) (c) (the root c of B (r-2) (c) has r-2 children). Hence, we denote by U c = E c \F B (r-2) (c)
the set of permitted edges in H(c).

• For each variable x, introduce 3r new vertices which induce the primary subgraph denoted H (x) = (V x , E x ). The vertex set V x contains four special vertices x, x , ¬x, ¬x . The vertices x and ¬x have r -2 distinct vertices in their neighborhoods and x and ¬x are connected to r common vertices v 1 x , v 2 x , . . . , v r x . Also, we connect x, ¬x to x , ¬x , respectively, with two forbidden edges in H (x). The right part of Figure 2 gives an illustration of H (x). By adding a component B (r-1) (y) for each vertex y ∈ {v i

x : 1 ≤ i ≤ r} and identifying the root of B (r-1) (y) with y, we construct a new subgraph H(x) = (V x , E x ). We define the set of forbidden edges in

H(x) by F x = {xx , ¬x¬x } ∪ ( 1≤i≤r F B (r-1) (v i x )
) and hence U x = E x \ F x denotes the set of permitted edges in H(x).

• We interconnect H(x) and H(c) by adding edge xc if x appears positively in clause c and ¬xc if x appears negatively. These crossing edges are always permitted and 8 collected in the set U cross .

B k (v) v . . . . . . . . . . . . r k H (x) x ¬x x ¬x v 1 x v 2 x . . . v r x . . . r -2 . . .
Let U = ( c∈C U c ) ∪ ( x∈X (U x ) ∪ U cross be the global set of permitted edges. This construction is computable in polynomial time, yielding a graph G that is a bipartite graph of maximum degree r + 1.

We claim that there is a truth assignment T of I which satisfies all clauses if and only if there is a maximal r-degree constrained partial subgraph

G S = (V, S) of G, where S ⊆ U .
If T is a truth assignment of I which satisfies all clauses, a maximal r-degree constrained partial subgraph G S = (V, S) with S ⊆ U can be constructed as follows:

1. For each variable gadget H(c), by maximality U c ⊆ S.

2.

For each variable x, we add edges according to the assignment as follows: If T (x) = true, we add v i x x for all 1 ≤ i ≤ r and the two crossing edges connecting ¬x with their respective clause gadgets. If T (x) = false, we add v i

x ¬x for all 1 ≤ i ≤ r and the two crossing edges connecting x with their respective clause gadgets. In both cases, by maximality we add 2(r -2) pendent edges incident to x and ¬x and also all permitted edges in B (r-1) (y) for all y ∈ {v i

x : 1 ≤ i ≤ r}. 3. At last, for each variable c which has more than one true literal in assignment T , add some arbitrary crossing edges to c such that d G S (c) = r.

The resulting subgraph is a maximal r-degree constrained partial subgraph G S = (V, S) with S ⊆ U .

Conversely, assume the existence of a maximal r-degree partial subgraph G S = (V, S) with S ⊆ U . First, recall that for every gadget B k (v), we must have

E(B k (v))\F B k (v) ⊆ S for k ∈ {r -1, r -2}.
Moreover, for each variable gadget H(x), at least one of the pairs of crossing edges incident to x and ¬x have to be in S (by maximality). Hence, we set T (x) = true if both crossing edges incident to ¬x are in S and otherwise we set T (x) = false. This assignment is valid and since for each clause c, at most two crossing edges incident to vertex c are in S (G S is a subgraph with maximum degree r), then T satisfies all clauses of I.

In Theorem 1, we showed that, for every fixed r ≥ 2, Ext r-DCPS is hard even when the set of forbidden edges E \ U is an induced matching. In the following, we prove the same result does not hold when r = 1, by reducing this problem to the problem of finding a maximum matching in a weighted graph. We claim that with this construction, G = (V, E) with U ⊆ E is a yes-instance of Ext 1-DCPS if and only if G contains a maximum weighted matching of weight at least 2W |U |. To this end, first assume that G = (V, E) with U ⊆ E is a yes-instance. This means that there exists a maximal matching M in G that contains no edge from U . Observe that M is also a matching in G , and we will extend it to a matching

M in G of weight at least 2W |U |. Since M is maximal in G, it follows that {u, v} ∩ V (M ) = ∅ for each uv ∈ U . For each uv ∈ U such that |{u, v} ∩ V (M )| = 1, add to M the corresponding new edge, i.e., if u / ∈ V (M )
, add edge us uv , and otherwise add vs uv . After this, M contains for each u ∈ V (U ) one edge e u in G that contains u. The summed weight of these edges is at least

W |{e u = ux | x / ∈ V (U )}| + 2W |{uv | e u = uv = e v }| = W |V (U )| = 2W |U |.
Conversely, assume that there exists a matching M in G of weight at least 2W |U |. We claim that M = M ∩E is a maximum matching in G with M ⊆ U . Since G contains no edge from U it immediately follows that M ⊆ U . It remains to show maximality. Assume towards contradiction that there exists an edge e ∈ E \ M such that M ∪ {e} is still a matching.

If e ∈ U , then e is also an edge in G . Since M is maximal, it follows that there is at least one edge e ∈ M such that e ∩ e = ∅. Since e / ∈ M , e has to be an added edge involving s uv for some uv ∈ U . If e intersects only e in M , then M \ {e } ∪ {e} is also a matching in G , and its weight is larger than the weight of M -note that e is an added edge of weight W , while e is an original edge involving at least one vertex from V (U ), thus of weight at least W + 1. This means that M \ {e } ∪ {e} is a matching in G of strictly larger weight than M , a contradiction to the choice of M . Similarly, if e intersects more edges, then it intersects exactly one more edge e ∈ M , and again e contains some added vertex s xy = s uv . Let, w.l.o.g., e = us uv and e = xs xy . Since U is a matching, we know that u = x and thus, the only edge in G that intersects both e and e in G is e = ux. Since both u and x are in V (U ), e has weight 2W + 1 in G , while both e and e have weight W . Again, we see that M \ {e , e } ∪ {e} is a matching with weight more than M in G , contradicting the choice of M .

If e / ∈ U , then e does not exist in G . Let e = xy and note that in M only one of the endpoints xy can be matched with s xy while the other remains unmatched; otherwise, this edge would also be in M . (Note that here again it is important that U is a matching.) By the definition of W , for M to have weight at least 2W |U |, it has to contain at least r edges of weight 2W + 1 and t = 2|U | -2r edges of weight W for some r ∈ N. Edges of weight at least W and 2W + 1 contain one, respectively two, vertices from V (U ), so all vertices in V (U ) need to be matched in order to reach the claimed weight. So in particular, there cannot be an edge xy ∈ U such that only one of its endpoints is matched in M .

In [START_REF] Casel | Extension of vertex cover and independent set in some classes of graphs[END_REF], several results are proposed for the extension variant of the Independent Set problem (Ext IS for short) in different classes of graphs like bipartite graphs, planar graphs, chordal graphs, etc. Here, we deduce a new result for a subclass of claw-free graphs.

Corollary 3. Ext IS is NP-complete restricted to line graphs of subcubic bipartite graphs.

Proof. Let G = (V, E) be a subcubic bipartite graph and L(G) = (V , E ) be its line graph. It is well known that any matching S of G corresponds to an independent set S = L(S) of G and vice versa. In particular, S is a maximal matching of G if and only if L(S) is a maximal independent set. Hence, (G, U ) is a yes-instance of Ext 1-DCPS if and only if (L(G), L(U )) is a yes-instance of Ext IS. Theorem 1 with r = 1 concludes the proof.

A reduction from (3, B2)-SAT can also be used to show the following. Theorem 4. For every fixed r ≥ 1, Ext r-EC is NP-complete in bipartite graphs with maximum degree r + 2, even if the forced edge set U is a matching.

Proof. The proof is based on a reduction from (3, B2)-SAT. A main building block B 2r (v) (or B 2r+1 (v)) in our construction is based on a complete bipartite subgraph of 2r (or 2r + 1) vertices where one specified edge between two special vertices v and v has been deleted. So, B 2r (v) = K r,r -{vv } and B 2r+1 (v) = K r+1,r -{vv }. Except for these two vertices v, v , the other vertices of B 2r (v) are not linked to any other vertex in the whole construction, while for B 2r+1 (v), it is only the case of v (i.e., only v is also linked outside B 2r+1 (v)). Block B 2r (v) will appear five times in each variable gadget and block B 2r+1 (v) will correspond to each clause gadget (see Figure 3 for an illustration). By construction, all edges of B 2r (v) will belong to any r-EC solution (in fact, vertices v and v still need one more edge to satisfy the minimum degree constraint) and for B 2r+1 (c), it will be almost the case (except for few edges of B 2r+1 (c) incident to c, as all neighbors of c in B 2r+1 (c) have degree r + 1, and all edges between N (c) and N (N (c)) \ {c} have to be in the edge cover; c will need one more incident edge in the edge cover besides (some of) the edges from B 2r+1 (c)). Now, consider an instance I of (3, B2)-SAT with clauses C = {c 1 , . . . , c m } and variables X = {x 1 , . . . , x n }. We build a bipartite graph G = (V, E) of maximum degree r +2, together with a set U of permitted edges as follows:

• For each clause c ∈ C, we build a clause gadget B 2r+1 (c) which is a component K r,r-1 plus two vertices c, c . An illustration of B 2r+1 (c) is given in the left side of Figure 3.

• For each variable x ∈ X , we construct a subgraph H(x) = (V x , E x ) as follows: build two P 5 denoted P = (x, l, m, r, ¬x) and P = (x , l , m , r , ¬x ), respectively; then between each pair of vertices v, v of P and P a block B 2r (v) is added for each v on P ; this interconnects v on P with the corresponding vertex v on P , as v and v are special to B 2r (v). The variable gadget H(x) = (V x , E x ) is illustrated to the right of Figure 3.

c . . . . . . c Kr,r-1 B2r+1(c) x l m r ¬x • • • • • • x • • • • • • l • • • • • • m • • • • • • r • • • • • • ¬x H(x)
• We interconnect H(x) and B 2r+1 (c), where x is a literal of clause c by adding edge xc if x appears positively in c and the edge ¬xc if x appears negated. Such edges will be called crossing.

Now, it is easy to see that G is bipartite of maximum degree r + 2. Finally, let U = {x i l i , ¬x i r i : 1 ≤ i ≤ n}, picking the corresponding vertices and edges in each H(x i ). Gadget H(x) guarantees that for any minimal r-EC containing U , crossing edges can only be incident to either x or ¬x, but not both, meaning that these edges correspond to variable assignments. Block B 2r+1 (c) guarantees that for any minimal r-EC containing U , there is at least one crossing edge incident to vertex c. By construction, and the role of the crossing edges to H(x), any crossing edge incident to c has to correspond to a variable assignment that satisfies a literal of c.

We claim that there is a truth assignment T of I which satisfies all clauses if and only if G admits a minimal r-EC solution H = (V, S) of G, where U ⊆ S.

If T is a truth assignment of I which satisfies all clauses, a minimal r-EC solution H = (V, S) can be constructed as follows: Conversely, assume that H = (V, S) is a minimal r-EC solution of G containing U . By considering the variable gadget H(x) and in order to keep minimality, S contains either lm or rm but not both, since {xl, ¬xr} ⊂ S by hypothesis and since all edges in 12 the block B 2r (v) for v ∈ {l, m, r} have to be included into the edge cover by our previous observations. Hence, we set T (x i ) = true if rm ∈ S and T (x i ) = false if lm ∈ S. Since H has to get a minimum degree at least r for each vertex and vertex c has a degree r -1 in clause gadget B 2r+1 (c), then the partial subgraph H contains at least one crossing edge incident to each c and hence T is a valid assignment of I.

• For each variable x, if T (x) =

Complexity results for planar graphs

In this section, we turn our attention to planar graphs. Hence, we need a specific problem that can cope with this restriction. All reductions given in this section are hence from 4-Bounded Planar 3-Connected SAT (or 4P3C3SAT for short), the restriction of exact 3-satisfiability 2 to clauses in C over variables in X where each variable occurs in at most four clauses (at least one time but at most two times negated while it appears one time unnegated and at most three times unnegated) and the associated bipartite graph BP is planar of maximum degree four. (The bipartite graph associated to (C, X ) is the graph BP = (C ∪ X, E(BP )), where vertex set C = {c 1 , . . . , c m } represents the clauses in C, vertex set X = {x 1 , . . . , x n } represents the variables in X , and E(BP ) = {c j x i : variable i occurs in clause j}.) This restriction is also NP-complete [START_REF] Kratochvíl | A Special Planar Satisfiability Problem and a Consequence of Its NP-completeness[END_REF]; in the following, we always assume that the planar graph comes with an embedding in the plane. This gives us a planar variable-clause-graph G, corresponding to the original SAT instance I. The additional technical difficulties come with the embeddings that need to be preserved. Suppose that a variable x i appears in at most four clauses c 1 , c 2 , c 3 , c 4 of I such that in the induced (embedded) subgraph Proof. Consider first r = 1, corresponding to Ext EDS. Given an instance I = (C, X ) of 4P3C3SAT with clause set C = {c 1 , . . . , c m } and variable set X = {x 1 , . . . , x n }, we build a planar subcubic bipartite graph H = (V H , E H ) together with a set U ⊆ E H of forced edges as an instance of Ext EDS.

G i = G[{x i , c 1 , c 2 , c 3 , c 4 }], c 1 x i , c 2 x i , c 3 x i , c 4 x i is
For each variable x i , we introduce a corresponding gadget H(x i ) as depicted in Figure 4, the forced edge set U xi contains {m i r i , r i p i } for case (1), {p j i r j i , r j i m j i : 1 ≤ j ≤ 4} for case (2) and

{p 1 i p 2 i , p 2 i p 3 i , p 5 i p 6 i , p 6 i p 7 i , m 2 i f i } for case (3).
For each clause c j ∈ C, we construct a clause gadget H(c j ) as depicted on the right, and a forced edge set U cj , each clause gadget H(c j ) contains 8 vertices and 7 edges, with

|U cj | = 2.
Edges in U are drawn in bold.

H(c) for clause c = 1 ∨ 2 ∨ 3 1 c 2 c 1c 2c 3c 4c 5c 6c
2 addressing the problem to decide whether there is a truth assignment setting exactly one literal in each clause to true

l i m i r i p i t i f i H(c 1 ) H(c 2 ) H(c 3 ) H(c 4 )
case ( 1)

t 1 i p 1 i r 1 i m 1 i l 1 i f 1 i p 2 i r 2 i m 2 i l 2 i t 2 i p 3 i r 3 i m 3 i l 3 i f 2 i p 4 i r 4 i m 4 i l 4 i H(c 1 ) H(c 2 ) H(c 3 ) H(c 4 )
case ( 2) 2), (3) are corresponding to H(x i ), depending on how x i appears (as a negative or positive literal) in the four clauses (here, case 3 is rotated). Bold edges denote elements of Ux i . Crossing edges are marked by dashed lines.

t 1 i p 1 i p 2 i p 3 i p 4 i l 2 i l 1 i t 2 i p 5 i p 6 i p 7 i p 8 i r 2 i r 1 i m 1 i m 2 i f i H(c 2 ) H(c 3 ) H(c 1 ) H(c 4 ) case (3)
Moreover, we interconnect with some crossing edges the subgraphs H(x i ) and H(c j ) by linking x i (or ¬x i ) to c j according to how it appears in the clause. More precisely, each clause gadget H(c j ) is connected to the rest of the graph via two (or one, respectively) crossing edges incident to 2 cj (or to 1 cj , respectively). We also set the forced edge set U = ( xi∈X U xi ) ∪ ( cj ∈C U cj ). This construction is built in polynomial time, giving a planar subcubic bipartite graph.

Note that by minimality, for any edge of U , there exists at least one private edge to dominate it. So, let S be a minimal edge dominating set with S ⊇ U , then for each clause gadget H(c), at least one of the crossing edges incident to it is in S. Further, for each variable x, let c x t (or c x f , respectively) be the set of crossing edges incident to t i (or to f i , respectively), {t 1 i , t 2 i } (or to {f 1 i , f 2 i }, respectively), and {t 1 i , t 2 i } (or to f i , respectively) for the cases 1, 2 and 3 of H(x), respectively, then by minimality of S, at most one of (S ∩ c x t ) or (S ∩ c x f ) is non-empty. Therefore, it can be easily checked that I has a satisfying assignment T if and only if H has a minimal edge dominating set containing U .

For r ≥ 2, we start with the instance I = (H, U ) given in the construction above for r = 1. Recall that Let B = v∈L B r (v) be the added edges from H to H . Note that any r-EDS S of H must contain B. Moreover, S is a minimal r-EDS of H if and only if S \ B is a minimal edge dominating set of H. Remark 1. Reconsidering the previous construction that reduces the case when r > 1 to the case when r = 1, and using the NP-hardness of EDS in bipartite graphs [START_REF] Bertossi | Dominating sets for split and bipartite graphs[END_REF][START_REF] Yannakakis | Edge dominating sets in graphs[END_REF], we deduce NP-hardness of r-EDS for all r ≥ 1.

H = (V H , E H ) is a bipartite graph with bipartition V H = L ∪ R, while U ⊆ E H is a
x i c 1 c 2 c 3 c 4 case 1 t i l i m i r i f i c 1 c 2 c 3 c 4 case 2 t 1 i l 1 i m 1 i r 1 i f 1 i t 2 i l 2 i m 2 i r 2 i f 2 i p 1 i p 2 i c 1 c 2 c 3 c 4 case 3 t 1 i t 2 i l 1 i l 2 i m 1 i m 2 i r i f i c 1 c 2 c 3 c 4
In [START_REF] Kanté | On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets[END_REF], several results are proposed for the enumeration of minimal dominating sets in line graphs. Here, we strengthen these results by showing that extending a given vertex set to a minimal dominating set (a problem we call Ext DS) in line graphs of a planar bipartite subcubic graphs is already a hard problem. Corollary 6. Ext DS is NP-complete, even when restricted to line graphs of planar bipartite subcubic graphs.

Proof. Let G = (V, E) be a bipartite subcubic graph and L(G) = (V , E ) be its line graph. It is well known that any edge dominating set S of G corresponds to a dominating set S = L(S) of G and vice versa. In particular, S is a minimal edge dominating set of G if and only if L(S) is a minimal dominating set. Hence, (G, U ) is a yes-instance of Ext EDS if and only if (L(G), L(U )) is a yes-instance of Ext DS. Theorem 5 with r = 1 concludes the proof.

The two next statements appear to be only strengthening Theorems 1 and 4 in the particular case of r = 1, but the proof details behind are different indeed.

Theorem 7. Ext 1-EC is NP-complete for planar bipartite subcubic graphs.

Proof. The proof is based on a reduction from 4P3C3SAT. We illustrate how these cases are used in the reductions explicitly for Ext 1-EC. While the interconnections of the clause gadgets and the variable gadgets are similar to the non-planar case, the variable gadgets differ according to the cases listed above, see Figure 5.

We start from a variable-clause graph G = (C ∪ X, E) corresponding to an instance I = (C, X ) of 4P3C3SAT and transform it into a planar bipartite graph H = (V H , E H ) by replacing every node x i in G with one of the three variable gadgets H(x i ) which are illustrated in Figure 5. The forced edge set U i , corresponding to variable gadget H(x i ), contains

• t i l i , r i f i for case 1, • t 1 i l 1 i , r 1 i f 1 i , t 2 i l 2 i , r 2 i t 2
i for case 2 and

• t 1 i l 1 i , t 2 i l 2 i , r i f i for case 3.
Let U = 1≤i≤n U i be the set of forced edges of H. This construction can be undertaken in polynomial time and the final graph H is planar, bipartite and subcubic. We now claim that I is satisfiable if and only if H admits a minimal edge cover containing U . Suppose T is a truth assignment of I which satisfies all clauses. For each clause c j , let h(j) be an index such that variable x h(j) satisfies clause c j for T and let J = [n] \ h([m]) be the indices unused by the mapping h. We construct a minimal edge cover S of H by considering all possibilities of H(x i ):

• for each variable gadget H(x i ) which complies with "case (1)", we set:

S 1 :={t h(j) c j , m h(j) r h(j) : T (x h(j) ) = true, x h(j) appears positively in c j } ∪{f h(j) c j , m h(j) l h(j) : T (x h(j) ) = false, x h(j) appears negatively in c j } ∪{m i r i : i ∈ J}.
• for each variable gadget H(x i ) which complies with "case (2)" by assuming h(j) = k, we set S 2 to:

{t 1 k c j (t 2 k c j ), m 1 k r 1 k , r 1 k p 1 k , m 2 k r 2 k , r 2 k p 2 k : T (x k ) = true ∧ t 1 k c j ∈ E H (t 2 k c j ∈ E H )} ∪{f 1 k c j (f 2 k c j ), m 1 k l 1 k , l 2 k p 1 k , m 2 k l 2 k , l 1 k p 2 k : T (x k ) = false ∧ f 1 k c j ∈ E H (f 2 k c j ∈ E H )} ∪{l 1 i p 2 i , l 1 i m 1 i , l 2 i m 2 i , l 2 i p 1 i : i ∈ J}.
• for each variable gadget H(x i ) which complies with "case (3)" by assuming h(j) = k, we set:

S 3 :={t 1 k c j (t 2 k c j ), m 1 k r k , m 2 k r k : T (x k ) = true ∧ t 1 k c j ∈ E H (t 2 k c j ∈ E H )} ∪{f k c j , m 1 k l 1 k , m 2 k l 2 k : T (x k ) = false} ∪{l 1 i m 1 i , l 2 i m 2 i : i ∈ J}.
Finally we set S := S 1 ∪ S 2 ∪ S 3 ∪ U . One can easily check that S is a minimal edge cover of H.

Conversely, suppose S is a minimal edge cover of H containing U . By minimality of S, we propose an assignment T of I depending on different types of variable gadgets of H as follows:

• If H(x i ) complies with case (1), in order to cover vertex m i , the edge cover S either contains m i r i or m i l i (not both by minimality). This means that we set T (x i ) = true (or T (x i ) = false, respectively) if m i r i ∈ S (or m i l i ∈ S, respectively).

• If H(x i ) complies with case (2), in order to cover vertices m 1 i , m 2 i , p 1 i , p 2 i , the edge cover S contains exactly one of edges in the pairs (l

1 i m 1 i , r 1 i m 1 i ), (l 2 i m 2 i , r 2 i m 2 i ), (l 1 i p 2 i , r 2 i p 2 i ) and (r 1 i p 1 i , l 2 i p 1 i ). Hence, we set -T (x i ) = true if {l 1 i m 1 i , l 1 i p 2 i , l 2 i p 1 i , l 2 i m 2 i } ∩ S = ∅, and -T (x i ) = false if |{l 1 i m 1 i , l 1 i p 2 i , l 2 i p 1 i , l 2 i m 2 i } ∩ S| ≥ 1.
• If H(x i ) complies with case (3), in order to cover vertices m 1 i , m 2 i , S contains exactly one of edges in the pairs (r i m

1 i , l 1 i m 1 i ), (r i m 2 i , l 2 i m 2 i )
. This means that we set

-T (x i ) = true if S ∩ {l 1 i m 1 i , l 2 i m 2 i } = ∅ and -T (x i ) = false if |S ∩ {l 1 i m 1 i , l 2 i m 2 i }| ≥ 1.
We obtain a valid assignment T . Since S covers all vertices of C, T satisfies all clauses of I.

Theorem 8. Ext 1-DCPS is NP-complete even for planar bipartite subcubic graphs.

Proof. The proof is based on a reduction from 4P3C3SAT. For an instance I = (C, X ) of 4P3C3SAT with clause set C = {c 1 , . . . , c m } and variable set X = {x 1 , . . . , x n }, we build a planar bipartite subcubic graph H = (V H , E H ), together with a set U ⊆ E H of permitted edges as an instance of Ext 1-DCPS as follows.

• For each clause c j , we introduce a clause gadget H(c j ) together with a permitted edge set U cj which is already explained in detail in Theorem 1 for r = 1.

• For each variable x i depending on how x i appears (negated or non-negated) in clauses, we introduce three different gadgets H(x i ) together with a set of permitted edges U xi , which is depicted in Figure 6.

• We also interconnect H(x i ) to H(c j ), where x i appears positively or negatively in clause c j by crossing edges like in the proof of Theorem 1. Let U cross be the set of all crossing edges.

Let U = ( m j=1 U cj ) ∪ ( n i=1 U xi ) ∪ U cross .
This construction computes in polynomial time a planar bipartite subcubic graph. We claim that (H, U ) is a yes-instance of Ext 1-DCPS if and only if T is a satisfying assignment of I.

Suppose T is a truth assignment of I which satisfies all clauses. We produce a maximal edge matching S ⊆ U as follows: the method of choosing edges from clause gadgets and crossing edges is already explained in Theorem 1 for r = 1, so we here just show which edges of each H(x i ) should be in S:

• If H(x i ) complies with case (1), we add {m i l 1 i , h 1 i f 1 i , h 2 i f 2 i } if T (x i ) = true and we add {m i l 2 i , g 1 i t 1 i , g 2 i t 2 i } if T (x i ) = false. • If H(x i ) complies with case (2), we add {f 1 i h 1 i , p 1 i p 3 i , m 2 i r 2 i , f 2 i h 2 i , p 5 i p 7 i , l 1 i m 1 i } if T (x i ) = true; if T (x i ) = false, we add {p 2 i p 3 i , t 1 i g 1 i , l 2 i m 2 i , p 6 i p 7 i , t 2 i g 2 i , m 1 i r 1 i }. • If H(x i ) complies with case (3), we add {l 1 i m 1 i , l 2 i m 2 i , l 3 i m 3 i , f i h i } if T (x i ) = true; otherwise, if T (x i ) = false, we add 1≤j≤3 {r j i m j i , t j i g j i }. g 1 i t 1 i g 2 i t 2 i h 1 i f 1 i h 2 i f 2 i l 1 i l 2 i m i r i H(c 1 )
H(c 2 )

H(c 3 ) H(c 4 ) case 1 p 1 i p 2 i p 3 i p 4 i p 5 i p 6 i p 7 i p 8 i g 1 i t 1 i h 1 i f 1 i g 2 i t 2 i h 2 i f 2 i l 1 i m 1 i r 1 i l 2 i m 2 i r 2 i H(c 1 )
H(c 2 )

H(c 3 ) H(c 4 ) case 2
g 1 i t 1 i l 1 i m 1 i r 1 i l 2 i m 2 i r 2 i l 3 i m 3 i r 3 i p i g 2 i t 2 i g 3 i t 3 i h i f i H(c 1 ) H(c 2 ) H(c 3 ) H(c 4 ) case 3
Figure 6: Variable gadgets H(x i ) of Theorem 8. Cases (1), ( 2), (3) are corresponding to H(x i ), depending on how x i appears (negated or non-negated) in the four clauses. Edges not in Ux i are drawn bold. Crossing edges are marked with dashed lines.

Conversely, suppose S ⊆ U is a maximal edge matching of H. Because of maximality, for each clause gadget H(x j ) there exists at least one crossing edge in S incident to a vertex of H(x j ). This means that there is an assignment T which satisfies all clauses of I. We now show that T is a valid assignment:

• If H(x i ) complies with case (1), by maximality either l 1 i m i or l 2 i m i (not both) is in S, hence we set T (x i ) = true if l 1 i m 1 i ∈ S and T (x i ) = false if l 2 i m i ∈ S.
• If H(x i ) complies with case (2), by maximality either

S 1 = {p 1 i p 3 i , m 2 i r 2 i , p 5 i p 7 i , l 1 i m 1 i } or S 2 = {p 2 i p 3 i , l 2 i m 2 i , p 6 i p 7 i , m 1 i r 1 i } (not both) is in S, so we set T (x i ) = true if S 1 ∈ S and T (x i ) = false if S 2 ∈ S.
• If H(x i ) complies with case (3), by maximality either

S 1 = 1≤j≤3 {l j i m j i } or S 2 = 1≤j≤3 {r j i m j i } (not both) is in S, hence we set T (x i ) = yes if S 1 ∈ S and T (x i ) = false if S 2 ∈ S.

Parameterized perspective

The next result is quite simple and characterizes the yes-instances of Ext r-EC.

Lemma 9. There is an r-EC solution G = (V, E ) where E ⊇ U such that S G = {v ∈ V (U ) : d G (v) > r} is an independent set of G U if and only if ext(G, U ) = ∅.
Proof. (⇐) An edge among two vertices x, y ∈ U of a minimal extension X ⊇ U certifying that ext(G, U ) = ∅ can only exist if x or y is, or both x and y are, incident to at most r edges from X because of minimality.

(⇒) Let us look into the other direction.

Let G = (V, E ) be a partial subgraph of G with U ⊆ E and d G (v) ≥ r for all v ∈ V . Moreover, assume S G = {v ∈ V (U ) : d G (v) > r} is an independent set of G U . Consider any minimal partial subgraph H = (V, E H ) of G = (V, E ) maintaining the property d G (v) ≥ r for all v ∈ V . Since S G is an independent set of G U , U ⊆ E H and therefore, E H ∈ ext(G, U ).
This structural property can be used to design an FPT-algorithm for Ext r-EC. More precisely, our proposed algorithm lists all 3 |U | many independent sets of G[U ] included in V (U ) from an instance I = (G, U ) of Ext r-EC. In each case, we produce an equivalent instance of Min lower-upper-cover problem (MinLUCP), the optimization version of a generalization of r-EC, that can be solved in polynomial time which gives the following result.

Theorem 10. For every fixed r ≥ 1, Ext r-EC, with standard parameter, is in FPT; more precisely, the running time can be upper-bounded by O * (3 |U | ).

Proof. Let us establish a relation between the instances of the two problems Ext r-EC and MinLUCP. Let (G, U ) be a yes-instance of Ext r-EC, where G = (V, E) is a graph of minimum degree at least r and U ⊆ E. So, ext(G, U ) = ∅ which implies by Lemma 9 the existence of a particular independent set S of G U . We build an instance (G U , a, b), U = E \ U , of MinLUCP, where a, b are two non-negative functions defined as follows:

a(v) := r if v ∈ V \ V (U ) r -d G U (v) if v ∈ V (U ), and b(v) := d G (v) if v ∈ (V \ V (U )) ∪ S r -d G U (v) if v ∈ V (U ) \ S.
The next property is rather immediate. Since MinLUCP is solvable in polynomial time [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF], then the running time is dominated by the procedure that lists all possible independent sets of G[U ], i.e., there are 3 |U | possibilities: each vertex of each edge in U can be either included or excluded of the independent set, except for taking both endpoints in.

For Ext r-DCPS, we can also exploit some structural properties of yes-instances and then use the polynomial solvability of Simple b-Matching to show that Ext r-DCPS, with dual parameter, is in FPT. It is sometimes more convenient to think about this problem as follows: Given a graph G = (V, E) and an edge set U , the question is if there exists an inclusion-wise maximal edge subset S ⊆ E of G such that the partial subgraph G S has maximum degree r and avoids U , i.e., S ∩ U = ∅. Our parameter is |U |. Assume there is an inclusion-wise maximal partial subgraph G E = (V, E ) of G with maximum degree r such that E ∩ U = ∅. The next property is quite immediate.

19 E) and forbidden set U ⊂ E (edges are marked with bold line). A vertex cover V of G U (vertices with a bold border) is shown on the left side. On the right side, the weighted graph G = (V, U ) built from G and V is displayed. Lemma 12. The set {v ∈ V : v is incident to U and to r edges in E } is a vertex cover of G U = (V, U ).

V = {L, E, K} L B C D E F K H weighted graph (G , w ) L B C D E F K H 1 2 1 1 0 0 0 1 2 1 1 Figure 7: Graph G = (V,
Proof. By contradiction, suppose there is an edge xy ∈ U such that x and y are both incident to less than r edges in E . Then E ∪ {e} is a new solution of r-DCPS; this is a contradiction to the maximality of E .

We now introduce some notations useful in the following. For a minimal vertex cover V of G U , let (G , w ) be the edge-weighted graph of (V, U ) defined as follows: for v ∈ V , d (v) = 0 if v / ∈ V , and d (v) = 1 if v ∈ V . We define the edge weight w by: w (e) = d (x) + d (y) for e = xy ∈ U . Figure 7 illustrates the construction of (G , w ) from an original graph G and a specified vertex cover V of G U .

Theorem 13. Let r ≥ 1. There is a maximal r-DCPS set S for G such that S ∩ U = ∅ if and only if there is a vertex cover V of G U such that there exists an r-DCPS set S for the corresponding weighted graph G such that w (S ) ≥ |V | × r.

Proof. Let G = (V, E) be a graph and let U ⊆ E. Let G S = (V, S) be any maximal partial subgraph with maximum degree r of G such that S ∩U = ∅ (if any). First observe that since S is an r-DCPS set for G which avoids U , it is also an r-DCPS set for G . From Lemma 12, we know V = {v ∈ V : v is incident once to U and r times to S} is a vertex cover of G U , and let V ⊆ V be a minimal vertex cover of G U . Hence, for the graph G with edge-weight w associated to the minimal vertex cover V of G U , it follows that w (S)

≥ v∈V d G S (v) = |V | × r.
Conversely, assume that V is a minimal vertex cover of G U such that there exists an r-DCPS set S for G such that w (S ) ≥ |V | × r. By the definition of the edgeweights w , it follows that w (S ) = v∈V d G S (v). As the subgraph G S has maximum degree r, the weight w (S ) ≥ |V | × r is only possible if d G S (v) = r for all v ∈ V . Greedily extending S to an r-DCPS set for the original graph G hence gives a solution for Ext r-DCPS on (G, U ); observe that the edges in U can not be chosen by the greedy procedure, as each edge in U is already incident to at least one vertex in V which already has degree r. 20

Using the characterization given in Theorem 13, the next result is rather straightforward. Proof. Given an instance (G, U ) of Ext r-DCPS, consider an algorithm that lists all minimal vertex covers V of G U and checks if the optimal value of Max r-DCPS on (G , w ) is at least |V | × r. According to Theorem 13, this procedure suffices to decide if there exists an r-DCPS set S with S ∩ U = ∅, i.e., if (G, U ) is a yes-instance for Ext r-DCPS.

The running time is dominated by the procedure that lists all minimal vertex covers, as solving Max r-DCPS can be done in polynomial time by [START_REF] Gabow | An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems[END_REF]. As the number of edges in a graph is an upper bound on any minimal vertex cover of that graph, it is clear that we can enumerate all minimal vertex covers of G U in time O * (2 |U | ) by [START_REF] Damaschke | Parameterized enumeration, transversals, and imperfect phylogeny reconstruction[END_REF][START_REF] Fernau | On parameterized enumeration[END_REF][START_REF] Fernau | Edge dominating set: Efficient enumeration-based exact algorithms[END_REF].

Using our approach, the running time estimate cannot be improved; consider for instance the case when E(G U ) is a perfect matching. However, if G U is connected, then we know that the number of vertices |V (G U )| is upper-bounded by |E(G U )| -1. Hence, the classical results of Moon and Moser [START_REF] Moon | On cliques in graphs[END_REF] on enumerating maximal independent sets show the last claim on the running time.

When bounding the degree of the graphs, we can consider an even smaller parameter and obtain feasibility results.

Proposition 15. For graphs with maximum degree r + 1, Ext r-DCPS is polynomialtime decidable when r = 1 and is in FPT with respect to the number ι of isolated edges in U for r ≥ 2. More precisely, we can upper-bound the running time by O * (2 ι ).

Proof. Consider the partial subgraph G = G U = (V, E \ U ), i.e., the graph induced by the forbidden edges. Since the maximum degree of G is r + 1, if G contains a triangle or a path of length at least 3, then then answer is no. Therefore, we can suppose that G is a collection of stars. If one leaf of a star of G has a degree at most r in G, then this star must be an isolated edge in G and it is exactly for one of these two endpoints (otherwise, the answer is no). Hence, let P G be the set of the stars which are isolated edges in G and such that both endpoints are of degree r + 1 in G.

• For r ≥ 2, for the set of stars of G with more than one edge, leaves and center are clearly determined and for each single edge of G not in P G , the endpoint with degree less than r is chosen as a center. Now, for each star in P G we have to determine one of the endpoints as a center and the other one as a leaf. This determines the claimed running time. We can now build the set L of leaves for all stars of G . Let E L = {uv ∈ E : u ∈ L} and G L = (V, E L ). We check for all possible labelings, if there is a label which satisfies two following conditions the answer is yes, else the answer is no.

1. for each v ∈ L, d G L = (v) = r + 1. 2. for each vertex v ∈ V \ L, d G L (v) ≤ r.
• For r = 1, we construct a new graph H by omitting all sets of vertices {u i , u i , v i , w i , w i } for the stars [u i , v i , w i ] of G (with center v i ) where u i , w i are neighbors of the leaves u i , w i (without v i ). Notice at each time u i , v i have to be disjoint from one star to another one, otherwise the answer is no. Now, H is a collection of paths (maybe trivial) and cycles where the forbidden edges induce a matching. Remove from H all cycles and the paths where both end edges are in U . Now, H is a collection of paths where at least one of end edges is forbidden. For all of these paths, start from one side and satisfy the maximality by assigning the first possible edge to a forbidden edge; if there is a path that does not satisfy the maximality, the answer is no, else the answer is yes.

Remark 2. For graphs with maximum degree r + 1, Ext r-DCPS with r ≥ 2 is parameterized equivalent to SAT with respect to the number of isolated edges in E \ U and variables, respectively. Proof. We only consider r = 1. For r ≥ 2, we can use the gadget B r (v) as in Theorem 5.

v 1 v 2 v 3 v 4 v 5 v 6 v 5 v 1 v 2 v 6 v 3 v 4 x 1 y 1 z 1 x 2 y 2 z 2
The hardness result comes from a reduction from Ext VC on bipartite graphs, the extension version of Vertex Cover; see [START_REF] Casel | Extension of vertex cover and independent set in some classes of graphs[END_REF]. Let I = (G, U ) be an instance of Ext VC, where G = (V, E) is a bipartite graph with partition (V 1 , V 2 ) of V and U ⊆ V , the question of Vertex Cover is to decide if G has a minimal vertex cover S with U ⊆ S.

We build an instance

I = (G , U ) of Ext EDS as follows. Let us first construct a new graph G = (V , E ) with V = V ∪ {x i , y i , z i : i = 1, 2} and
E = E ∪ i=1,2 {x i y i , y i z i } ∪ {vx i : v ∈ V i } . G is bipartite with partition into V 1 = V 1 ∪ {x 2 , y 1 , z 2 } and V 2 = V 2 ∪ {x 1 , y 2 , z 1 }. Set U = {ux 1 : u ∈ U ∩ V 1 } ∪ {ux 2 : u ∈ U ∩ V 2 } ∪ {x 1 y 1 , x 2 y 2 } so, |U | = |U | + 2.
: v ∈ V 1 ∩S}∪{vx 2 : v ∈ V 2 ∩S}∪{x 1 y 1 , x 2 y 2 } is an
edge dominating set of G which includes U because S contains U . Since S is minimal, S is minimal, too; observe that private edges of a vertex v ∈ S ∩ V 1 (i.e. an edge vu with u / ∈ S ∩ V 1 ) translate to private edges of vx 1 ∈ S , analogously for x ∈ S ∩ V 2 . By construction, y i z i is a private edge for x i y i , i = 1, 2.

Conversely, suppose S is a minimal edge dominating set of G containing U . Since S is minimal, then for each e ∈ S there is a private edge set S e ⊆ E , S e = ∅, which is dominated only by e. Moreover, we have, for i ∈ {1, 2}:

∀v ∈ V i ((vx i ∈ S ) ⇐⇒ (∀u ∈ V 3-i (vu / ∈ S ∩ E)) ,
since S is minimal and {x 1 y 1 , x 2 y 2 } ⊆ U . We now show how to safely modify S such that S ∩ E = ∅. If it is not already the case, there is some edge, w.l.o.g., e = uv ∈ S ∩ E with u ∈ V 1 and v ∈ V 2 . In particular from the above observations, we deduce u / ∈ U , v / ∈ U and S e ⊆ E. Modify S by the following procedure.

• If the private solution set S e \{e} contains some edges incident to u and some edges incident to v, then e ∈ S will be replaced by ux 1 and vx 2 ;

• if every edge in the private solution S e is adjacent to u, replace e in S by ux 1 , otherwise if every edge in the private solution S e is adjacent to v, replace e in S by vx 2 .

The case distinction is necessary to guarantee that S stays a minimal edge dominating set after each modification step. We repeat this procedure until S ∩ E = ∅. At the end of the process, every vertex v ∈ V covers the same set of edges as vx 1 or vx 2 dominates. Hence, by setting S = {v ∈ V : vx 1 ∈ S or vx 2 ∈ S }, we build a minimal vertex cover of G containing U . Remark 3. Note that the procedure of local modifications given in Theorem 16 does not preserve optimality, but only inclusion-wise minimality.

Price of extension

Considering the possibility that some set U might not be extensible to any minimal solution, one might ask how far U is from an extensible set. This concept, introduced in [START_REF] Casel | On the complexity of solution extension of optimization problems[END_REF], is called Price of Extension (PoE). A similar approach has already been studied in the past called the Price of Connectivity in [START_REF] Cardinal | Connected vertex covers in dense graphs[END_REF] in the context of connectivity. This notion has been introduced in [START_REF] Cardinal | Connected vertex covers in dense graphs[END_REF] for Min VC which is defined as the maximum ratio between the connected vertex cover number and the vertex cover number. Here, the goal of studying PoE is to measure how far efficiently computable extensible subsets of the given presolution U are to U or to the largest possible extensible subsets of U . To formalize this, we define optimization problems corresponding to Ext r-EC and Ext r-EDS. Actually, since we mainly propose negative results, we only focus on r = 1 by introducing and considering the following problems: Let us make some simple observations about every minimal edge cover of H. {v i v i : v i ∈ V } is a part of every edge cover since, v i for v i ∈ V are leaves of H. Moreover, for each e = v i v j ∈ E with i < j, at least one edge between v i v ij or v j v i,j belongs to any edge cover of H. Furthermore, if v i v i,j ∈ S, by minimality we deduce that v i v i / ∈ S . Hence, for each v i v j ∈ E, at most one of v i v i , v j v j can be in S . Hence, S = {v i : v i v i ∈ S } is an independent set of G with size k.

Max Ext EC Input: A graph G = (V, E) and a set of edges U ⊆ E. Solution: Minimal edge cover S of G. Output: Maximize |S ∩ U |. v 1 v 2 v 3 v 4 v 1 v 1 v 1 v 1,2 v 2 v 2 v 2 v 2,3 v 3 v 3 v 3 v 3,4 v 4 v 4 v 4 v 1,4 v 2,4
Using the strong inapproximability results for Max IS given in [START_REF] Trevisan | Non-approximability results for optimization problems on bounded degree instances[END_REF][START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF], observing ∆(H) = ∆(G) + 1 and |V H | ≤ 2|V | 2 , we obtain the claimed result.

Using result given in [START_REF] Monnot | Algorithmic aspects of upper edge domination[END_REF], an Ω n ε-1/2 -inapproximability result can be immediately deduced for Max Ext EDS, as well. The next result is obtained by a simple approximation preserving reduction from Max EXT VC to Max Ext EDS and improves on the mentioned immediate inapproximability result.

Theorem 18. For any constant ε ∈ (0, 1) and any ρ ∈ Ω n ε-1 , Max Ext EDS does not admit a polynomial ρ-PoE for general graphs of n vertices, unless P = NP.

Proof. we propose a simple approximation preserving reduction from Max EXT VC to Max Ext EDS similar to Theorem 16. In [START_REF] Casel | Extension of vertex cover and independent set in some classes of graphs[END_REF], it is shown that Max EXT VC is hard to approximate within ratio n ε-1 for any constant ε ∈ (0; 1) for a graph of order n. Let (G = (V, E), U ) be an instance of Max Ext VC, we build an instance (G = (V , E ), U ) of Max Ext EDS such that V = V ∪{v } and E = E∪{uv : u ∈ V }. We claim that there is a solution of size k for Max Ext VC on (G, U ) if and only if Max Ext EDS has a solution of size k on (G , U ). Without loss of generality, suppose that U = ∅. Furthermore, suppose that S is a minimal vertex cover of G such that |S ∩ U | = k, so S = {uv : u ∈ S} is a minimal edge dominating set where |S ∩ U | = k. Since S is a minimal vertex cover, for any u ∈ S, there exists at least one private edge e u ∈ E which is only covered by u, hence e u will be a private edge for any uv ∈ S . Conversely, suppose that S is a minimal edge dominating set of G containing k edges of U . In the following, we will show that how we replace any minimal edge dominating set S of G with a new minimal solution S including just some edges incident to v such that S ∩ U = S ∩ U . The procedure is completely analogous to what we did in Theorem 16, keeping all edges incident to v in S and replacing any edges non-incident to v with some edges incident to v as follows. For an non-incident edge e = xy ∈ S , not incident to v :

• if the private solution set S e \ {e} contains some edges incident to x and some edges incident to y, then e ∈ S will be replaced by xv and yv ;

• if every edge in the private solution S e is adjacent to x, replace e in S by xv , otherwise if every edge in the private solution S e is adjacent to y, replace e in S by yv . In contrast to the last hardness result, we give a simple approximation depending on the maximum degree ∆(G). Recall that PoE is meant to measure how far efficiently computable extensible subsets are from the given presolution U or to the largest possible extensible subsets of U . We say that Min Ext 1-DCPS admits a polynomial ρ-PoE if for every instance (G, U ), we can compute a solution S of G in polynomial time which satisfies PoE(S) = apx opt ≤ ρ. In the particular case U = ∅, Min Ext 1-DCPS is exactly the well known problem Minimum Maximal Matching, where the goal is to find the smallest maximal matching. In [START_REF] Dudycz | Tight approximation ratio for minimum maximal matching[END_REF][START_REF] Escoffier | New results on polynomial inapproximabilityand fixed parameter approximability of edge dominating set[END_REF], it is shown that Minimum Maximal Matching is hard to approximate with a factor better than 2 and 1.18, respectively, assuming Unique Games Conjecture (UGC) and P = NP, respectively. We complement this bound by showing the following. Theorem 20. A 2-approximation for Min Ext 1-DCPS can be computed in polynomial time.

Proof. Let (G = (V, E), U ) be an instance of Min Ext 1-DCPS. The approximate solution for Min Ext 1-DCPS consists in outputting a maximal matching M of G in the following way: we build first a maximum matching in G U and then we extend it into a maximal matching of the whole graph. Let M * be an optimal solution of Min Ext

PoE = |U | + |M U | |U | + |M * U | ≤ |M * U | + |M U | |M * U | + |M * U | ≤ |M | |M * | (1)
It is well known that that |M 1 | ≤ 2|M 2 | for any pair M 1 , M 2 of maximal matchings. So in particular, putting this inequality with M 1 = M and M 2 = M * in inequality (1), gives the expected result.

Conclusions

We have undertaken some study on several complexity aspects of extension variants of edge graph problems. Our results should be useful in particular to the (input-sensitive) enumeration algorithms community that has so far not put that much attention on edge graph problems; we are only aware of [START_REF] Golovach | An incremental polynomial time algorithm to enumerate all minimal edge dominating sets[END_REF] in this direction. Conversely, outputsensitive enumeration algorithms, e.g., for matchings have been around for more than twenty years [START_REF] Uno | Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs[END_REF]. Some thoughts on edge cover enumeration can be found in [START_REF] Wang | An efficient fixed-parameter enumeration algorithm for weighted edge dominating set[END_REF]. Our research might also inspire to revisit exact and / or parameterized algorithms on Edge Domination; previous papers like [START_REF] Fernau | Edge dominating set: Efficient enumeration-based exact algorithms[END_REF] or [START_REF] Rooij | Exact algorithms for edge domination[END_REF] did not focus on special graph classes, where we see some potential for future research.

Figure 1 :

 1 Figure 1: The gadgets H(c) and H(x). Edges not in U are drawn as thicker lines.

Figure 2 :

 2 Figure 2: The gadgets B k (v) and H (x). Edges from the forbidden subset in F B k (v) are marked with bold lines of the left side and more generally, edges not in U are marked with bold lines.

Proposition 2 .

 2 Ext 1-DCPS is polynomial-time decidable when the forbidden edges U = E \ U form a matching. Proof. Let G = (V, E) with U ⊆ E be an instance of Ext 1-DCPS where the partial subgraph G U is a collection of disjoint edges and isolated vertices. Construct an edgeweighted graph G from G as follows. First subdivide each edge in U , i.e., for each uv ∈ U , add a new vertex s uv and replace edge uv by two new edges us uv and vs uv , each with weight W = |E| + |V |. Then assign weights to the remaining edges, by setting the weight for edge xy ∈ E to 1, W + 1 or 2W + 1 if |{x, y} ∩ V (U )| equals, 0, 1 or 2, respectively.

Figure 3 :

 3 Figure 3: Block B 2r+1 (c) for clause c is depicted on the left-hand side. The subgraph H(x) = (Vx, Ex) is shown on the right-hand side. Edges of U are drawn in bold.

  true, then {xc : x appears positively in c} ∪ (E x \ {lm, l m }) ⊆ S , and if T (x) = false, then {¬xc : x appears negatively in c} ∪ (E x \ {mr, m r }) ⊆ S . • Since T is a satisfying assignment, we have already added in the previous step k ≥ 1 crossing edges connected to block B 2r+1 (c) for each clause c. Then, we arbitrarily delete k -1 edges S c of B 2r+1 (c) incident to c, and we add E(B 2r+1 (c)) \ S c to S.

Theorem 5 .

 5 an anti-clockwise ordering of edges around x i . By looking at G i and considering how variable x i appears as a negative or positive literal in the four clauses c 1 , c 2 , c 3 , c 4 in I, the construction should handle the three following cases: (1): x i ∈ c 1 , c 2 and ¬x i ∈ c 3 , c 4 ; (2): x i ∈ c 1 , c 3 and ¬x i ∈ c 2 , c 4 ; (3): x i ∈ c 1 , c 2 , c 3 and ¬x i ∈ c 4 . All other cases are included in these cases by rotations and / or interchanging x i with ¬x i . For any r ≥ 1, Ext r-EDS is NP-complete for planar bipartite graphs of maximum degree r + 2.

Figure 4 :

 4 Figure 4: Variable gadgets H(x i ) of Theorem 5. Cases (1), (2), (3) are corresponding to H(x i ), depending on how x i appears (as a negative or positive literal) in the four clauses (here, case 3 is rotated). Bold edges denote elements of Ux i . Crossing edges are marked by dashed lines.

  subset of forced edges. Now, for each vertex v of the left part L, we add the gadget B r (v) depicted to the right. Denote by H the resulting bipartite graph and consider I = (H , U ) as an instance of Ext r-EDS.

Figure 5 :

 5 Figure 5: Construction for Ext EC (planar). On the left: A variable x i appearing in four clauses c 1 , c 2 , c 3 , c 4 in I. On the right, cases 1, 2, 3: The gadgets H(x i ) in the constructed instance depend on how x i appears (negated or non-negated) in the four clauses. Bold edges denote elements of U .

Property 11 .

 11 If there is a solution of MinLUCP for the instance (G U , a, b), then ext(G, U ) = ∅. Proof. Assume that instance (G U , a, b) of MinLUCP admits a feasible solution and let G * = (V, E * ) be an optimal solution. Then, the partial subgraph H = (V, E * ∪ U ) satisfies the hypothesis of Lemma 9 (actually, H is already minimal with respect to the property ∀v ∈ V , d H (v) ≥ r). ♦ Using the outcome given in Property 11, consider the algorithm that lists all possible instances (G[U ], a, b) for MinLUCP by checking all independent sets of G[U ] included in V (U ) from an instance I = (G, U ) of Ext r-EC. This means that we try different values for function b.

Theorem 14 .

 14 For every fixed r ≥ 1, Ext r-DCPS, parameterized by the number of forbidden edges collected in U , is in FPT. More precisely, the running time can be upperbounded by O * (2 |U | ). If the graph G U is connected, then this upper bound improves to O * (1.4423 |U | ).

Figure 8 :Theorem 16 .

 816 Figure 8: (G, U ) as an instance of Ext VC is shown on the left, with V 1 = {v 2 , v 4 , v 5 } and V 2 = {v 1 , v 3 , v 6 } and U = {v 2 }. The constructed instance (G , U ) of Ext EDS is shown on the right. The vertices and edges of U and U are marked with bold lines.

Figure 9 :

 9 Figure 9: On the left side, an instance of Max IS and on the right side, the corresponding instance of Max Ext EC. Bold edges of H are the set of forced edges U .

  Let U = {uv : u ∈ U }. So G is a graph with |V | = |V | + 1 and |U | = |U |.

  Now, by setting S = {u : uv ∈ S }, we make a minimal vertex cover of G, such that|S ∩ U | = |S ∩ U |. Since |V | = |V | + 1and considering the inapproximability result ofMax Ext VC from[START_REF] Casel | Extension of vertex cover and independent set in some classes of graphs[END_REF], the proof is complete.

Theorem 19 .

 19 Max Ext EDS is 1 ∆(G U )+1 -approximable for instance (G, U ) of maximum degree ∆.Proof. Let (G = (V, E), U ) be an instance of Max Ext EDS, where the maximum degree of partial subgraph G U induced by U is bounded by ∆. Compute a maximum matching M of G U and transform it into a maximal matching M of G containing M . It is well known that any maximal matching is an edge dominating set. Obviously,(∆(G U ) + 1)|M | ≥ |U | ≥ opt Max Ext EDS (G, U ) since G U is (∆(G U ) + 1)-edge colorable.Considering Ext 1-DCPS, we need to adapt the notion of the price of extension because we have to consider subset of forbidden edges (i.e., U ); more precisely, we want to increase |U | as little as possible. Hence, the optimization problem, called Min Ext 1-DCPS, is defined as follows:Min Ext 1-DCPS Input: A graph G = (V, E)and a set of edges U ⊆ E. Solution: Maximal matching S of G. Output: Minimize |U ∪ S|.

1 -

 1 DCPS with value opt Min Ext 1-DCPS (G, U ) = |U ∪ M * |, i.e., a maximal matching of G containing a minimum number of edges outside of U . For A ∈ {U, U }, and a matching M , define M A = A ∩ M . Now, we claim that M is a 2-approximation solution for Min Ext 1-DCPS. By the decrease of PoE in term of U , and considering that |M * U | ≤ |U | together with |M * U | ≤ |M U | (M U is a maximum matching in G U ), we deduce:

  This construction is illustrated in Figure8. We claim that (G , U ) is a yes-instance of Ext EDS if and only if (G, U ) is a yes-instance of Ext VC.Suppose (G, U ) is a yes-instance for Ext VC; so there exists a minimal vertex cover S for G with U ⊆ S. The set S = {vx 1

A different generalization of edge cover was considered in[START_REF] Fernau | Vertex and edge covers with clustering properties: Complexity and algorithms[END_REF], requiring that each connected component induced by the edge cover solution contains at least t edges. Clearly, if every vertex is incident to at least r edges from the cover, then each connected component induced by the edge cover solution contains at least r edges.

Acknowledgements. The work was partially supported by the ANR project ANR-17-CE23-0010 ("ESIGMA") and by the ANR project ANR-21-CE48-0022 ("S-EX-AP-PE-AL"). We are grateful to an anonymous reviewer who showed us the idea behind Proposition 2. This improved Proposition 2 in [14].

Max Ext EDS

Input: A graph G = (V, E) and a set of edges U ⊆ E. Solution: Minimal edge dominating set S of G. Output: Maximize |S ∩ U |.

For Π = Max Ext EC or Π = Max Ext EDS, we denote the value of an optimal solution by opt Π (G, U ). Since for both problems opt Π (G, U ) ≤ |U |, with equality if and only if (G, U ) is a yes-instance of the extension variant, we deduce from our previous results that Max Ext EC and Max Ext EDS are NP-hard. In the particular case U = E, Max Ext EDS is exactly the problem called Upper EDS where the goal is to find the largest minimal edge dominating set; Upper EDS can be also viewed as Upper DS in line graphs. In [START_REF] Mcrae | Generalizing NP-completeness proofs for bipartite and chordal graphs[END_REF], it is shown that Upper EDS is NP-hard in bipartite graphs. Very recently, an NP-hardness proof for planar graphs of bounded degree, an APX-completeness result for graphs of maximum degree six and a tight Ω n ε-1/2 -inapproximability result for general graphs and for any constant ε ∈ (0, 1 2 ), are given in [START_REF] Monnot | Algorithmic aspects of upper edge domination[END_REF]. The price of extension PoE is defined exactly as the ratio of approximation, i.e., apx opt . We say that Π admits a polynomial ρ-PoE if for every instance (G, U ), we can compute a solution S of G in polynomial time which satisfies PoE(S) ≥ ρ.

Theorem 17. For any constant ε ∈ (0, 1 2 ) and any ρ ∈ Ω ∆ ε-1 and ρ ∈ Ω n ε-1 2 , Max Ext EC does not admit a polynomial ρ-PoE for general graphs of n vertices and maximum degree ∆, unless P = NP.

Proof. The proof is based on a reduction from the Maximum Independent Set problem (Max IS for short). Given a graph G = (V, E) with n vertices and m edges where V = {v 1 , . . . , v n }, as an instance of Max IS, we build a bipartite graph H = (V H , E H ) as follows: for each v i ∈ V , add a P 3 with edge set {v i v i , v i v i }, and for each edge e = v i v j ∈ E with i < j, add a middle vertex v i,j and connect v i to v j via v i,j . Consider I = (H, U ) as an instance of Max EXT EC, where the forced edge subset is given by

An example of this construction is illustrated in Figure 9.

We claim that there is a solution of size k for Max Ext EC on (H, U ) if and only if G has an independent set of size k. Suppose that S is a maximal independent set of G of size k. For each e ∈ E, let v e ∈ V \ S be a vertex which covers e. Clearly, S = {v i,j v e : e = v i v j ∈ E} ∪ {v i v i : v i ∈ V } ∪ {v i v i : v i ∈ S} is a minimal edge cover


Matthieu Gouel

Omar Darwich

Maxime Mouchet

Kevin 2023 Vermeulen

Poster: Towards a Publicly Available Framework to Process Traceroutes with MetaTrace

ABSTRACT

The objective of this research is to contribute towards the development of an open-source framework for processing large-scale traceroute datasets. By providing such a framework, we aim to benefit the community by saving time in everyday traceroute analysis and enabling the design of new scalable reactive measurements [START_REF] Allman | A reactive measurement framework[END_REF], where prior traceroute measurements are leveraged to make informed decisions for future ones [START_REF] Gouel | Zeph & Iris map the internet: A resilient reinforcement learning approach to distributed ip route tracing[END_REF][START_REF] Vermeulen | Diamond-Miner: Comprehensive discovery of the internet's topology diamonds[END_REF].

It is important to clarify that our goal is not to surpass proprietary solutions like BigQuery, which are utilized by CDNs for processing billions of traceroutes [START_REF] Flavel | FastRoute: A Scalable Load-Aware Anycast Routing Architecture for Modern CDNs[END_REF][START_REF][END_REF]. These proprietary solutions are not freely accessible to the public, whereas our focus is on creating an open and freely available framework for the wider community.

Our contributions include (1) sharing the ideas and thinking process behind building MetaTrace, which efficiently utilizes Click-House features for traceroute processing; and ( 2) providing an open-source implementation of MetaTrace 1 .

We evaluated MetaTrace using two types of queries: predicate queries for filtering traceroutes based on conditions, and aggregate queries for computing metrics on traceroutes. Our results show that MetaTrace is significantly faster compared to alternative solutions. For predicate queries, it outperforms a multiprocessed Rust solution by a factor of 552 and is 3.4 times faster than ClickHouse without MetaTrace optimizations. For aggregate queries, MetaTrace processes 202 million traceroutes in 11 seconds, with its performance scaling linearly with traceroute volume. Notably, on a single server, MetaTrace can perform a predicate query on a 6-year dataset of 6 billion traceroutes in just 240 seconds.

Furthermore, MetaTrace is resource-efficient, making it accessible for research groups with limited resources to conduct Internetscale traceroute studies.

Conference (IMC '23), October 24-26, 2023, Montreal, QC, Canada. ACM, New York, NY, USA, 2 pages. https://doi.org/10.1145/3618257.3625001

METHODOLOGY

Which processing do we want to perform? The initial consideration before selecting a database was determining the common computations we performed on traceroutes. Our use-cases align with previous studies [START_REF] Cunha | Sibyl: A Practical Internet Route Oracle[END_REF][START_REF] Fontugne | Pinpointing delay and forwarding anomalies using large-scale traceroute measurements[END_REF][START_REF] Vermeulen | Diamond-Miner: Comprehensive discovery of the internet's topology diamonds[END_REF] that focus on computing aggregated statistics, such as the RTT between a source and a destination, or converting IP-level paths from traceroutes into AS-level paths and analyze specific ASes like Tier 1s or CDNs.

The common use cases can be translated into two general query types: aggregate queries and predicate queries. On one hand, an aggregate query calculates summarized information about the data, such as the minimum RTT among a set of traceroutes. On the other hand, a predicate query returns only the traceroutes that meet specific conditions, such as whether the traceroute traverses a particular AS.

Which database to choose? Optimizing the choice of a database for performant aggregate and predicate queries is not overly restrictive. However, we observed that there is no compelling reason to modify or delete traceroute data. Consequently, we sought a database that prioritizes efficient read operations. We found the ClickHouse database [START_REF] Clickhouse | ClickHouse Database[END_REF] to be a promising candidate as it is promoted as a database optimized for reads and aggregations. Moreover, ClickHouse offers a comprehensive set of convenient features for expressing complex aggregate queries. Notably, ClickHouse introduces a powerful feature called "groupArray", which facilitates manipulation of data in aggregate queries.

While the benchmark conducted by ClickHouse itself [START_REF] Clickhouse | ClickHouse Benchmark[END_REF] was compelling, we independently verified its superior performance over standard solutions like MySQL and PostgreSQL, even on simple queries. This confirmed that ClickHouse significantly outperformed these solutions by orders of magnitude in our specific setup. However, it is important to clarify that we are not asserting ClickHouse as the ultimate solution for processing traceroutes. Nevertheless, based on our experience, ClickHouse has proven to be highly reliable and has fulfilled our requirements for several years [START_REF] Gouel | Zeph & Iris map the internet: A resilient reinforcement learning approach to distributed ip route tracing[END_REF][START_REF] Vermeulen | Diamond-Miner: Comprehensive discovery of the internet's topology diamonds[END_REF][START_REF] Vermeulen | Internet scale reverse traceroute[END_REF]. We believe it is valuable to share this information with the community. Furthermore, we emphasize that ClickHouse employs a SQL-like language that is easy to learn, requiring minimal effort for the community to adopt such a database. Finally, we have developed an open-source tool 2 that enables the conversion of traceroute data from one commonly used format [START_REF]Archipelago[END_REF][START_REF]RIPE Atlas: A global internet measurement network[END_REF] to another, including the MetaTrace format, in order to facilitate the integration of multiple traceroute datasets.

Which schema to represent a traceroute? Now that we have selected our database, we need to determine an appropriate schema for storing the traceroutes. Given that ClickHouse is a columnoriented database, we structure our schema based on the fields present in an ICMP reply to a traceroute probe (e.g., TTL, RTT). Additionally, we include fields that uniquely identify the traceroute that generated the probe, such as the flow identifier and traceroute timestamp. In this design, a traceroute is represented as a collection of rows, where each row contains these fields. The flow identifier within each row enables differentiation between load-balanced paths, as encountered in per-flow load balancing scenarios [START_REF] Vermeulen | Diamond-Miner: Comprehensive discovery of the internet's topology diamonds[END_REF].

This data format offers several advantages. First, it is compatible with all existing traceroute tools, serving as the lowest common denominator for platforms and tools that utilize traceroute techniques. These tools typically send TTL-limited probes to generate ICMP TTL exceeded messages from routers along the path. Second, the format is memory-efficient for predicate queries. By loading only the relevant column(s) for a predicate, it becomes feasible to identify the rows that match the predicate efficiently.

How to improve the database performance? Finally, we can leverage ClickHouse's features to minimize the query time and the resource usage. To achieve this, we judiciously select how to sort traceroute data enabling queries to be processed in blocks of rows. ClickHouse facilitates this through its "sorting key" mechanism. It enables efficient utilization of RAM while also optimizing disk usage, as the sorting key also influences the compression quality of the columns.

However, it is essential to note that a table can have only one sorting key, limiting the ability to optimize for predicate queries on arbitrary columns. Assuming we use the sorting key (source, destination, timestamp), our objective is to have a mechanism to sort the data by (predicate, source, destination, timestamp), where the predicate can be a subset of columns or even the result of an aggregate query per (source, destination, timestamp). ClickHouse provides a solution for this through the materialized view feature. It enables us to generate a table from the computed result, thus creating a materialized view for each predicate, significantly enhancing predicate query performance. Finally, since the materialized view is properly sorted, the increase in disk usage remains reasonable.

How to add metadata on traceroutes? Metadata refers to additional information associated with IP addresses, such as ASes or geolocation. ClickHouse offers a feature called "dictionary", which enables the creation of a table containing mappings from IP addresses to corresponding values. Specifically, this dictionary can be implemented as a radix tree that maps IP prefixes to metadata. To ensure the most relevant metadata is used for each traceroute, the radix tree can be parameterized by a date.

EVALUATION

On a dataset of 202 million traceroutes from one day of RIPE Atlas [START_REF]RIPE Atlas: A global internet measurement network[END_REF], MetaTrace takes 25% less disk space than the compressed JSON source data. MetaTrace is able to serve predicate queries 552x faster than a multiprocessed Rust solution, and is 3.4x faster than the ClickHouse database without MetaTrace's optimizations. On aggregate queries, MetaTrace is 62x faster than our Rust solution. Overall, MetaTrace is able to serve both types of queries with a very reasonable 1.6 GB maximum usage of memory. MetaTrace's performance scales linearly with the number of traceroutes. The technical details of the evaluation of MetaTrace can be found in a distinct technical report [START_REF] Gouel | Towards a publicly available framework to process traceroutes with MetaTrace[END_REF].

CONCLUSION

This work highlights the advantages of utilizing MetaTrace, an intelligent utilization of ClickHouse, for traceroute processing. Meta-Trace outperforms multiprocessed Python and Rust solutions, as well as the raw ClickHouse database, in terms of query response time for both predicate and aggregate queries. Furthermore, this performance improvement is achieved while utilizing reasonable amounts of memory, CPU, and disk resources. As a result, Meta-Trace enables the processing of large traceroute datasets, potentially in combination, within a local environment. This work will hopefully enable us and the community to build reactive traceroute measurement frameworks at Internet scale.

https://github.com/dioptra-io/pantrace

ACKNOWLEDGEMENTS

A research grant from the French Ministry for Armed Forces has made this work possible. We thank Robert Beverly for their careful reading and feedback on earlier versions of this work. Matthieu Gouel is associated with Sorbonne University, CNRS, Laboratoire d'informatique de Paris 6, LIP6, F-75005 Paris, France. Matthieu Gouel has partially carried out the work presented in this extended abstract at LINCS (www.lincs.fr). Omar Darwich and Kevin Vermeulen are associated with the LAAS-CNRS, Paul Sabatier University, CNRS, Toulouse, France.