=Paper=
{{Paper
|id=Vol-1326/031-Hanaka
|storemode=property
|title=A Fixed-Parameter Algorithm for Max Edge Domination
|pdfUrl=https://ceur-ws.org/Vol-1326/031-Hanaka.pdf
|volume=Vol-1326
|dblpUrl=https://dblp.org/rec/conf/sofsem/HanakaO15
}}
==A Fixed-Parameter Algorithm for Max Edge Domination==
https://ceur-ws.org/Vol-1326/031-Hanaka.pdf
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)