论文标题
线性方程的几乎一致的系统
Almost Consistent Systems of Linear Equations
论文作者
论文摘要
检查线性方程系统是否一致是无处不在的应用程序的基本计算问题。在处理不一致的系统时，可能会寻求一项任务，以最大程度地减少不满意的方程数量。这个问题是即使对于两元素字段的两变量方程，即使在任何常数内，NP- hard和ugc- hard都可以在任何常数内近似。我们从参数化复杂性的角度研究了这个问题，参数为不满意的方程数。我们考虑在欧几里得领域定义的方程式 - 一个概括有限和无限领域的通勤环家族，包括理性，整数和许多其他结构。我们表明，如果每个方程都包含大多数两个变量，则该问题是固定参数可进行的。这概括了许多显着的图形分离问题，例如两次化，多路切割和通过切割的大小进行了参数化。为了补充这一点，我们表明，当方程中允许三个或更多变量以及许多不是欧几里得域的交换环时，问题是W [1] - hard。在技术方面，我们介绍了重要的平衡子图的概念，从而概括了马克思的重要分离器[Theor。计算。科学。 2006]到偏置图的设置。此外，我们对参数化的MINCSP [Kim等人，SODA 2021]使用最新结果，以有效地解决了具有分离的切割请求的多形概括。
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains - a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers, and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests.
