×

On bounded block decomposition problems for under-specified systems of equations. (English) Zbl 1237.68096

Summary: When solving a system of equations, it can be beneficial not to solve it in its entirety at once, but rather to decompose it into smaller subsystems that can be solved in order. Based on a bisimplicial graph representation we analyze the parameterized complexity of two problems central to such a decomposition: The Free Square Block problem related to finding smallest subsystems that can be solved separately, and the Bounded Block Decomposition problem related to determining a decomposition where the largest subsystem is as small as possible. We show both problems to be W[1]-hard. Finally we relate these problems to crown structures and settle two open questions regarding them using our results.

MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Software:

GPDOF
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Wilczkowiak, M.; Trombettoni, G.; Jermann, C.; Sturm, P.; Boyer, E., Scene modeling based on constraint system decomposition techniques, (Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV 2003), vol. 2 (2003), IEEE Computer Society: IEEE Computer Society Los Alamitos), 1004-1010
[2] S. Ait-Aoudia, R. Jegou, D. Michelucci, Reduction of constraint systems, in: Proceedings of Compugraphics 1993, 1993, pp. 83-92.; S. Ait-Aoudia, R. Jegou, D. Michelucci, Reduction of constraint systems, in: Proceedings of Compugraphics 1993, 1993, pp. 83-92.
[3] Lovász, L.; Plummer, M. D., Matching Theory (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001
[4] Asratian, A. S.; Denley, T. M.J.; Häggkvist, R., Bipartite Graphs and Their Applications (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0914.05049
[5] Dulmage, A. L.; Mendelsohn, N. S., Coverings of bipartite graphs, Canad. J. Math., 10, 517-534 (1958) · Zbl 0091.37404
[6] Dulmage, A. L.; Mendelsohn, N. S., On the inversion of sparse matrices, Math. Comp., 16, 80, 494-496 (1962) · Zbl 0115.11301
[7] Pothen, A.; Fan, C.-J., Computing the block triangular form of a sparse matrix, ACM Trans. Math. Software, 16, 4, 303-324 (1990) · Zbl 0900.65117
[8] Bliek, C.; Neveu, B.; Trombettoni, G., Using graph decomposition for solving continuous csps, (Maher, M.; Puget, J.-F., Principles and Practice of Constraint Programming? - CP98. Principles and Practice of Constraint Programming? - CP98, Lecture Notes in Comput. Sci., vol. 1520 (1998), Springer: Springer Berlin), 102-116
[9] Hall, P., On representatives of subsets, J. London Math. Soc., 10, 1, 26-30 (1935) · Zbl 0010.34503
[10] Mann, H. B.; Ryser, H. J., Systems of distinct representatives, Amer. Math. Monthly, 60, 6, 397-401 (1953) · Zbl 0050.05103
[11] Chen, J.; Kanj, I. A., Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms, J. Comput. System Sci., 67, 4, 833-847 (2003) · Zbl 1091.68076
[12] Chlebík, M.; Chlebíková, J., Crown reductions for the minimum weighted vertex cover problem, Discrete Appl. Math., 156, 3, 292-312 (2008) · Zbl 1132.68071
[13] Jermann, C.; Trombettoni, G.; Neveu, B.; Mathis, P., Decomposition of geometric constraint systems: a survey, Internat. J. Comput. Geom. Appl., 16, 5-6, 379-414 (2006) · Zbl 1104.65304
[14] A. Lomonosov, Graph and combinatorial algorithms for geometric constraint solving, PhD thesis, University of Florida, Gainesville, 2004.; A. Lomonosov, Graph and combinatorial algorithms for geometric constraint solving, PhD thesis, University of Florida, Gainesville, 2004.
[15] Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0914.68076
[16] Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness II: On completeness for \(W [1]\), Theoret. Comput. Sci., 141, 1-2, 109-131 (1995) · Zbl 0873.68059
[17] Downey, R. G.; Fellows, M. R., Fixed-parameter intractability, (Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992 (1992), IEEE Computer Society: IEEE Computer Society Boston), 36-49
[18] Chor, B.; Fellows, M.; Juedes, D., Linear kernels in linear time, or how to save \(k\) colors in \(O(n^2)\) steps, (Hromkovic, J.; Nagl, M.; Westfechtel, B., Proceedings of WG 2004. Proceedings of WG 2004, Lecture Notes in Comput. Sci., vol. 3353 (2005), Springer: Springer Berlin), 257-269 · Zbl 1112.68412
[19] F.N. Abu-Khzam, R.L. Collins, M.R. Fellows, M.A. Langston, W.H. Suters, C.T. Symons, Kernelization algorithms for the vertex cover problem: Theory and experiments, in: L. Arge, G.F. Italiano, R. Sedgewick (Eds.), Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2004), 2004, pp. 62-69.; F.N. Abu-Khzam, R.L. Collins, M.R. Fellows, M.A. Langston, W.H. Suters, C.T. Symons, Kernelization algorithms for the vertex cover problem: Theory and experiments, in: L. Arge, G.F. Italiano, R. Sedgewick (Eds.), Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2004), 2004, pp. 62-69.
[20] Abu-Khzam, F. N.; Fellows, M. R.; Langston, M. A.; Suters, W. H., Crown structures for vertex cover kernelization, Theory Comput. Syst., 41, 3, 411-430 (2007) · Zbl 1148.68035
[21] C. Sloper, Techniques in parameterized algorithm design, PhD thesis, The University of Bergen, Norway, 2006.; C. Sloper, Techniques in parameterized algorithm design, PhD thesis, The University of Bergen, Norway, 2006. · Zbl 1154.68561
[22] Abrahamson, K. A.; Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness IV: On completeness for \(W [P]\) and PSPACE analogues, Ann. Pure Appl. Logic, 73, 3, 235-276 (1995) · Zbl 0828.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.