A Fixed-Parameter Algorithm for Max Edge Domination? Tesshu Hanaka and Hirotaka Ono Department of Economic Engineering, Kyushu University, Fukuoka 812-8581, Japan ono@csce.kyushu-u.ac.jp Abstract. In a graph, an edge is said to dominate itself and its adjacent edges. Given an undirected and edge-weighted graph G = (V, E) and an integer k, Max Edge Domination problem (MaxED) is to find a subset K ⊆ E with cardinality at most k such that total weight of edges domi- nated by K is maximized. MaxED is NP-hard due to the NP-hardness of the minimum edge dominating set problem. In this paper, we present fixed-parameter algorithms for MaxED with respect to treewidth ω. We first present an O(3ω · k · n · (k + ω 2 ))-time algorithm. This algorithm ena- bles us to design a subexponential fixed-parameter algorithm of MaxED for apex-minor-free graphs, which is a graph class that includes planar graphs. Keywords: max edge domination, fixed-parameter algorithm, bounded treewidth, subexponential FPT 1 Introduction Let G = (V (G), E(G)) be an undirected and positive edge-weighted graph, where V (G) is the set of n vertices and E(G) is the set of m edges. These V (G) and E(G) are simply denoted by V and E, respectively. For an edge e = {u, v} ∈ E, its weight is denoted by we or wuv . For E 0 S ⊆ E, we denote by V (E 0 ) the set of 0 0 vertices that appear in E , that is, V (E ) = e∈E 0 e. An edge is said to dominate itself and its all adjacent edges. We denote by DG (e) the set of edges dominated by an edge e, that is, DG (e) = {e0 ∈ E(G) | e0 ∩ e 6= ∅}. For a set E 0 of edges, we denote by DG (E 0 ) the set of edges dominated by an edge in E 0 , that is, DG (E) = {e ∈ E(G) | e ∩ V (E 0 ) 6= ∅}. In these notations, we may omit the subscript G if it is clear. Given G = (V, E) and an integer k, Max Edge Domination problem (MaxED) is to find a subset K ⊆ E with cardinality at most k such that total weight of edges dominated by K is maximized. This problem is formulated by the following optimization problem: X max we . K⊆E,|K|≤k e∈D(K) ? This work is partially supported by KAKENHI grant number 24106004, 25104521, 26540005 and Asahi Glass Foundation. 32 T. Hanaka and H. Ono In a sense of the decision problem, MaxED for an unweighted graph is equivalent to the well-known Minimum Edge Dominating Set (EDS), that is, the problem to find a minimum subset of E 0 dominating all edges in E. Due to the NP-hardness of EDS, MaxED is NP-hard, and several approximability (or inapproximability) results are known. For example, MaxED is APX-hard [21], and a greedy algorithm achieves approximation ratio max{1 − 1/e, k/s}, where s is the size of maximal matching [17]. In this paper, we consider fixed-parameter tractability of MaxED. Given a problem with input size n and a parameter γ, the problem is said to be fixed- parameter tractable (FPT, for short) if it can be solved in f (γ) · nO(1) time, where f is a certain function that depends only on parameter γ. An algorithm that achieves the above running time is called a fixed-parameter algorithm. Par- ticularly, if f (γ) = 2o(γ) , the problem is called subexponential fixed-parameter tractable. For general concepts of fixed parameter tractability and related to- pics, see [9, 12, 22]. It is known that EDS is FPT with respect to the solution size [10], but this does not imply the fixed parameter tractability of MaxED with respect to k, because the solution size of EDS can be much larger than k in gene- ral. In fact, MaxED with parameter k has shown to be W [1]-hard [3]. Recently, Guo, J. et al. proved that MaxED is W [1]-hard even for unweighted bipartite graphs [16]. This implies that there unlikely exists a fixed-parameter algorithm for MaxED with parameter k. In this paper, we show that (1) MaxED with respect to treewidth ω is FPT, and (2) MaxED with respect to k is subexponential FPT for apex-minor-free graphs, which is a graph class that includes planar graphs. For the former result, we present an O(3ω ·k·n·(k+ω 2 ))-time algorithm for MaxED. The fixed-parameter tractability of MaxED with respect to treewidth is rather straightforward, but the improved running time plays a key role of the latter result. There are many combinatorial optimization problems that have subexpo- nential fixed-parameter algorithms for superclasses of planar graphs. A powerful meta-theorem to design a subexponential fixed-parameter algorithm is known for problems having bidimensionality ([5, Theorem 8.1]). Roughly speaking, if a problem has bidimensionality, the treewidth of a planar √ graph (or a graph in some superclasses of planar graphs) is bounded by O( k ∗ ), where k ∗ is the optimal value of the problem. By combining this with 2O(ω) nO(1) -time algo- rithm, a subexponential fixed-parameter algorithm can be obtained. Although EDS with respect to solution size is an example of problems having bidimension- ality, MaxED with respect to k is unfortunately not. Instead, we try to choose a special K ∗ among all the optimal solutions. In this strategy, K ∗ and its neigh- bors are localized so that the treewidth √ of the subgraph of G induced by K ∗ and its neighbors is bounded by O( k). Then, we can expect a similar speeding-up effect. The points become (i) how we localize K ∗ , and (ii) the design of a fixed- parameter algorithm whose exponent is linear of ω. This scheme is proposed by [14] to design a subexponential fixed-parameter algorithm of Partial Vertex Cover with respect to k, which is also not a bidimensional problem, subexpo- nential fixed-parameter algorithms with respect to k for the partial dominating A Fixed Parameter Algorithm ... 33 set and the partial vertex cover of apex-minor-free graphs. Another example of employing this scheme is found in [19]. To apply the scheme, we utilize a gene- ralized version of EDS, say r-EDS, and investigate the approximability. Based on these together with the faster algorithm mentioned in the previous paragraph, we show √ that there is an algorithm solving MaxED for apex-minor-free graphs in 2O( k) · nO(1) time. 1.1 Related Work As mentioned above, MaxED is strongly related to EDS. EDS is the problem of finding a minimum subset S ⊆ E such that all edges e ∈ E \ S are adjacent to at least one edge in S. EDS is also known as Minimum Maximal Matching. There are many studies for EDS from the viewpoint of (in)approximability, parame- terized complexity and exact algorithms. For example, EDS is 2-approximable in polynomial time [15], NP-hard to approximate within any factor better than 7/6 [4], and can be exactly solved in O∗ (1.3160n ) time, where O∗ -notation sup- presses all polynomially bounded factors [24]. EDS is also known to be fixed- parameter tractable with respect to several parameters, e.g., the solution size of EDS, treewidth, and so on. For example, an O∗ (1.821τ )-time algorithm of ∗ EDS [23] and an O∗ (2.1479k )-time algorithm of EDS for cubic graphs are pro- posed, where τ is the solution size of the minimum vertex cover, and k ∗ is the solution size of EDS. As mentioned before, EDS with solution size is known to be a bidimensional problem. By using the bidimensonality theory, a subexponential fixed-parameter algorithm for apex-minor-free graphs can be designed [6]. Compared with EDS, MaxED itself is less studied. MaxED is a special case of Maximum Coverage Problem (MaxC): Given n elements xi with positive weight wi , i = 1, 2, . . . , n, sets of S1 , S2 , . . . , Sm ⊆ {x1 , x2 , . . . , xn } and P a positive in- teger k, find a set C ⊆ {1, 2, . . . , m} such that |C| ≤ k and xi ∈S wi is j∈C Sj maximized. Since MaxC is known to be (1 − 1/e)-approximable in polynomial time [8, 18], so is MaxED. Though the approximation ratio is tight for MaxC under P6=NP ([11]), MaxED is just known to be APX-hard [21]. As for the paramete- rized complexity, MaxED with respect to k has been shown to be W [1]-hard[3]. Recently, Guo et al. proved that MaxED is W [1]-hard even for unweighted bi- partite graphs [16]. This paper is organized as follows. In Section 2, we introduce notations and definitions. In Sections 3 and 4, we present two fixed-parameter algorithms for MaxED. We first present a basic algorithm in Section√3, and then improve the running time in Section 4. Finally, we show that a 2O( k) · nO(1) -time algorithm of MaxED for apex-minor-free graphs in Section 5. 2 Preliminaries Let G = (V, E) be an undirected and edge-weighted graph. For V 0 ⊆ V , let G[V 0 ] denote a subgraph of G induced by V 0 . For E 0 ⊆ E, we simply denote G[V (E 0 )] by G[E 0 ]. 34 T. Hanaka and H. Ono 2.1 Tree Decomposition Our algorithms that will be presented in Sections 3 and 4 are based on dynamic programming on tree decomposition. In this subsection, we give the definition of tree decomposition. Definition 1. A tree decomposition of a graph G = (V, E) is defined as a pair hX , T i, where X = {X1 , X2 , . . . , XN ⊆ V }, and T is a tree whose nodes are labeled by 1, 2, . . . , N , such that S 1. i∈I Xi = V . 2. For ∀{u, v} ∈ E, there exists Xi such that {u, v} ⊆ Xi . 3. For all i, j, k ∈ {1, 2, . . . , N }, if j lies on the path from i to k in T , then Xi ∩ Xk ⊆ Xj . In the following, we call T a decomposition tree, and we use term “nodes” (not “vertices”) for T to avoid a confusion. The width of a tree decomposition hX , T i is is defined by maxi∈{1,2,...,N } |Xi | − 1, and the treewidth of G, denoted by tw(G), is the minimum width over all tree decompositions of G. We sometimes use ω to represent tw(G). In general, computing tw(G) of a given G is NP-hard [1], but fixed-parameter tractable with respect to the treewidth [2]. In the following, we assume that a decomposition tree with the minimum treewidth is given. Moreover, we introduce a very useful tree decomposition for some algorithms, called nice tree decomposition. In the sense, it is a special binary tree decompo- sition. Definition 2. . A tree decomposition hX , T i is called nice tree decomposition if it satisfies the following: 1. T is rooted at a designated node XN ∈ X , called root node. 2. Every node of the tree T has at most two children nodes. 3. The nodes of T hold one of the following four node types: – A leaf node i which has no children and the corresponding leaf bag Xi has |Xi | = 1. – An introduce node i which has one child j with Xi = Xj ∪ {v} for a vertex v ∈ V . – A Forget node i which has one child j with Xi = Xj \ {v} for a vertex v∈V . – A Join node i which has two children j, l ∈ X with Xi = Xj = Xl . 2.2 r-Edge Dominating Set We define a new problem by extending the notion of domination. We first define distance between two edges e1 = {u1 , v1 } and e2 = {u2 , v2 } as the shortest path length among (u1 , u2 )-path, (u1 , v2 )-path, (v1 , u2 )-path and (v1 , v2 )-path, which we denote by d(e1 , e2 ). r-Edge Dominating Set (r-EDS) is the problem of finding an edge set S ⊆ E with minimum size such that for every e ∈ E \ S, A Fixed Parameter Algorithm ... 35 d(e, e0 ) < r holds for some edge e0 ∈ S. This problem is clearly a generalization of EDS, because 1-EDS is equivalent to EDS. To design a subexponential fixed- parameter algorithm in Section 5, we design a constant-factor approximation algorithm for 2-EDS. 3 Fixed-Parameter Algorithm Bounded Treewidth In this section, we present a dynamic programming (DP) algorithm based on a nice decomposition tree. By the assumption above, we are already given a nice decomposition tree with treewidth of ω. We assume that the algorithm first prepares k + 1 DP tables for each Xi , so (k + 1) · N tables in total. The algorithm runs in the bottom-up manner; it fills tables from leaf nodes to the root node. For simplicity, we assume that the indices of Xi correspond to the order that the algorithm visits Xi ; the algorithm fills tables of X1 , X2 , . . . , XN in this order. We further give several assumptions for the tree decomposition. We define a mapping g from E to Xi . For an edge e ∈ E, there exists at least one bag Xi such that e ⊆ Xi by the definition of tree decomposition. We define g(e) = Xi where i is the smallest index such that e ⊆ Xi . By defining g, we make clear in which node we handle e. Based on g, we partition E into E1 , E2 , . . . , EN , where Ei = {e ∈ E | g(e) = Xi }. We then define a subgraph Gi = (Vi , Ei ) of G, where Vi = Xi . (r) Now, we prepare DP tables Ai like Table 1 for each Xi , where r = 0, 1, · · · , k. Here, r represents the number of edges selected as a part of a solution at the (r) (r) moment. In table Ai , let |Vi | = ni . Table Ai consists of ni + 1 columns and ni 3 rows. The first ni columns represent the statuses of vertices in Gi . The last column represents the value of the corresponding statuses output by the function defined latter. Each vertex v in Xi has the status c(v) ∈ {0, 1, 2} and for each (r) row in Ai , we define the coloring c = (c(v1 ), c(v2 ), · · · , c(vni )) ∈ {0, 1, 2}|Vi | . We also define c(Vi \V 0 ) where V 0 ⊆ Vi as a part of coloring c. Status 0 represents the vertex which is not the endpoint of the solution, while status 1 means that (r) Table 1. Ai (r) v1 v2 · · · vni fi () 0 0 ··· 0 10 1 0 ··· 0 11 .. .. .. .. . . . . 1 1 ··· 1 - 2 0 ··· 0 - .. .. .. .. . . . . 2 2 ··· 2 - 36 T. Hanaka and H. Ono the vertex is the endpoint of that. In the sense, status 2 is special status. That is, the vertex with 2 is not the endpoint of the solution in Xi but it will be the endpoint of that after Xi . (r) We define the function fi (c) : {0, 1, 2}|Vi | → R ∪ {−∞} for each DP table (r) Ai . This function’s value represents the total weight of edges dominated by the part of solution until Xi . If fi (c) = −∞, it means the coloring c is invalid. We perform dynamic programming from leaf nodes. First, we start initia- lization for all leaf node. For each leaf node i, we assume that Xi = {x} and (r) c = c(x). Then, we compute fi (c) as follows: ( (r) 0 (r = 0 and c ∈ {0, 2}) fi (c) := . −∞ (otherwise) Then, we explain update step. Let c0 be the coloring in Xi−1 . Update methods are different for each node type as follows. Introduce node (Xi = Xi−1 ∪ {x}) : There are following two cases for an introduce node. case 1. c = c0 × {0} or c = c0 × {2} where c0 = c0 (Vi−1 ) = c(Vi \ {x}). case 2. There is a neighbor z of x in Xi−1 such that c = c(Vi \({z}∪{x}))× {1} × {1} and c0 = c(Vi−1 \ {z}) × {2}. (r) For each case, fi (c) is defined as follows.  (r) 0 fi−1 (c ) + σ(c)  (case 1) (r) (r−1) 0 fi (c) := fi−1 (c ) + σ(c) (case 2) ,  −∞ (otherwise)  P where σ(c) = u∈{vi |c(vi )6=0} wuv . The value σ(c) represents the total weight (u,v)∈Ei of edges dominated by the coloring c in Xi . Forget node (Xi = Xi−1 \ {x}) : (r) For a forget node, we can immediately define fi (c) as follows: (r) (r) (r) fi (c) := max{fi−1 (c × {0}), fi−1 (c × {1})}. We do not consider the case that c(x) = 2 because x will be never the endpoint of the solution due to forget node. Join node (Xi = Xj = Xl ) : We assume that Xj and Xl are the children nodes of Xi . For a join node, (r) we have to compute fi for the combination of Xj and Xl . Because Xi = Xj = Xl , there is the coloring c in each node Xi , Xj and Xl . Thus, we can (r) define fi (c) as follows: (r) (r ) (r−rj ) fi (c) := max {fj j (c), fl (c)}. 0≤rj ≤r A Fixed Parameter Algorithm ... 37 Finally, we compute the root node. It is one of the four node type, thus we firstly update DP table following above methods. Then we modify the value fr (c). (r) That is, if there is a vertex v such that c(v) = 2 in coloring c, let fN (c) := −∞. (r) Then we output maxr,c fN (c). Now, we consider the running time of this algorithm. For each leaf node, we can initialize DP tables in O(k)-time since |Xi | = 1. Then, we analyze update step. When the node is introduce node, the running time is O(3ω · k · ω 2 ) because ni = O(ω) for each node Xi and we can calculate σ(c) in O(ω 2 )-time for each row. For a forget node, we only check two coloring c × {0} and c × {1} of Xi−1 corresponding to c in Xi . Therefore, the running time of a forget node is O(3ω ·k). (r) In a join node, we search the best combination of Xj and Xl for each fi (c) in ω 2 O(k)-time. Thus, the running time of a forget node is O(3 ·k )-time. Finally, we (r) modify DP table and output maxr,c fN (c) in the root node in O(3ω · k · ω)-time. Thus, the total running time is as follows: O(k · N ) + O(3ω · k · N · (k + ω 2 )) + O(3ω · k · ω) = O(3ω · k · n · (k + ω 2 )). Therefore, we can show the following theorem. Theorem 1. There is an O(3ω · k · n · (k + ω 2 ))-time algorithm for MaxED. 4 Subexponentioal Fixed-Parameter Algorithm In this section, we will show the following theorem by presenting a subexponen- tial fixed-parameter algorithm. √ Theorem 2. There exists a 2O( k) · nO(1) -time algorithm for MaxED on apex- minor free graphs. √ Let G be an apex-minor-free graph. If tw(G) = O( k) holds, then Theorem 1 proves Theorem 2. Otherwise we will remove a set I of irrelevant edges from G so that at least one optimal solution is a subset of E \ I √ and optimal also for the problem in G[E \ I], and we have tw(G[E \ I]) = O( k). Then, applying Theorem 1 to G[E \I], we obtain Theorem 2. To identify such a set I of irrelevant edges, we introduce the notion of lexicographically smallest solution. The ideas follow from the ones given by Fomin et al. [14] as mentioned in Introduction. Definition 3. Given an ordering σ = e1 e2 . . . em of E and subsets X and Y of E, we say that X is lexicographically smaller than Y , denoted by X ≤σ Y , if Eσi ∩ X = Eσi ∩ Y and ei+1 ∈ Y \ X for some i ∈ {0, 1, . . . , m}, where Eσi = {e1 , e2 , . . . , ei } for i ∈ {1, 2, . . . , m} and Eσ0 = ∅. We call a set K ⊆ E the lexicographically smallest (optimal) solution for MaxED if for any other solution K 0 for the MaxED we have that K ≤σ K 0 . Let σ = e1 e2 . . . em be an ordering of the edges according to the total weight of the Pedges dominated by an edge in non-increasing order. For e ∈ E, let µ(e) = e0 ∈D(e) we0 . In the ordering σ, µ(e1 ) ≥ µ(e2 ) ≥ · · · ≥ µ(em−1 ) ≥ µ(em ), 38 T. Hanaka and H. Ono holds. Throughout the section, we assume that E is ordered by σ, and may use Eσ instead of E to emphasize this. We also denote {e1 , e2 , . . . , ei } by Eσi . We will propose an algorithm that finds not an optimal solution but the lexicographically smallest optimal solution for MaxED, which can make it clear to define a set of irrelevant edges. To this end, we give the following three lemmas, though the proof of Lemma 3 is omitted. Lemma 1. Given a graph G = (V, Eσ ), let K = {ui1 , ui2 , . . . , uik }be the lexico- graphically smallest solution for MaxED, where uik = ej for some j. Then, K is a 2-EDS of size k for G[Eσj ]. Proof. Show this by contradiction. Assume that a lexicographically smallest so- lution K of MaxED is not a 2-EDS for G[Eσj ]. This implies that there exists an edge ei (1 ≤ i ≤ j) such that D2 (ei ) ∩ K = ∅. Let K 0 = K \ {ej } ∪ {ei }. Clearly, |K 0 | = |K|. Since any edge e ∈ D(ei ) is not dominated by K, we have µ(K 0 ) ≥ µ(K) − µ(ej ) + µ(ei ) ≥ µ(K), a contradiction. t u Lemma 2. Let G be √an apex-minor-free graph. If G has an r-EDS of size at most k, tw(G) = O(r k). Proof. If G has an r-EDS of size k, then it has (2k, √ r)-center. Therefore, according to Lemma 8 of [19], the treewidth of G is O(r k). t u Lemma 3. On apex-minor-free graphs, there exists an EPTAS for r-EDS. Now we are ready to give a subexponential fixed-parameter algorithm. First, we sort e1 , e2 , . . . , em ∈ Eσ and scan it from em to e1 . We put a stick in the right of em and let s := m. In an intermediate stage, if G[Eσj ] does not have a 2-edge dominating set of size at most (1 + )k, let s := j − 1, N := N ∪ {ej }, and then we move the stick to the left of ej . Notice that the edges in the left of the stick belong to E \ N and the edges in the right are in N . The contraposition of Lemma 1 denotes that the lexicographically smallest solution for MaxED K lies E \ N , that is, K ⊆ E \ N . If G[Eσj ] has a 2-edge dominating set √ of size at most (1 + )k, then we find a subgraph G0 such that tw(G0 ) = O( k) and there exists K 0 ⊆ E(G0 ) satisfying µ(K) = µ(K 0 ) for an optimal solution K of G, where |K 0 | ≤ k and |K| ≤ k. Given the parameter (G = (V, Eσ ), k, , ∅) where  > 0, the algorithm is described as follows. Subexponential fixed-parameter Algorithm Step 0. Let p := m Step 1. While there does not exist 2-edge dominating set of size at most (1+)k for G[Eσp ], repeat N := N ∪ {ep }, p := p − 1. Step 2. Let I = {e | e ∈ N, D(e) ⊆ N } and E 0 = E \ I. A Fixed Parameter Algorithm ... 39 Step 3. Find a tree decomposition of G0 = G[E 0 ] using the constant factor approximation algorithm of Demaine et al. [7] for computing the treewidth of H-minor-free graph. Step 4. Apply the algorithm of Theorem 1 to G[E 0 ]. The correctness of the algorithm can be shown by following the proof of Theorem 1 of [14]. In Step 1, we identify an edge set N that are not used in lexicographically smallest solution of MaxED. edge in E \ N . We check whether G[Eσp ] has 2-edge dominating set of size at most (1 + )k by Lemma 3. If G[Eσp ] does not have it, then {ui1 , ui2 , . . . uik } satisfying uik = ep is not the lexico- graphically smallest solution for MaxED by Lemma 1. Therefore, ep ∈ / K. We will show latter half is valid. Note that edges in N are not candidates. Thus, an edge e ∈ N adjacent to only edges in N is not dominated by K, that is, the set I is a set of irrelevant edges. Therefore, we delete a set of such edges as I. Let E 0 = E \ I. There exists K of size at most k in G such that µ(K) = maxK⊆E,|K|≤k µ(K) if and only if there exists K 0 ⊆ E 0 in G0 such that |K 0 | ≤ k and µ(K 0 ) = maxK 0 ⊆E 0 ,|K|≤k µ(K 0 ). Hence, we will find K 0 in G0 where |K 0 | ≤ k by Theorem 1. We analyze the running time of this algorithm. When the loop in Step 2. is broken out, G[E \N ] has 2-edge dominating set of size at most (1+)k. Let D2 be 2-edge dominating set of size at most (1+)k. Then, D2 is 3-edge dominating set for G[E 0 ] because all edges p such that e ∈ N 0 √∩ E are adjacent to edges in E \ N . 0 Therefore, tw(G ) = O(3 (1 + )k) = O( k) is shown by Lemma 2. We use the constant factor approximation algorithm of Demaine et al. [7] to compute the treewidth of H-minor-free√ graph, then we find tree decomposition such that the size of treewidth is O( k) for G[E 0 ] in nO(1) -time. Finally, we use the algorithm of Theorem 1 to find optimal solution for MaxED in√O(3ω · k · n · (k + ω 2 ))-time. Therefore, our algorithm achieves running time 2O( k) · nO(1) . References 1. Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods 8(2), 277–284 (1987) 2. Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25(6), 1305–1317 (1996) 3. Cai, L.: Parameterized Complexity of Cardinality Constrained Optimization Prob- lems. In: The Computer Journal 51(1), 102–121 (2008) 4. Chlebı́k, M., Chlebı́ková, J.: Approximation hardness of edge dominating set prob- lems. Journal of Combinatorial Optimization 11(3), 279–290 (2006) 5. Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. The Computer Journal 51(3), 292–302 (2008) 6. Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with appli- cations through bidimensionality. Combinatorica 28(1), 19–36 (2008) 7. Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.i.: Algorithmic graph minor the- ory: Decomposition, approximation, and coloring. In: Proceedings of 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 637–646. IEEE (2005) 40 T. Hanaka and H. Ono 8. Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with n onnegative data. Mathematics of Operations Research 7(4), 515–531 (1982) 9. Downey, R.G., Fellows, M.R.: Parameterized complexity, vol. 3. Springer- Heidelberg (1999) 10. Escoffier, B., Monnot, J., Paschos, V., Xiao, M.: New results on polynomial inapproximability and fixed parameter approximability of edge dominating set. In: Parameterized and Exact Computation, Lecture Notes in Computer Science, vol. 7535, pp. 25–36. Springer Berlin Heidelberg (2012) 11. Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM (JACM) 45(4), 634–652 (1998) 12. Flum, J., Grohe, M.: Parameterized complexity theory, vol. 3. Springer (2006) 13. Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and eptas. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 748–759. SIAM (2011) 14. Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Subexponential algorithms for partial cover problems. Information Processing Letters 111(16), 814–818 (2011) 15. Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discrete Applied Mathematics 118(3), 199–207 (2002) 16. Guo, J., Shrestha, Y.: Parameterized complexity of edge interdiction problems. In: Computing and Combinatorics, Lecture Notes in Computer Science, vol. 8591, pp. 166–178. Springer International Publishing (2014) 17. Hanaka, T., Ono, H.: Approximation ratios of greedy algorithms for max edge domination. In: Proceedings of Hinokuni Information Symposium (in Japanese). Information Processing Society of Japan (2013) 18. Hochbaum, D.S.: Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In: Approximation algorithms for NP-hard problems. pp. 94–143. PWS Publishing Co. (1996) 19. Ishii, T., Ono, H., Uno, Y.: Subexponential fixed-parameter algorithms for partial vector domination. In: Combinatorial Optimization, pp. 292–304. Lecture Notes in Computer Science, Springer International p Publishing (2014) 20. Micali, S., Vazirani, V.V.: An O( |V ||E|) algoithm for finding maximum matching in general graphs. In: Proceedings of 21st Annual Symposium on Foundations of Computer Science. pp. 17–27. IEEE (1980) 21. Miyano, E., Ono, H.: Maximum domination problem. In: Proceedings of the Seven- teenth Computing: The Australasian Theory Symposium-Volume 119. pp. 55–62. Australian Computer Society, Inc. (2011) 22. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006) 23. Xiao, M., Nagamochi, H.: Parameterized edge dominating set in cubic graphs. In: Frontiers in Algorithmics and Algorithmic Aspects in Information and Manage- ment, Lecture Notes in Computer Science, vol. 6681, pp. 100–112. Springer Berlin Heidelberg (2011) 24. Xiao, M., Nagamochi, H.: A refined exact algorithm for edge dominating set. In: Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 7287, pp. 360–372. Springer Berlin Heidelberg (2012)