×

Branch and recharge: exact algorithms for generalized domination. (English) Zbl 1244.68082

The authors present a new approach to the design and analysis of branching algorithms for exact solutions of NP-hard problems. The approach of branch and recharge is based on the combination of a branching algorithm and a recharging mechanism. The new methodology is illustrated using a generalization of the domination problem on graphs, \((\sigma,\varrho)\)-domination. A vertex subset \(S\subseteq V(G)\) is called a \((\sigma,\varrho)\)-dominating set if \(|N(v)\cap S|\in \sigma\) for all \(v\in S\) and \(|N(v)\cap S|\in \varrho\) for all \(v\in V\backslash S\), where \(\sigma\) and \(\varrho\) are nonempty sets of integers. The paper presents an algorithm with time complexity \(O^*(c^n)\) for the enumeration of all \((\sigma,\varrho)\)-dominating sets, where the constant \(c<2\) depends on \(\sigma\) and \(\varrho\).

MSC:

68W05 Nonnumerical algorithms
05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289 n ). J. Algorithms 54, 168–204 (2005) · Zbl 1101.68716 · doi:10.1016/j.jalgor.2004.06.008
[2] Björklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: Proceedings of FOCS 2006, pp. 575–582. IEEE Press, New York (2006) · Zbl 1170.68651
[3] Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32, 547–556 (2004) · Zbl 1052.05055 · doi:10.1016/j.orl.2004.03.002
[4] Byskov, J.M., Madsen, B.A., Skjernaa, B.: On the number of maximal bipartite subgraphs of a graph. J. Graph Theory 48, 127–132 (2005) · Zbl 1059.05045 · doi:10.1002/jgt.20041
[5] Eppstein, D.: Small maximal independent sets and faster exact graph coloring. J. Graph Algorithm Appl. 7, 131–140 (2003) · Zbl 1027.05092 · doi:10.7155/jgaa.00064
[6] Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination–a case study. In: Proceedings of ICALP 2005. LNCS, vol. 3380, pp. 192–203. Springer, Berlin (2005) · Zbl 1082.68866
[7] Fomin, F.V., Golovach, P., Kratsch, D., Kratochvil, J., Liedloff, M.: Branch and recharge: exact algorithms for generalized domination. In: Proceedings of WADS 2007. LNCS, vol. 4619, pp. 508–519. Springer, Berlin (2007) · Zbl 1209.05240
[8] Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52, 293–307 (2008) · Zbl 1170.68029 · doi:10.1007/s00453-007-9152-0
[9] Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9 (2008) · Zbl 1445.05101 · doi:10.1145/1435375.1435384
[10] Fomin, F.V., Golovach, P.A., Kratochvil, J., Kratsch, D., Liedloff, M.: Sort and search: exact algorithms for generalized domination. Inf. Process. Lett. 109, 795–798 (2009) · Zbl 1197.05104 · doi:10.1016/j.ipl.2009.03.023
[11] Fomin, F.V., Grandoni, F., Kratsch, D.: A measure &amp; conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25 (2009) · doi:10.1145/1552285.1552286
[12] Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: A simple O(20.288n ) independent set algorithm. In: Proceedings of SODA 2006, pp. 18–25. SIAM, Philadelphia (2006) · Zbl 1192.68960
[13] Golovach, P., Kratochvíl, J.: Computational complexity of generalized domination: a complete dichotomy for chordal graphs. In: Proceedings of WG 2007. LNCS, vol. 4769, pp. 1–11. Springer, Berlin (2007) · Zbl 1141.68530
[14] Golovach, P., Kratochvíl, J.: Generalized domination in degenerate graphs: a complete dichotomy of computational complexity. In: Proceedings of TAMC 2008. LNCS, vol. 4978, pp. 182–191. Springer, Berlin (2008) · Zbl 1139.68344
[15] Golovach, P., Kratochvíl, J., Suchý, O.: Parameterized complexity of generalized domination problems. In: Proceedings of WG 2009. LNCS, vol. 5911, pp. 133–142. Springer, Berlin (2009) · Zbl 1273.68171
[16] Gupta, S., Raman, V., Saurabh, S.: Fast exponential algorithms for Maximum r-regular induced subgraph problems. In: Proceedings of FSTTCS 2006. LNCS, vol. 4337, pp. 139–151. Springer, Berlin (2006) · Zbl 1177.68154
[17] Halldorsson, M.M., Kratochvíl, J., Telle, J.A.: Independent sets with domination constraints. Discrete Appl. Math. 99, 39–54 (2000) · Zbl 0939.05063 · doi:10.1016/S0166-218X(99)00124-9
[18] Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Dekker, New York (1998) · Zbl 0890.05002
[19] Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nord. J. Comput. 5, 128–142 (1998) · Zbl 0905.68100
[20] Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theor. Comput. Sci. 223, 1–72 (1999) · Zbl 0930.68066 · doi:10.1016/S0304-3975(98)00017-6
[21] Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5, 66–67 (1976) · Zbl 0336.68021 · doi:10.1016/0020-0190(76)90065-X
[22] Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 5, 23–28 (1965) · Zbl 0144.23205 · doi:10.1007/BF02760024
[23] Rosen, K.H.: Discrete Mathematics and Its Applications. McGraw-Hill, New York (2007)
[24] Telle, J.A.: Complexity of domination-type problems in graphs. Nord. J. Comput. 1, 157–171 (1994)
[25] Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization–Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Berlin (2003) · Zbl 1024.68529
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.