×

Separator-based data reduction for signed graph balancing. (English) Zbl 1206.90201

Summary: Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.

MSC:

90C35 Programming involving graphs or networks
05C15 Coloring of graphs and hypergraphs

Software:

PANTHER; GLPK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abu-Khzam FN, Collins RL, Fellows MR, Langston MA, Suters WH, Symons CT (2004) Kernelization algorithms for the vertex cover problem: Theory and experiments. In: Proceedings of the 6th workshop on algorithm engineering and experiments (ALENEX ’04). SIAM, pp 62–69
[2] Abu-Khzam FN, Fellows MR, Langston MA, Suters WH (2007) Crown structures for vertex cover kernelization. Theory Comput Syst 41(3):411–430 · Zbl 1148.68035 · doi:10.1007/s00224-007-1328-0
[3] Agarwal A, Charikar M, Makarychev K, Makarychev Y (2005) \(O(\sqrt{\log n})\) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. In: Proceedings of the 37th ACM symposium on theory of computing (STOC ’05). ACM, pp 573–581 · Zbl 1192.68864
[4] Antal T, Krapivsky PL, Redner S (2006) Social balance on networks: The dynamics of friendship and enmity. Physica D: Nonlinear Phenom 224(1–2):130–136 · Zbl 1130.91041 · doi:10.1016/j.physd.2006.09.028
[5] Avidor A, Langberg M (2007) The multi-multiway cut problem. Theor Comput Sci 377(1–3):35–42 · Zbl 1115.68171 · doi:10.1016/j.tcs.2007.02.026
[6] Barahona F (1980) On the complexity of max cut. Tech Rep 186, IMAG, Université Joseph Fourier, Grenoble, France
[7] Barahona F (1982) On the computational complexity of Ising spin glass models. J Phys A: Math Gen 15(10):3241–3253 · doi:10.1088/0305-4470/15/10/028
[8] Barahona F, Ridha Mahjoub A (1989) Facets of the balanced (acyclic) induced subgraph polytope. Math Program 45(1–3):21–33 · Zbl 0675.90071 · doi:10.1007/BF01589094
[9] Barvinok AI, Woods K (2003) Short rational generating functions for lattice point problems. J Am Math Soc 16(4):957–979 · Zbl 1017.05008 · doi:10.1090/S0894-0347-03-00428-4
[10] Bodlaender HL, Koster AMCA (2008) Combinatorial optimization on graphs of bounded treewidth. Comput J 51:255–269 · Zbl 05534220 · doi:10.1093/comjnl/bxm037
[11] Boginski V, Butenko S, Pardalos PM (2005) Statistical analysis of financial networks. Comput Stat Data Anal 48(2):431–443 · Zbl 1429.62460 · doi:10.1016/j.csda.2004.02.004
[12] Boginski V, Butenko S, Pardalos PM (2006) Mining market data: A network approach. Comput Oper Res 33(11):3171–3184 · Zbl 1113.90079 · doi:10.1016/j.cor.2005.01.027
[13] Boros E, Hammer PL (1991) The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Ann Oper Res 33(3):151–180 · Zbl 0741.90077 · doi:10.1007/BF02115753
[14] Chen J, Kanj IA, Jia W (2001) Vertex cover: Further observations and further improvements. J Algorithms 41(2):280–301 · Zbl 1017.68087 · doi:10.1006/jagm.2001.1186
[15] Chiang C, Kahng AB, Sinha S, Xu X, Zelikovsky AZ (2007) Fast and efficient bright-field AAPSM conflict detection and correction. IEEE Trans Comput-Aided Des Integr Circ Syst 26(1):115–126 · Zbl 05450384 · doi:10.1109/TCAD.2006.882642
[16] Coleman T, Saunderson J, Wirth A (2008) A local-search 2-approximation for 2-correlation-clustering. In: Proceedings of the 16th annual European symposium on algorithms (ESA ’08). LNCS, vol 5193. Springer, Berlin, pp 308–319 · Zbl 1158.68549
[17] DasGupta B, Enciso GA, Sontag ED, Zhang Y (2007) Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. Biosystems 90(1):161–178 · doi:10.1016/j.biosystems.2006.08.001
[18] Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin
[19] Estivill-Castro V, Fellows MR, Langston MA, Rosamond FA (2006) FPT is P-time extremal structure I. In: Proceedings of the 1st algorithms and complexity in Durham workshop (ACiD ’06). Texts in Algorithmics, vol 4. College Publications, pp 1–41
[20] Feist AM, Scholten JCM, Palsson BØ, Brockman FJ, Ideker T (2006) Modeling methanogenesis with a genome-scale metabolic reconstruction of Methanosarcina barkeri. Mol Syst Biol 2:2006 .0004 · doi:10.1038/msb4100046
[21] Fellows MR, Langston MA (1989) An analogue of the Myhill–Nerode theorem and its use in computing finite-basis characterizations. In: Proceedings of the 30th annual IEEE symposium on foundations of computer science (FOCS ’89). IEEE, pp 520–525
[22] Flum J, Grohe M (2006) Parameterized complexity theory. Springer, Berlin · Zbl 1143.68016
[23] Gabow HN (2000) Path-based depth-first search for strong and biconnected components. Inf Process Lett 74(3–4):107–114 · Zbl 1339.68301 · doi:10.1016/S0020-0190(00)00051-X
[24] Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115–1145 · Zbl 0885.68088 · doi:10.1145/227683.227684
[25] Grötschel M, Pulleyblank WR (1981) Weakly bipartite graphs and the max-cut problem. Oper Res Lett 1(1):23–27 · Zbl 0494.90078 · doi:10.1016/0167-6377(81)90020-1
[26] Guo J, Niedermeier R (2007) Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1):31–45 · doi:10.1145/1233481.1233493
[27] Guo J, Hüffner F, Niedermeier R (2004) A structural view on parameterizing problems: Distance from triviality. In: Proceedings of the 1st international workshop on parameterized and exact computation (IWPEC ’04). LNCS, vol 3162. Springer, Berlin, pp 162–173 · Zbl 1104.68050
[28] Guo J, Gramm J, Hüffner F, Niedermeier R, Wernicke S (2006) Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J Comput Syst Sci 72(8):1386–1396 · Zbl 1119.68134 · doi:10.1016/j.jcss.2006.02.001
[29] Guo J, Moser H, Niedermeier R (2008) Iterative compression for exactly solving NP-hard minimization problems. In: Proceedings of the DFG SPP 1126 ”algorithmics of large and complex networks”. LNCS. Springer, Berlin, to appear · Zbl 1248.68380
[30] Gutwenger C, Mutzel P (2000) A linear time implementation of SPQR-trees. In: Proceedings of the 8th international symposium on graph drawing (GD ’00). LNCS, vol 1984. Springer, Berlin, pp 77–90 · Zbl 1043.68621
[31] Harary F (1953) On the notion of balance of a signed graph. Michigan Math J 2(2):143–146 · Zbl 0056.42103 · doi:10.1307/mmj/1028989917
[32] Harary F (1959) On the measurement of structural balance. Behav Sci 4(4):316–323 · doi:10.1002/bs.3830040405
[33] Harary F, Lim MH, Wunsch DC (2002) Signed graphs for portfolio analysis in risk management. IMA J Manag Math 13(3):201–210 · Zbl 1065.91025 · doi:10.1093/imaman/13.3.201
[34] Henzinger MR, Rao S, Gabow HN (2000) Computing vertex connectivity: New bounds from old techniques. J Algorithms 43(2):222–250 · Zbl 0951.68108 · doi:10.1006/jagm.1999.1055
[35] Hicks IV, Koster AMCA, Kolotoğlu E (2005) Branch and tree decomposition techniques for discrete optimization. In: TutORials 2005, tutorials in operations research, INFORMS, pp 1–29
[36] Hopcroft JE, Tarjan RE (1973) Dividing a graph into triconnected components. SIAM J Comput 2(3):135–158 · Zbl 0281.05111 · doi:10.1137/0202012
[37] Hüffner F (2005) Algorithm engineering for optimal graph bipartization. In: Proceedings of the 4th international workshop on experimental and efficient algorithms (WEA ’05). LNCS, vol 3503. Springer, Berlin, pp 240–252. Extended version to appear in J Graph Algorithms Appl · Zbl 1121.68459
[38] Hüffner F (2007) Algorithms and experiments for parameterized approaches to hard graph problems. PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena · Zbl 1250.05107
[39] Hüffner F, Komusiewicz C, Moser H, Niedermeier R (2008) Fixed-parameter algorithms for cluster vertex deletion. In: Proceedings of the 8th Latin American theoretical informatics symposium (LATIN ’08). LNCS, vol 4598. Springer, Berlin, pp 711–722. Extended version to appear in Theory Comput Syst · Zbl 1136.68465
[40] Khot S (2002) On the power of unique 2-prover 1-round games. In: Proceedings of the 34th ACM symposium on theory of computing (STOC ’02). ACM, pp 767–775 · Zbl 1192.68367
[41] Konig D (1936) Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig, English translation: Theory of finite and infinite graphs, Birkhäuser, 1990
[42] Leroy X, Vouillon J, Doligez D et al (1996) The objective caml system. Available on the web, http://caml.inria.fr/ocaml/
[43] Makhorin A (2004) GNU linear programming kit reference manual version 4.8. Department of Applied Informatics, Moscow Aviation Institute
[44] Mi H, Lazareva-Ulitsky B, Loo R, Kejariwal A, Vandergriff J, Rabkin S, Guo N, Muruganujan A, Doremieux O, Campbell MJ, Kitano H, Thomas PD (2005) The PANTHER database of protein families, subfamilies, functions and pathways. Nucleic Acids Res 33(Supplement 1):284–288
[45] Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press, Oxford · Zbl 1095.68038
[46] Oda K, Kitano H (2006) A comprehensive map of the toll-like receptor signaling network. Mol Syst Biol 2:2006.0015 · doi:10.1038/msb4100057
[47] Oda K, Kimura T, Matsuoka Y, Funahashi A, Muramatsu M, Kitano H (2004) Molecular interaction map of a macrophage. AfCS Res Rep 2:14
[48] Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43(3):425–440 · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X
[49] Polzin T, Vahdati Daneshmand S (2006) Practical partitioning-based methods for the Steiner problem. In: Proceedings of the 4th international workshop on experimental and efficient algorithms (WEA ’06). LNCS, vol 4007. Springer, Berlin, pp 241–252 · Zbl 1196.68236
[50] Razgon I, O’Sullivan B (2008) Almost 2-SAT is fixed-parameter tractable. In: Proceedings of the 35th international colloquium on automata, languages and programming (ICALP ’08). LNCS, vol 5125. Springer, Berlin, pp 551–562 · Zbl 1153.68397
[51] Reed B, Smith K, Vetta A (2004) Finding odd cycle transversals. Oper Res Lett 32(4):299–301 · Zbl 1052.05061 · doi:10.1016/j.orl.2003.10.009
[52] Sturmfels B (1996) Gröbner bases and convex polytopes. University lecture series, vol 8. American Mathematical Society, Providence · Zbl 0856.13020
[53] Thagard P, Verbeurgt K (1998) Coherence as constraint satisfaction. Cogn Sci 22(1):1–24 · Zbl 05396065 · doi:10.1207/s15516709cog2201_1
[54] Volz E (2004) Random networks with tunable degree distribution and clustering. Phys Rev E 70(5):056115 · doi:10.1103/PhysRevE.70.056115
[55] Wernicke S (2003) On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems. Diplomarbeit, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen
[56] Yannakakis M (1981) Edge-deletion problems. SIAM J Comput 10(2):297–309 · Zbl 0468.05043 · doi:10.1137/0210021
[57] Zaslavsky T (1998) Bibliography of signed and gain graphs. Electronic Journal of Combinatorics DS8, updated version available at http://www.math.binghamton.edu/zaslav/Bsg/ · Zbl 0898.05001
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.