×

Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover. (English) Zbl 1331.68281

Summary: We investigate the gap between theory and practice for exact branching algorithms. In theory, branch-and-reduce algorithms currently have the best time complexity for numerous important problems. On the other hand, in practice, state-of-the-art methods are based on different approaches, and the empirical efficiency of such theoretical algorithms has seldom been investigated probably because they are seemingly inefficient because of the plethora of complex reduction rules. In this paper, we design a branch-and-reduce algorithm for the vertex cover problem using the techniques developed for theoretical algorithms and compare its practical performance with other state-of-the-art empirical methods. The results indicate that branch-and-reduce algorithms are actually quite practical and competitive with other state-of-the-art approaches for several kinds of instances, thus showing the practical impact of theoretical research on branching algorithms.

MSC:

68W05 Nonnumerical algorithms
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)

Software:

DIMACS; WebGraph
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abu-Khzam, F. N.; Collins, R. L.; Fellows, M. R.; Langston, M. A.; Suters, W. H.; Symons, C. T., Kernelization algorithms for the vertex cover problem: theory and experiments, (ALENEX (2004)), 62-69
[2] Akiba, T.; Iwata, Y., Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover, (ALENEX (2015)), 70-81 · Zbl 1429.68164
[3] Boldi, P.; Rosa, M.; Santini, M.; Vigna, S., Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks, (WWW (2011)), 587-596
[4] Boldi, P.; Vigna, S., The WebGraph framework I: compression techniques, (WWW (2004)), 595-601
[5] Bourgeois, N.; Escoffier, B.; Paschos, V. T.; van Rooij, J. M.M., Fast algorithms for max independent set, Algorithmica, 62, 1-2, 382-415 (2012) · Zbl 1241.68087
[6] Chen, J.; Kanj, I. A.; Xia, G., Improved upper bounds for vertex cover, Theoret. Comput. Sci., 411, 40-42, 3736-3756 (2010) · Zbl 1205.05217
[7] Cheng, J.; Ke, Y.; Chu, S.; Cheng, C., Efficient processing of distance queries in large graphs: a vertex cover approach, (SIGMOD (2012)), 457-468
[8] Cygan, M.; Pilipczuk, M.; Pilipczuk, M.; Wojtaszczyk, J. O., On multiway cut parameterized above lower bounds, ACM Trans. Comput. Theory, 5, 1, 3 (2013) · Zbl 1322.68098
[9] Fomin, F. V.; Grandoni, F.; Kratsch, D., A measure & conquer approach for the analysis of exact algorithms, J. ACM, 56, 5, 25:1-25:32 (Aug. 2009)
[10] Funke, S.; Nusser, A.; Storandt, S., On \(k\)-path covers and their applications, Proc. VLDB Endow., 7, 10, 893-902 (2014)
[11] Hopcroft, J. E.; Karp, R. M., An \(n^{5 / 2}\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 4, 225-231 (1973) · Zbl 0266.05114
[12] Hüffner, F., Algorithm engineering for optimal graph bipartization, J. Graph Algorithms Appl., 13, 2, 77-98 (2009) · Zbl 1210.05110
[13] Iwata, Y., A faster algorithm for dominating set analyzed by the potential method, (IPEC (2011)), 41-54 · Zbl 1352.68111
[14] Iwata, Y.; Oka, K.; Yoshida, Y., Linear-time FPT algorithms via network flow, (SODA (2014)), 1749-1761 · Zbl 1423.68572
[15] (Johnson, D. J.; Trick, M. A., Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993 (1996), American Mathematical Society) · Zbl 0851.00080
[16] Kneis, J.; Langer, A.; Rossmanith, P., A fine-grained analysis of a simple independent set algorithm, (FSTTCS (2009)), 287-298 · Zbl 1248.05202
[17] Lokshtanov, D.; Narayanaswamy, N. S.; Raman, V.; Ramanujan, M. S.; Saurabh, S., Faster parameterized algorithms using linear programming (2012), CoRR · Zbl 1398.68254
[18] Nemhauser, G.; Trotter, L., Vertex packing: structural properties and algorithms, Math. Program., 8, 232-248 (1975) · Zbl 0314.90059
[19] Razgon, I., Computing minimum directed feedback vertex set in \(o(1.9977^n)\), (ICTCS (2007)), 70-81
[20] Razgon, I., Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3, J. Discrete Algorithms, 7, 2, 191-212 (2009) · Zbl 1187.68353
[21] Reed, B.; Smith, K.; Vetta, A., Finding odd cycle transversals, Oper. Res. Lett., 32, 4, 299-301 (2004) · Zbl 1052.05061
[22] Tomita, E.; Sutani, Y.; Higashi, T.; Takahashi, S.; Wakatsuki, M., A simple and faster branch-and-bound algorithm for finding a maximum clique, (WALCOM (2010)), 191-203 · Zbl 1274.05455
[23] Wahlström, M., Half-integrality, LP-branching and FPT algorithms, (SODA (2014)), 1762-1781 · Zbl 1418.68107
[24] Xiao, M.; Nagamochi, H., Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs, Theoret. Comput. Sci., 469, 92-104 (2013) · Zbl 1259.68263
[25] Xiao, M.; Nagamochi, H., Exact algorithms for maximum independent set, (ISAAC (2013)), 328-338 · Zbl 1406.68047
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.