Abstract
We develop an O(n 3) algorithm for deciding if an n-vertex digraph has a subset of vertices with the property that each vertex of the graph has an even number of arcs into the subset. This algorithm allows us to give a combinatorial interpretation of Gauss-Jordan and Gauss elimination on square boolean matrices. In addition to solving this independence-mod-2 (even) set existence problem we also give efficient algorithms for related domination-mod-2 (odd) set existence problems on digraphs. However, for each of the four combinations of these two properties we show that even though the existence problem on digraphs is tractable, the problems of deciding the existence of a set of size exactly k, larger than k, or smaller than k, for a given k, are all NP-complete for undirected graphs.
Research support in part by Czech research grants GAUK 194/1996 and 158/1999, and GAĆR 201/1996/0194
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
E. Berlekamp, R.J. McEliece and H.C.A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory. Vol.29, No.3, 1978, 384–386. 106
M. Halldórsson, unpublished. 101
M. Halldórsson, J. Kratochv’il and J.A. Telle, Independent sets with domination constraints, Proceedings ICALP’98-25th International Colloquium on Automata, Languages and Programming, Aalborg, Denmark, July 1998, LNCS vol. 1443, 176–187 101, 109
M. Mahajan and V. Vinay, Determinant: combinatorics, algorithms, complexity, Chicago Journal of Theoretical Computer Science, 1997:5, 1997. Preliminary version SODA’97.
M. Mahajan and V. Vinay, Determinant: Old Algorithms, New Insights, in Proceedings SWAT’98-6th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, July 1998, LNCS Vol. 1432, 276–287. 102
S.C. Ntafos and S.L. Hakimi, On the complexity of some coding problems, IEEE Trans. Inform. Theory, Vol. 27, 1981, 794–796. 106
J.A. Telle, Characterization of domination-type parameters in graphs, Proceedings of 24th Southeastern International Conference on Combinatorics, Graph Theory and Computing-Congressus Numerantium Vol.94 1993, 9–16. 101
J.A. Telle, Complexity of domination-type problems in graphs, Nordic Journal of Computing 1(1994), 157–171. 109
A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory. Vol.43 No. 6, 1997, 1757–1766. Preliminary version STOC’97. 106
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Halldórsson, M.M., Kratochvíl, J., Telle, J.A. (1999). Mod-2 Independence and Domination in Graphs. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds) Graph-Theoretic Concepts in Computer Science. WG 1999. Lecture Notes in Computer Science, vol 1665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46784-X_11
Download citation
DOI: https://doi.org/10.1007/3-540-46784-X_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66731-5
Online ISBN: 978-3-540-46784-7
eBook Packages: Springer Book Archive