论文标题
关于查找大型奇数诱导子图和奇数色的复杂性
On the complexity of finding large odd induced subgraphs and odd colorings
论文作者
论文摘要
我们研究了查找问题的复杂性，鉴于图形$ g $，最大的$ g $ $ g $，所有学位奇数（称为奇数子图），以及最少的奇数子图，该分区$ v（g）$。我们称这些参数为$ {\ sf mos}（g）$和$χ_ {\ sf Odd}（g）$。我们证明，如果$ q \ q \ leq 2 $，则决定$χ_ {\ sf Odd}（g）\ leq Q $是否可以解决多项式时间，否则np complete。我们在时间中提供算法$ 2^{o（{\ sf rw}）} \ cdot n^{o（1）} $和$ 2^{o（q \ cdot {\ cdot {\ sf rw}）} \ cdot n^{o（1）} $ to Complo odd}（g）\ leq q $在$ n $ -vertex上分别是$ {\ sf rw} $的排名宽度，我们证明对等级宽度的依赖性在ETH下是渐近的最佳选择。最后，我们在受限的图类类或与其他参数有关的这些参数上给出了一些紧密的界限。
We study the complexity of the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters ${\sf mos}(G)$ and $χ_{\sf odd}(G)$, respectively. We prove that deciding whether $χ_{\sf odd}(G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise. We provide algorithms in time $2^{O({\sf rw})} \cdot n^{O(1)}$ and $2^{O(q \cdot {\sf rw})} \cdot n^{O(1)}$ to compute ${\sf mos}(G)$ and to decide whether $χ_{\sf odd}(G) \leq q$ on $n$-vertex graphs of rank-width at most ${\sf rw}$, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.
