论文标题
最大边缘可着色子图的参数化复杂性
Parameterized Complexity of Maximum Edge Colorable Subgraph
论文作者
论文摘要
图$ h $是{\ em $ p $ - edge colorable}，如果有颜色$ψ：e（h）\ rightarrow \ {1,2，\ dots，p \} $，以便对于独特的$ uv，vw \ in E（h）$，我们有$ uv，我们有$ uv，我们有$ uv \ neq（uv）\ neq neqψ（vw）。 {\ sc maximum edge-colorable子图}问题作为输入$ g $和integers $ l $和$ p $，目的是找到一个子图$ h $ of $ g $和$ p $ - ed $ h $的$ h $，例如$ | e（h）| \ geq l $。我们从参数化复杂性的角度研究上述问题。我们通过使用{\ sc Integer线性编程}和$（2）$ $ l $进行参数化时获得\ fpt \算法：$（1）$ $ g $的顶点封面封面，通过简化为\ textsc {rainbow匹配}的随机算法，并使用codiNistic algorithmith和diveins and diveins and dive，$（2）$ $ l $，并使用cordingm and dive and cordor和crodity and dive。关于参数$ p+k $，其中$ k $是以下一个：$（1）$解决方案大小，$ l $，$（2）$ $ g $的顶点封面数量，$ g $，$（3）$ $ $ l- {\ mm}（g）$，$ {\ mm}（g）$是$ g $ g $ g $ g $ g $ g $ g $ g $;我们表明，问题的（决策版本）允许使用$ \ MATHCAL {O}（K \ CDOT P）$ VERTICES的内核。此外，我们表明，对于任何$ε> 0 $，除非$ \ np \ np \ np \ subseteq \ conplousy $，否则没有大小$ \ mathcal {o}（k^{1-ε} \ cdot f（p））$的内核。
A graph $H$ is {\em $p$-edge colorable} if there is a coloring $ψ: E(H) \rightarrow \{1,2,\dots,p\}$, such that for distinct $uv, vw \in E(H)$, we have $ψ(uv) \neq ψ(vw)$. The {\sc 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)| \geq 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 {\sc Integer Linear Programming}, and $(2)$ $l$, a randomized algorithm via a reduction to \textsc{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 - {\mm}(G)$, where ${\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-ε} \cdot f(p))$, for any $ε> 0$ and computable function $f$, unless $\NP \subseteq \CONPpoly$.
