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 nd a subset K E with cardinality at most k such that total weight of edges dominated 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 xed-parameter algorithms for MaxED with respect to treewidth !. We rst present an O(3! k n (k + !2))-time algorithm. This algorithm enables us to design a subexponential xed-parameter algorithm of MaxED for apex-minor-free graphs, which is a graph class that includes planar graphs.
max K E;jKj k e2D(K)
X
we:
? This work is partially supported by KAKENHI grant number 24106004, 25104521,
26540005 and Asahi Glass Foundation.
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
nd a minimum subset of E0 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 [
In this paper, we consider xed-parameter tractability of MaxED. Given
a problem with input size n and a parameter , the problem is said to be
xedparameter 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 xed-parameter algorithm.
Particularly, if f ( ) = 2o( ), the problem is called subexponential xed-parameter
tractable. For general concepts of xed parameter tractability and related
topics, see [
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 xed-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
subexponential xed-parameter algorithms for superclasses of planar graphs. A powerful
meta-theorem to design a subexponential xed-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(pk ), where k is the
optimal value of the problem. By combining this with 2O(!)nO(1)-time
algorithm, a subexponential xed-parameter algorithm can be obtained. Although
EDS with respect to solution size is an example of problems having
bidimensionality, 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
neighbors are localized so that the treewidth of the subgraph of G induced by K and
its neighbors is bounded by O(pk). Then, we can expect a similar speeding-up
e ect. The points become (i) how we localize K , and (ii) the design of a
xedparameter algorithm whose exponent is linear of !. This scheme is proposed
by [
As mentioned above, MaxED is strongly related to EDS. EDS is the problem of
nding a minimum subset S E such that all edges e 2 E n 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,
parameterized complexity and exact algorithms. For example, EDS is 2-approximable
in polynomial time [
As mentioned before, EDS with solution size is known to be a bidimensional
problem. By using the bidimensonality theory, a subexponential xed-parameter
algorithm for apex-minor-free graphs can be designed [
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 fx1; x2; : : : ; xng and a positive
integer k, nd a set C f1; 2; : : : ; mg such that jCj k and Pxi2Sj2C Sj wi is
maximized. Since MaxC is known to be (1 1=e)-approximable in polynomial
time [
This paper is organized as follows. In Section 2, we introduce notations and de nitions. In Sections 3 and 4, we present two xed-parameter algorithms for MaxED. We rst present a basic algorithm in Section 3, and then improve the running time in Section 4. Finally, we show that a 2O(pk) nO(1)-time algorithm of MaxED for apex-minor-free graphs in Section 5. 2
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 E0 E, we simply denote G[V (E0)] by G[E0]. 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 de nition of tree decomposition.
De nition 1. A tree decomposition of a graph G = (V; E) is de ned as a pair hX ; T i, where X = fX1; X2; : : : ; XN V g, and T is a tree whose nodes are labeled by 1; 2; : : : ; N , such that
Xi \ Xk 1. Si2I Xi = V . 2. For 8fu; vg 2 E, there exists Xi such that fu; vg Xi. 3. For all i; j; k 2 f1; 2; : : : ; N g, if j lies on the path from i to k in T , then
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 de ned by maxi2f1;2;:::;Ng jXij 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 [
Moreover, we introduce a very useful tree decomposition for some algorithms, called nice tree decomposition. In the sense, it is a special binary tree decomposition.
De nition 2. . A tree decomposition hX ; T i is called nice tree decomposition if it satis es the following: 1. T is rooted at a designated node XN 2 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 jXij = 1. { An introduce node i which has one child j with Xi = Xj [ fvg for a vertex v 2 V . { A Forget node i which has one child j with Xi = Xj n fvg for a vertex v 2 V .
{ A Join node i which has two children j; l 2 X with Xi = Xj = Xl. 2.2
r-Edge Dominating Set We de ne a new problem by extending the notion of domination. We rst de ne distance between two edges e1 = fu1; v1g and e2 = fu2; v2g 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 nding an edge set S E with minimum size such that for every e 2 E n S, d(e; e0) < r holds for some edge e0 2 S. This problem is clearly a generalization of EDS, because 1-EDS is equivalent to EDS. To design a subexponential xedparameter 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 rst prepares k + 1 DP tables for each Xi, so (k + 1) N tables in total. The algorithm runs in the bottom-up manner; it lls 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 lls tables of X1; X2; : : : ; XN in this order.
We further give several assumptions for the tree decomposition. We de ne a mapping g from E to Xi. For an edge e 2 E, there exists at least one bag Xi such that e Xi by the de nition of tree decomposition. We de ne g(e) = Xi where i is the smallest index such that e Xi. By de ning g, we make clear in which node we handle e. Based on g, we partition E into E1; E2; : : : ; EN , where Ei = fe 2 E j g(e) = Xig. We then de ne a subgraph Gi = (Vi; Ei) of G, where Vi = Xi.
Now, we prepare DP tables Ai(r) 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 moment. In table Ai(r), let jVij = ni. Table A(r) consists of ni + 1 columns and i 3ni rows. The rst ni columns represent the statuses of vertices in Gi. The last column represents the value of the corresponding statuses output by the function de ned latter. Each vertex v in Xi has the status c(v) 2 f0; 1; 2g and for each row in Ai(r), we de ne the coloring c = (c(v1); c(v2); ; c(vni )) 2 f0; 1; 2gjVij. We also de ne c(Vi nV 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 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.
We de ne the function fi(r)(c) : f0; 1; 2gjVij ! R [ f 1g for each DP table Ai(r). This function's value represents the total weight of edges dominated by the part of solution until Xi. If fi(c) = 1, it means the coloring c is invalid.
We perform dynamic programming from leaf nodes. First, we start initialization for all leaf node. For each leaf node i, we assume that Xi = fxg and c = c(x). Then, we compute fi(r)(c) as follows: fi(r)(c) := (0 (r = 0 and c 2 f0; 2g) 1 (otherwise) :
Then, we explain update step. Let c0 be the coloring in Xi 1. Update methods are di erent for each node type as follows.
Introduce node (Xi = Xi 1 [ fxg) :
There are following two cases for an introduce node. case 1. c = c0 f0g or c = c0 f2g where c0 = c0(Vi 1) = c(Vi n fxg). case 2. There is a neighbor z of x in Xi 1 such that c = c(Vi n(fzg[fxg)) f1g f1g and c0 = c(Vi 1 n fzg) f2g.
For each case, fi(r)(c) is de ned as follows.
fi(r)(c) := > : 1 ><8fi(r)1(c0) + (c) (case 1) fi(r 1 1)(c0) + (c) (case 2) (otherwise) ; of edges dominated by the coloring c in Xi.
where (c) = P u2f(vui;jvc)(2vEi)i6=0g wuv. The value (c) represents the total weight Forget node (Xi = Xi 1 n fxg) :
For a forget node, we can immediately de ne fi(r)(c) as follows: fi(r)(c) := maxffi(r)1(c f0g); fi(r)1(c f1g)g: 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, we have to compute fi(r) 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 de ne fi(r)(c) as follows: fi(r)(c) :=
f (rj)(c); fl(r rj)(c)g: max f j 0 rj r
Finally, we compute the root node. It is one of the four node type, thus we rstly update DP table following above methods. Then we modify the value fr(c). That is, if there is a vertex v such that c(v) = 2 in coloring c, let f N(r)(c) := 1. Then we output maxr;c f N(r)(c).
Now, we consider the running time of this algorithm. For each leaf node, we can initialize DP tables in O(k)-time since jXij = 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 f0g and c f1g of Xi 1 corresponding to c in Xi. Therefore, the running time of a forget node is O(3! k). In a join node, we search the best combination of Xj and Xl for each fi(r)(c) in O(k)-time. Thus, the running time of a forget node is O(3! k2)-time. Finally, we modify DP table and output maxr;c f N(r)(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 subexponential xed-parameter algorithm.
Theorem 2. There exists a 2O(pk) nO(1)-time algorithm for MaxED on apexminor free graphs.
Let G be an apex-minor-free graph. If tw(G) = O(pk) 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 n I and optimal also for
the problem in G[E n I], and we have tw(G[E n I]) = O(pk). Then, applying
Theorem 1 to G[E nI], 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. [
Let = e1e2 : : : em be an ordering of the edges according to the total weight of the edges dominated by an edge in non-increasing order. For e 2 E, let (e) = Pe02D(e) we0 . In the ordering , (e1) (e2) (em 1) (em); holds. Throughout the section, we assume that E is ordered by , and may use E instead of E to emphasize this. We also denote fe1; e2; : : : ; eig by Ei . We will propose an algorithm that nds not an optimal solution but the lexicographically smallest optimal solution for MaxED, which can make it clear to de ne 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 = fui1 ; ui2 ; : : : ; uik gbe the lexicographically smallest solution for MaxED, where uik = ej for some j. Then, K is a 2-EDS of size k for G[Ej ].
Proof. Show this by contradiction. Assume that a lexicographically smallest solution K of MaxED is not a 2-EDS for G[Ej ]. This implies that there exists an edge ei (1 i j) such that D2(ei) \ K = ;. Let K0 = K n fej g [ feig. Clearly, jK0j = jKj. Since any edge e 2 D(ei) is not dominated by K, we have (K0) (K) (ej ) + (ei) (K); a contradiction.
Lemma 2. Let G be an apex-minor-free graph. If G has an r-EDS of size at most k, tw(G) = O(rpk).
Proof. If G has an r-EDS of size k, then it has (2k; r)-center. Therefore, according
to Lemma 8 of [
Lemma 3. On apex-minor-free graphs, there exists an EPTAS for r-EDS.
Now we are ready to give a subexponential xed-parameter algorithm. First, we sort e1; e2; : : : ; em 2 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[Ej ] does not have a 2-edge dominating set of size at most (1 + )k, let s := j 1, N := N [ fej g, 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 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 N , that is, K E n N . If G[Ej ] has a 2-edge dominating set of size at most (1 + )k, then we nd a subgraph G0 such that tw(G0) = O(pk) and there exists K0 E(G0) satisfying (K) = (K0) for an optimal solution K of G, where jK0j k and jKj k.
Given the parameter (G = (V; E ); k; ; ;) where > 0, the algorithm is described as follows.
Step 1. While there does not exist 2-edge dominating set of size at most (1+ )k for G[Ep], repeat N := N [ fepg, p := p 1.
Step 2. Let I = fe j e 2 N; D(e) N g and E0 = E n I.
tu
tu
Step 3. Find a tree decomposition of G0 = G[E0] using the constant factor
approximation algorithm of Demaine et al. [
Step 4. Apply the algorithm of Theorem 1 to G[E0].
The correctness of the algorithm can be shown by following the proof of
Theorem 1 of [
We analyze the running time of this algorithm. When the loop in Step 2. is
broken out, G[E nN ] 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[E0] because all edges such that e 2 Np\ E0 are adjacent to edges in E n N .
Therefore, tw(G0) = O(3p(1 + )k) = O( k) is shown by Lemma 2. We use the
constant factor approximation algorithm of Demaine et al. [