Name
Abstract | ||
|---|---|---|
A graph H is p-edge colorable if there is a coloring
$$\psi : E(H) \rightarrow \{1,2,\dots ,p\}$$
, such that for distinct
$$uv, vw \in E(H)$$
, we have
$$\psi (uv) \ne \psi (vw)$$
. The Maximum Edge-Colorable Subgraph problem takes as input a graph G and integers l and p, and the objective is to find a subgraph H of G and a p-edge-coloring of H, such that
$$|E(H)| \ge l$$
. We study the above problem from the viewpoint of Parameterized Complexity. We obtain FPT algorithms when parameterized by: (1) the vertex cover number of G, by using Integer Linear Programming, and (2) l, a randomized algorithm via a reduction to Rainbow Matching, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters
$$p+k$$
, where k is one of the following: (1) the solution size, l, (2) the vertex cover number of G, and (3)
$$l - {\texttt {mm}}(G)$$
, where
$${\texttt {mm}}(G)$$
is the size of a maximum matching in G; we show that the (decision version of the) problem admits a kernel with
$${\mathcal {O}}(k \cdot p)$$
vertices. Furthermore, we show that there is no kernel of size
$${\mathcal {O}}(k^{1-\epsilon } \cdot f(p))$$
, for any
$$\epsilon > 0$$
and computable function f, unless
$${\textsf {NP}}\subseteq \textsf {coNP/poly}$$
.
|
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s00453-022-01003-0 | Algorithmica |
Keywords | DocType | Volume |
Edge Coloring, Kernelization, FPT Algorithms, Kernel Lower Bound | Journal | 84 |
Issue | ISSN | Citations |
10 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 7 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Agrawal Akanksha | 1 | 0 | 0.34 |
| Kundu Madhumita | 2 | 0 | 0.34 |
| Sahu Abhishek | 3 | 0 | 0.34 |
| Saket Saurabh | 4 | 2023 | 179.50 |
| Tale Prafullkumar | 5 | 0 | 0.34 |