On algorithms employing treewidth for \(L\)-bounded cut problems. (English) Zbl 1384.05147
Summary: Given a graph \(G=(V,E)\) with two distinguished vertices \(s,t\in V\) and an integer parameter \(L>0\), an \(L\)-bounded cut is a subset \(F\) of edges (vertices) such that the every path between \(s\) and \(t\) in \(G\setminus F\) has length more than \(L\). The task is to find an \(L\)-bounded cut of minimum cardinality.
Though the problem is very simple to state and has been studied since the beginning of the 70’s, it is not much understood yet. The problem is known to be \(\mathcal{NP}\)-hard to approximate within a small constant factor even for \(L\geq 4\) (for \(L\geq 5\) for the vertex-deletion version). On the other hand, the best known approximation algorithm for general graphs has approximation ratio only \(\mathcal{O}({n^{2/3}})\) in the edge case, and \(\mathcal{O}({\sqrt{n}})\) in the vertex case, where \(n\) denotes the number of vertices.
We show that for planar graphs, it is possible to solve both the edge- and the vertex-deletion version of the problem optimally in \(\mathcal{O}((L+2)^{3L}n)\) time. That is, the problem is fixed-parameter tractable (FPT) with respect to \(L\) on planar graphs. Furthermore, we show that the problem remains FPT even for bounded genus graphs, a super class of planar graphs.
Our second contribution deals with approximations of the vertex-deletion version of the problem. We describe an algorithm that for a given graph \(G\), its tree decomposition of width \(\tau\) and vertices \(s\) and \(t\) computes a \(\tau\)-approximation of the minimum \(L\)-bounded \(s-t\) vertex cut; if the decomposition is not given, then the approximation ratio is \(\mathcal{O}(\tau \sqrt{\log \tau})\). For graphs with treewidth bounded by \(\mathcal{O}(n^{1/2-\varepsilon})\) for any \(\varepsilon>0\), but not by a constant, this is the best approximation in terms of \(n\) that we are aware of.
Though the problem is very simple to state and has been studied since the beginning of the 70’s, it is not much understood yet. The problem is known to be \(\mathcal{NP}\)-hard to approximate within a small constant factor even for \(L\geq 4\) (for \(L\geq 5\) for the vertex-deletion version). On the other hand, the best known approximation algorithm for general graphs has approximation ratio only \(\mathcal{O}({n^{2/3}})\) in the edge case, and \(\mathcal{O}({\sqrt{n}})\) in the vertex case, where \(n\) denotes the number of vertices.
We show that for planar graphs, it is possible to solve both the edge- and the vertex-deletion version of the problem optimally in \(\mathcal{O}((L+2)^{3L}n)\) time. That is, the problem is fixed-parameter tractable (FPT) with respect to \(L\) on planar graphs. Furthermore, we show that the problem remains FPT even for bounded genus graphs, a super class of planar graphs.
Our second contribution deals with approximations of the vertex-deletion version of the problem. We describe an algorithm that for a given graph \(G\), its tree decomposition of width \(\tau\) and vertices \(s\) and \(t\) computes a \(\tau\)-approximation of the minimum \(L\)-bounded \(s-t\) vertex cut; if the decomposition is not given, then the approximation ratio is \(\mathcal{O}(\tau \sqrt{\log \tau})\). For graphs with treewidth bounded by \(\mathcal{O}(n^{1/2-\varepsilon})\) for any \(\varepsilon>0\), but not by a constant, this is the best approximation in terms of \(n\) that we are aware of.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W25 | Approximation algorithms |
Keywords:
approximation algorithmReferences:
| [1] | J. Ad´amek and V. Koubek.Remarks on flows in network with short paths. Commentationes Mathematicae Universitatis Carolinae, 12(4):661- 667, 1971. URL: · Zbl 0223.05108 |
| [2] | G. Baier, T. Erlebach, A. Hall, E. K¨ohler, P. Kolman, O. Pangr´ac, H. Schilling, and M. Skutella. Length-bounded cuts and flows. ACM Trans. Algorithms, 7(1):4:1-4:27, 2010. Preliminary version in Proc. of 33rd Inter national Colloquium on Automata, Languages, and Programming (ICALP), 2006. · Zbl 1295.68119 · doi:10.1145/1868237.1868241. |
| [3] | M. O. Ball, B. L. Golden, and R. V. Vohra. Finding the most vital arcs in a network. Operations Research Letters, 8(2):73 - 76, 1989. · Zbl 0679.90086 · doi:10.1016/ |
| [4] | A. Bar-Noy, S. Khuller, and B. Schieber. The complexity of finding most vital arcs and nodes. Technical Report CS-TR-3539, Univ. of Maryland, Dept. of Computer Science, Nov. 1995. URL: |
| [5] | C. Bazgan, A. Nichterlein, and R. Niedermeier. A refined complexity analy sis of finding the most vital edges for undirected shortest paths. In Proc. of Algorithms and Complexity - 9th International Conference (CIAC), pages 47-60, 2015. · Zbl 1459.68152 · doi:10.1007/978-3-319-18173-8_3. |
| [6] | H. L. Bodlaender. Planar graphs with bounded treewidth. Technical Report RUU-CS-88-14, Univ. Utrecht, Dept. of Computer Science, 1988. · Zbl 0684.68047 |
| [7] | H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and M. Pilipczuk. A c k n 5-approximation algorithm for treewidth. SIAM J. Comput, 45(2):317-378, 2016. · Zbl 1333.05282 · doi:10.1137/130947374. |
| [8] | M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. · Zbl 1334.90001 |
| [9] | A. Czumaj, M. M. Halld´orsson, A. Lingas, and J. Nilsson.Approx imation algorithms for optimization problems in graphs with superlog arithmic treewidth.Information Processing Letters, 94(2):49-53, 2005. · Zbl 1182.68361 · doi:10.1016/j.ipl.2004.12.017. |
| [10] | P. Dvoˇr´ak and D. Knop.Parametrized complexity of length-bounded cuts and multi-cuts. In Proc. of 12 Annual Conference on Theory and Applications of Models of Computation (TAMC), pages 441-452, 2015. · Zbl 1454.68056 · doi:10.1007/978-3-319-17142-5_37. |
| [11] | D. Eppstein. Diameter and treewidth in minor-closed graph families. Al gorithmica, 27(3):275-291, 2000. · Zbl 0963.05128 · doi:10.1007/s004530010020. |
| [12] | U. Feige, M. T. Hajiaghayi, and J. R. Lee.Improved approximation algorithms for minimum weight vertex separators.SIAM J. Comput, 38(2):629-657, 2008. Preliminary version in Proc. of STOC 2005. · Zbl 1172.68063 |
| [13] | T. Fluschnik, D. Hermelin, A. Nichterlein, and R. Niedermeier. Fractals for kernelization lower bounds, with an application to length-bounded cut problems. CoRR, abs/1512.00333, 2015. · Zbl 1388.68111 |
| [14] | T. Fluschnik, D. Hermelin, A. Nichterlein, and R. Niedermeier.Frac tals for kernelization lower bounds, with an application to length-bounded cut problems. In Proc. of 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 25:1-25:14, 2016. · Zbl 1388.68111 |
| [15] | E. C. Freuder.Complexity of K-tree structured constraint satisfaction problems. In Proc. of the 8th National Conference on Artificial Intelligence, pages 4-9, 1990. |
| [16] | P. A. Golovach and D. M. Thilikos. Paths of bounded length and their cuts: Parameterized complexity and algorithms. Discrete Optimization, 8(1):72-86, 2011. · Zbl 1248.90071 · doi:10.1016/j.disopt.2010.09.009. |
| [17] | F. Harary. Graph Theory. Addison-Wesley, 1969. · Zbl 0182.57702 |
| [18] | R. Impagliazzo and R. Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci, 62(2):367-375, 2001. · Zbl 0990.68079 · doi:10.1006/jcss.2000.1727. |
| [19] | L. Khachiyan, E. Boros, K. Borys, K. M. Elbassioni, V. Gurvich, G. Rudolf, and J. Zhao. On short paths interdiction problems: Total and node-wise limited interdiction. Theory Comput. Syst, 43(2):204-233, 2008. · Zbl 1148.68036 · doi:10. |
| [20] | P. Klein, S. Rao, M. Rauch, and S. Subramanian. Faster shortest-path algorithms for planar graphs. In Proc. of the 26th ACM Symposium on Theory of Computing (STOC), pages 27-37, 1994. · Zbl 1345.05103 · doi:10.1145/195058. |
| [21] | T. Kloks. Treewidth: Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. · Zbl 0825.68144 |
| [22] | P. Kolman and M. Kouteck´y. Extended formulation for CSP that is com pact for instances of bounded treewidth. Electr. J. Comb, 22(4):P4.30, 2015. · Zbl 1393.68073 |
| [23] | E. Lee. Improved hardness for cut, interdiction, and firefighter problems. In Proc. of 44rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 92:1-92:14, 2017. · Zbl 1442.68067 · doi:10.4230/LIPIcs. |
| [24] | F. T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787- 832, 1999. · Zbl 1065.68666 · doi:10.1145/331524.331526. |
| [25] | D. Lokshtanov, D. Marx, and S. Saurabh. Known algorithms on graphs on bounded treewidth are probably optimal. In Proc. of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 777-789, 2011. · Zbl 1373.68242 · doi:10.1137/1.9781611973082. |
| [26] | L. Lov´asz, V. Neumann-Lara, and M. D. Plummer. Mengerian theorems for paths of bounded length. Periodica Mathematica Hungarica, 9:269-276, 1978. · Zbl 0393.05033 · doi:10.1007/BF02019432. |
| [27] | A. R. Mahjoub and S. T. McCormick. Max flow and min cut with bounded length paths: complexity, algorithms, and approximation. Math. Program, 124(1-2):271-284, 2010. · Zbl 1198.90072 · doi:10.1007/s10107-010-0366-6. |
| [28] | N. Robertson and P. D. Seymour. Graph minors. III. planar tree-width. J. Comb. Theory, Ser. B, 36(1):49-64, 1984. · Zbl 0548.05025 · doi:10.1016/0095-8956(84) |
| [29] | M. Thorup. Undirected single-source shortest paths with positive inte ger weights in linear time. J. ACM, 46(3):362-394, 1999. · Zbl 1065.68597 · doi:10.1145/ |
| [30] | P. Zschoche, T. Fluschnik, H. Molter, and R. Niedermeier. The Compu tational Complexity of Finding Separators in Temporal Graphs. ArXiv e-prints, Nov. 2017. A Appendix L-bounded Cut as a CSP Instance An instance Q = (V, D, H, C) of CSP consists of • a set of variables z v, one for each v ∈ V ; without loss of generality we assume that V = {1, . . . , n}, • a set D of finite domains D v(also denoted D(v)), one for each v ∈ V , • a set of hard constraints H ⊆ {C U| U ⊆ V } and a set of soft con straints C ⊆ {C U| U ⊆ V } where each constraint C U∈ C ∪ H with U = {i 1, i 2, . . . , i k} and i 1< i 2< · · · < i k, is a |U |-ary relation C U⊆ D i 1× D i 2× · · · × D i k. For a vector z = (z 1, z 2, . . . , z n) and U = {i 1, i 2, . . . , i k} ⊆ V with i 1< i 2< · · · < i k, we define the projection of z on U as z |U= (z i, z i 2, . . . , z i). A 1 k vector z = (z 1, z 2, . . . , z n) satisfies the constraint C U∈ C ∪ H if and only if z|U∈ C U. We say that a vector z?= (z?1, . . . , z n?) is a feasible solution for Q if z?∈ D 1× D 2× . . . × D n and z?satisfies every hard constraint C ∈ H. In the maximization (minimization, resp.) version of CSP, the task is to find a feasible solution that maximizes (minimizes, resp.) the number of satisfied (unsatisfied, resp.) soft constraints; the cost of a feasible solution is the number of satisfied (unsatisfied, resp.) soft constraints. The constraint graph of Q is defined as H=(V, E) where E= {{u, v} | ∃C U∈ C ∪ H s.t. {u, v} ⊆ U }.We say that a CSP instance Q has bounded treewidth if the constraint graph of Q has bounded treewidth. Given an edge-deletion version of the L-bounded cut instance G = (V, E) with s, t ∈ V and an integer L, we construct the corresponding minimization CSP instance Q = (V, D, H, C) as follows. The set of variables of Q coincides with the set V of vertices of G and for each v ∈ V , the corresponding domain D v is {0, 1, . . . , L, L + 1}. The set of hard constraints H consists of two constraints, C{s}= {0} and C{t}= {L + 1}.The set of soft constraints C contains a constraint C{i,j}= {(‘, ‘0) | 0 ≤ ‘, ‘0≤ L + 1, |‘ − ‘0| ≤ 1} for each edge {i, j} ∈ E of the graph G. To see that a feasible solution for the constructed instance Q of CSP corre sponds to a feasible solution of the L-bounded cut problem of the same cost, and vice versa, we observe the following. Given an optimal solution F ⊂ E of the edge-deletion version of the L bounded cut problem, we distinguish two cases. If s and t belong to the same component of connectivity in (V, E F ), then the vector of shortest path dis tances from s to all other vertices in (V, E F ) yields a feasible solution for the CSP instance Q (to be more precise, if some of the distances are larger than L + 1, we replace in the vector every such value by L + 1); if s and t do not belong to the same component of connectivity in (V, E F ), we obtain a feasible solution for Q by assigning the value 0 to every vertex in the s-component and the value L + 1 to every vertex in the t-component. Note that in both cases the cost of the L-bounded cut and the cost of the CSP instance Q are the same. We also note that for every feasible solution (z 1, . . . , z n) of the instance Q, the set F = {{u, v} ∈ E | |z u− z v| > 1} is an L-bounded cut of the same cost. Finally, we note that the constraint graph of Q coincides with the original graph G. For the vertex-deletion version of the L-bounded cut problem in G = (V, E), the corresponding minimization CSP instance Q = (V, D, H, C) is defined sim ilarly. For each v ∈ V , we have D v= {−1, 0, . . . , L, L + 1} - the domain of every vertex is extended by an extra element −1 representing the fact that v belongs to the L-bounded cut. The set of hard constraints H contains con straints C{s}= {0} and C{t}= {L + 1}, and for each edge {i, j} ∈ E also a constraint H{i,j}={(‘, ‘0) | 0 ≤ ‘, ‘0≤ L + 1, |‘ − ‘0| ≤ 1} ∪ {(‘, −1) | 0 ≤ ‘ ≤ L + 1} ∪ {(−1, ‘) | 0 ≤ ‘ ≤ L + 1} . The set of soft constraints contains for each vertex u other than s and t a constraint C{u}= {0, 1 . . . , L, L + 1} . Given an optimal solution U ⊂ V of the vertex-deletion version of the L bounded cut problem, we distinguish two cases. If s and t belong to the same component of connectivity of G 0= G U , then assigning to every v ∈ U the value −1 and assigning to every v ∈ V U its distance from s in G 0 yields a feasible solution for the CSP instance Q (to be more precise, if some of the distances are larger than L + 1, we replace in the vector every such value by L + 1); if s and t do not belong to the same component of connectivity in G 0, we obtain a feasible solution for Q by assigning the value 0 to every vertex in the s-component, the value L + 1 to every vertex in the t-component and the value −1 to every v ∈ U . Note that in both cases the size of the L-bounded cut and the cost of the CSP instance Q are the same. We also note that for every feasible solution (z 1, . . . , z n) of the instance Q, the set U = {v ∈ V | z v= −1} is an L-bounded cut of size equal the cost of Q. Introduction Preliminaries Fixed-parameter Tractability on Planar and Bounded Genus Graphs-Approximation for L-bounded Vertex Cuts Open problems Appendix L-bounded Cut as a CSP Instance |
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.
