Abstract
The problem MaxLin2 can be stated as follows. We are given a system S of m equations in variables x 1,…,x n , where each equation \(\sum_{i \in I_{j}}x_{i} = b_{j}\) is assigned a positive integral weight w j and \(b_{j} \in\mathbb{F}_{2}\), I j ⊆{1,2,…,n} for j=1,…,m. We are required to find an assignment of values in \(\mathbb{F}_{2}\) to the variables in order to maximize the total weight of the satisfied equations.
Let W be the total weight of all equations in S. We consider the following parameterized version of MaxLin2: decide whether there is an assignment satisfying equations of total weight at least W−k, where k is a nonnegative parameter. We prove that this parameterized problem is W[1]-hard even if each equation of S has exactly three variables and every variable appears in exactly three equations and, moreover, each weight w j equals 1 and no two equations have the same left-hand side. We show the tightness of this result by proving that if each equation has at most two variables then the parameterized problem is fixed-parameter tractable. We also prove that if no variable appears in more than two equations then we can maximize the total weight of satisfied equations in polynomial time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
AA stands for Above Average.
For the number of equations only an exponential upper bound was obtained and the existence of a polynomial upper bound remains an open problem [3].
References
Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica 61(3), 638–655 (2011)
Alon, N., Gutin, G., Krivelevich, M.: Algorithms with large domination ratio. J. Algorithms 50, 118–131 (2004)
Crowston, R., Fellows, M., Gutin, G., Jones, M., Rosamond, F., Thomassé, S., Yeo, A.: Simultaneously satisfying linear equations over \(\mathbb {F}_{2}\): MaxLin2 and Max-r-Lin2 parameterized above average. In: Proc. FSTTCS 2011, pp. 229–240 (2011)
Crowston, R., Gutin, G., Jones, M., Kim, E.J., Ruzsa, I.: Systems of linear equations over \(\mathbb{F}_{2}\) and problems parameterized above average. In: SWAT 2010. Lect. Notes Comput. Sci., vol. 6139, pp. 164–175 (2010)
Crowston, R., Gutin, G., Jones, M., Raman, V., Saurabh, S.: Parameterized complexity of MaxSat above average. In: Proc. LATIN 2012. Lect. Notes Comput. Sci., vol. 7256, pp. 184–194 (2012)
Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. In: Proc. IPEC 2011. Lect. Notes Comput. Sci., vol. 7112, pp. 1–12 (2011)
Downey, R.G., Fellows, M.R., Vardy, A., Whittle, G.: The parameterized complexity of some fundamental problems in coding theory. SIAM J. Comput. 29(2), 545–570 (1999)
Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386–1396 (2006)
Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: A probabilistic approach to problems parameterized above or below tight bounds. J. Comput. Syst. Sci. 77, 422–429 (2011)
Håstad, J.: Some optimal inapproximability results. J. ACM 48, 798–859 (2001)
Kim, E.J., Williams, R.: Improved parameterized algorithms for above average constraint satisfaction. In: Proc. IPEC 2011. Lect. Notes Comput. Sci., vol. 7112, pp. 118–131 (2011)
Kratsch, S., Wahlström, M.: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. In: Proc. SODA 2012, pp. 94–103 (2012)
Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. Preprint. arXiv:1203.0833v2 [cs.DS]
Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137–153 (2009)
Rafiey, A.: Private Communication (2011)
Raman, V., Ramanujan, M.S., Saurabh, S.: Paths, flowers and vertex cover. In: Proc. ESA 2011. Lect. Notes Comput. Sci., vol. 6942, pp. 382–393 (2011)
Razgon, I., O’Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435–450 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Crowston, R., Gutin, G., Jones, M. et al. Parameterized Complexity of Satisfying Almost All Linear Equations over \(\mathbb{F}_{2}\) . Theory Comput Syst 52, 719–728 (2013). https://doi.org/10.1007/s00224-012-9415-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-012-9415-2