论文标题
奇数路径，循环和$ t $ -joins：连接和算法
Odd Paths, Cycles and $T$-joins: Connections and Algorithms
论文作者
论文摘要
最大程度地减少了满足均衡限制的边缘设置的重量，这是组合优化的一个挑战性分支，这是亚历山大·施里杰弗（Alexander Schrijver）的二进制超刻章章节所见证的。 we prove that the Shortest Odd Path problem in undirected graphs without cycles of negative total weight and several related problems are NP-hard, settling a long-standing open question asked by Lovász (Open Problem 27 in Schrijver's book ``Combinatorial Optimization''). On the other hand, we provide an efficient algorithm to the closely related and well-studied Minimum-weight Odd $T$-Join problem for non-negative权重：我们的算法以$ c $参数的fpt时间运行，其中$ c $是某些有效计算的最小计算成分的数量还考虑了多项式时间的求解。
Minimizing the weight of an edge set satisfying parity constraints is a challenging branch of combinatorial optimization as witnessed by the binary hypergraph chapter of Alexander Schrijver's book ``Combinatorial Optimization" (Chapter 80). This area contains relevant graph theory problems including open cases of the Max Cut problem and some multiflow problems. We clarify the interconnections between some of these problems and establish three levels of difficulties. On the one hand, we prove that the Shortest Odd Path problem in undirected graphs without cycles of negative total weight and several related problems are NP-hard, settling a long-standing open question asked by Lovász (Open Problem 27 in Schrijver's book ``Combinatorial Optimization''). On the other hand, we provide an efficient algorithm to the closely related and well-studied Minimum-weight Odd $T$-Join problem for non-negative weights: our algorithm runs in FPT time parameterized by $c$, where $c$ is the number of connected components in some efficiently computed minimum-weight $T$-join. If negative weights are also allowed, then finding a minimum-weight odd $\{s,t\}$-join is equivalent to the Minimum-weight Odd $T$-Join problem for arbitrary weights, whose complexity is still only conjectured to be polynomial-time solvable. The analogous problems for digraphs are also considered.
