Abstract
We introduce a graph-theoretic dissolution model that applies to a number of redistribution scenarios such as gerrymandering in political districting or work balancing in an online situation. The central aspect of our model is the deletion of certain vertices and the redistribution of their loads to neighboring vertices in a perfectly balanced way.
We investigate how the underlying graph structure, the pre-knowledge of which vertices should be deleted, and the relation between old and new vertex loads influence the computational complexity of the underlying graph problems. Our results establish a clear borderline between tractable and intractable cases.
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.
Similar content being viewed by others
References
Altman, M.: Districting Principles and Democratic Representation. PhD thesis, California Institute of Technology (1998)
Berman, F., Johnson, D., Leighton, T., Shor, P.W., Snyder, L.: Generalized planar matching. Journal of Algorithms 11(2), 153–184 (1990)
van Bevern, R., Bredereck, R., Bulteau, L., Chen, J., Froese, V., Niedermeier, R., Woeginger, G.J.: Star partitions of perfect graphs. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 174–185. Springer, Heidelberg (2014)
Duque, J.C.: Design of Homogeneous Territorial Units: A Methodological Proposal and Applications. PhD thesis, University of Barcelona (2004)
Duque, J.C., Ramos, R., Surinach, J.: Supervised regionalization methods: A survey. International Regional Science Review 30(3), 195–220 (2007)
Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman (1979)
Hell, P., Kirkpatrick, D.G., Kratochvíl, J., Kríz, I.: On restricted two-factors. SIAM Journal on Discrete Mathematics 1(4), 472–484 (1988)
Landau, Z., Su, F.: Fair division and redistricting. Social Choice and Welfare 32(3), 479–492 (2009)
Maravalle, M., Simeone, B.: A spanning tree heuristic for regional clustering. Communications in Statistics—Theory and Methods 24(3), 625–639 (1995)
Mehrota, A., Johnson, E.L., Nemhauser, G.L.: An optimization based heuristic for political districting. Management Science 44(8), 1100–1114 (1998)
Puppe, C., Tasnádi, A.: A computational approach to unbiased districting. Mathematical and Computer Modelling 48, 1455–1460 (2008)
Puppe, C., Tasnádi, A.: Optimal redistricting under geographical constraints: Why “pack and crack” does not work. Economics Letters 105(1), 93–96 (2009)
Vassilevska Williams, V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proc. 44th STOC, pp. 887–898. ACM (2012)
Yuster, R.: Combinatorial and computational aspects of graph packing and graph decomposition. Computer Science Review 1(1), 12–26 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Bevern, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., Woeginger, G.J. (2014). Network-Based Dissolution. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44465-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-662-44465-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44464-1
Online ISBN: 978-3-662-44465-8
eBook Packages: Computer ScienceComputer Science (R0)