.png){kind=icon}
返回
Almost Consistent Systems of Linear Equations
.png){kind=icon}
PRE
AI
DOI：10.1145/3733107.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
检查一个线性方程组是否相容是一个具有广泛应用的基本计算问题。在处理不相容系统时，人们可能寻求一个赋值以最小化不满足方程的数量。即使对于二元方程在二元域上的情况，该问题也难以在任意常数因子内进行近似（NP-hard且UGC-hard）。我们从参数化复杂度的角度研究此问题，参数为不满足方程的数量。我们考虑定义在具有特定Helly性质的交换环族（即无零因子环）上的方程。该集合包含，例如，有限和无限域、整数环以及系数来自域的一元多项式环；更一般地，它包含重要的Prüfer环类。我们证明，如果每个方程最多包含两个变量，则该问题是固定参数可解的。这推广了许多著名的图分离问题（如Bipartization、Multiway Cut和Multicut），这些问题均以割集大小为参数。作为补充，我们证明当方程允许三个或更多变量时，该问题是W[1]-hard的，同样适用于许多未被我们的FPT结果涵盖的交换环。在技术层面，我们引入重要平衡子图的概念，将Marx的重要分离器推广到偏置图的设置中。此外，我们利用Kim、Kratsch、Pilipczuk和Wahlström关于参数化MinCSP的最新结果，高效求解具有析取割请求的Multicut推广问题。
Keyword:
parameterized complexity
linear equations
biased graphs
minimum constraint satisfaction (MinCSP)
graph separation
期刊
A
IF:
1.4
论文数:
43
被引数:
1.1K
机构
引用论文
On Group Feedback Vertex Set Parameterized by the Size of the Cutset关于按割集大小参数化的群反馈顶点集.png)
Algorithmica
AlgorithmicaIF0
PREAI
分享收藏分享收藏
查看更多内容