Hitting and Harvesting Pumpkins

详细信息    查看全文

• 作者：Gwena?l Joret (1) gjoret@ulb.ac.be
  Christophe Paul (2) paul@lirmm.fr
  Ignasi Sau (2) sau@lirmm.fr
  Saket Saurabh (3) saket@imsc.res.in
  Stéphan Thomassé (4) stephan.thomasse@ens-lyon.fr
• 关键词：Hitting and packing – parameterized complexity – approximation algorithm – single ; exponential algorithm – iterative compression – graph minors
• 刊名：Lecture Notes in Computer Science
• 出版年：2011
• 出版时间：2011
• 年：2011
• 卷：6942
• 期：1
• 页码：394-407
• 全文大小：304.9 KB
• 参考文献：1. Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics 12(3), 289–297 (1999)
  2. Balasubramanian, R., Fellows, M., Raman, V.: An improved fixed parameter algorithm for Vertex Cover. Information Processing Letters 65, 163–168 (1998)
  3. Becker, A., Geiger, D.: Optimization of pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence 83, 167–188 (1996)
  4. Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: Proc. of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 629–638 (2009)
  5. Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 635–646. Springer, Heidelberg (2009)
  6. Bodlaender, H.L., van Leeuwen, J., Tan, R.B., Thilikos, D.M.: On interval routing schemes and treewidth. Information and Computation 139(1), 92–109 (1997)
  7. Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation 201(2), 216–231 (2005)
  8. Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science 411(40-42), 3736–3756 (2010)
  9. Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2 O(k) n 3) FPT Algorithm for the Undirected Feedback Vertex Set Problem. Theory of Computing Systems 41(3), 479–492 (2007)
  10. Diestel, R.: Graph Theory, vol. 173. Springer, Heidelberg (2005)
  11. Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, Heidelberg (1999)
  12. Fiorini, S., Joret, G., Pietropaoli, U.: Hitting Diamonds and Growing Cacti. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 191–204. Springer, Heidelberg (2010)
  13. Fiorini, S., Joret, G., Theis, D.O., Wood, D.R.: Small Minors in Dense Graphs (2010) (manuscript), http://arxiv.org/abs/1005.0895
  14. Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saurabh, S.: Hitting forbidden minors: Approximation and Kernelization. In: Proc. of the 28th Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, vol. 9, pp. 189–200 (2011)
  15. Friggstad, Z., Salavatipour, M.: Approximability of packing disjoint cycles. Algorithmica 60, 395–400 (2011)
  16. Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. Journal of Computer and System Sciences 72(8), 1386–1396 (2006)
  17. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63(4), 512–530 (2001)
  18. Joret, G., Paul, C., Sau, I., Saurabh, S., Thomassé, S.: Hitting and Harvesting Pumpkins (2011) (manuscript), http://arxiv.org/abs/1105.2704
  19. Krivelevich, M., Nutov, Z., Salavatipour, M.R., Yuster, J., Yuster, R.: Approximation algorithms and hardness results for cycle packing problems. ACM Transactions on Algorithms 3(4) (2007)
  20. Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6346, pp. 549–560. Springer, Heidelberg (2010)
  21. Lokshtanov, D., Marx, D., Saurabh, S.: Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal. In: Proc. of the 22nd annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 777–789 (2011)
  22. Robertson, N., Seymour, P.: Graph Minors. XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B 63(1), 65–110 (1995)
• 作者单位：1. Département d’Informatique, Université Libre de Bruxelles, Brussels, Belgium2. AlGCo project-team, CNRS, LIRMM, Montpellier, France3. The Institute of Mathematical Sciences, Chennai, India4. Laboratoire LIP, (U. Lyon, CNRS, ENS Lyon, INRIA, UCBL), Lyon, France
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

The c-pumpkin is the graph with two vertices linked by c?≥?1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph: On the one hand, we provide an FPT algorithm running in time 2O(k) nO(1)2^{\mathcal{O}(k)} n^{\mathcal{O}(1)} deciding, for any fixed c?≥?1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes the single-exponential FPT algorithms for Vertex Cover and Feedback Vertex Set, which correspond to the cases c?=?1,2 respectively. For this, we use a combination of iterative compression and a kernelization-like technique. On the other hand, we present an O(logn)\mathcal{O}(\log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices, and packing a maximum number of vertex-disjoint c-pumpkin-models. Our main ingredient here is a combinatorial lemma saying that any properly reduced n-vertex graph has a c-pumpkin-model of size at most f(c) logn, for a function f depending only on c.