论文标题
关于负载着色的结构参数化
On Structural Parameterizations of Load Coloring
论文作者
论文摘要
给定图形$ g $和一个积极的整数$ k $，2载的着色问题是检查是否存在$ 2 $ - 颜色$ f：v（g）\ rightarrow \ rightarrow \ {r，b \} $ of $ g $的$ g $，以使每个$ i \ in \ i \ in \ i f in \ {r，b \} $，至少与$ k $ i $ i $ i $ i i $ i i i $ i i $众所周知，即使在常规图（如常规图）等特殊类别上，该问题也是NP完整的。 Gutin and Jones（INF流程Lett 114：446-449，2014）表明，通过给出最多$ 7K $的顶点的内核，该问题是固定参数可处理的。 Barbero等。 （Algorithmica 79：211-229，2017）获得了一个不到$ 4K $的顶点和$ O（k）$边缘的内核，从而改善了较早的结果。 在本文中，我们研究了有关结构图参数的参数化复杂性。我们表明\ lcp {}不能在时间$ f（w）n^{o（w）} $中解决，除非ETH失败，并且可以在时间$ n^{o（w）} $中解决，其中$ n $是输入图的大小，$ w $是图形和$ f $ $ f $ $ f $是$ w $ w $ w $ w $ w $ w $ w $。接下来，我们考虑参数到集群图的距离，与共簇图的距离以及与阈值图的距离，这些距离比参数clique宽度弱，并表明相对于这些参数，问题是固定参数可拖动（FPT）。最后，我们证明\ lcp {}即使在两部分图和拆分图上也是np complete。
Given a graph $G$ and a positive integer $k$, the 2-Load coloring problem is to check whether there is a $2$-coloring $f:V(G) \rightarrow \{r,b\}$ of $G$ such that for every $i \in \{r,b\}$, there are at least $k$ edges with both end vertices colored $i$. It is known that the problem is NP-complete even on special classes of graphs like regular graphs. Gutin and Jones (Inf Process Lett 114:446-449, 2014) showed that the problem is fixed-parameter tractable by giving a kernel with at most $7k$ vertices. Barbero et al. (Algorithmica 79:211-229, 2017) obtained a kernel with less than $4k$ vertices and $O(k)$ edges, improving the earlier result. In this paper, we study the parameterized complexity of the problem with respect to structural graph parameters. We show that \lcp{} cannot be solved in time $f(w)n^{o(w)}$, unless ETH fails and it can be solved in time $n^{O(w)}$, where $n$ is the size of the input graph, $w$ is the clique-width of the graph and $f$ is an arbitrary function of $w$. Next, we consider the parameters distance to cluster graphs, distance to co-cluster graphs and distance to threshold graphs, which are weaker than the parameter clique-width and show that the problem is fixed-parameter tractable (FPT) with respect to these parameters. Finally, we show that \lcp{} is NP-complete even on bipartite graphs and split graphs.
