Document Open Access Logo

Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs

Authors Ralf Borndörfer , Katrin Casel , Davis Issac , Aikaterini Niklanovits , Stephan Schwartz , Ziena Zeif

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.27.pdf
  • Filesize: 0.83 MB
  • 14 pages

Document Identifiers

Author Details

Ralf Borndörfer
  • Zuse Institute Berlin, Germany
Katrin Casel
  • Hasso Plattner Institute, University of Potsdam, Germany
Davis Issac
  • Hasso Plattner Institute, University of Potsdam, Germany
Aikaterini Niklanovits
  • Hasso Plattner Institute, University of Potsdam, Germany
Stephan Schwartz
  • Zuse Institute Berlin, Germany
Ziena Zeif
  • Hasso Plattner Institute, University of Potsdam, Germany

Funding

This research was partially funded by the HPI Research School on Data Science and Engineering.
  • Niklanovits, Aikaterini: HPI Research School
  • Zeif, Ziena: HPI Research School

Cite AsGet BibTex

Ralf Borndörfer, Katrin Casel, Davis Issac, Aikaterini Niklanovits, Stephan Schwartz, and Ziena Zeif. Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.27

Abstract

A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c-1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w₁,…,w_k. In the 1970s Győri and Lovász showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T₁,…, T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least (w_i)/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least (w_i)/3 and at most max({r,3}) w_i, where r ≥ 1 is the ratio between the largest and smallest value in w₁, … , w_k. In particular for the balanced version, i.e. w₁ = w₂ = , … , = w_k, this gives a partition with 1/3w_i ≤ w(T_i) ≤ 3w_i.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • connected partition
  • Győri-Lovász
  • balanced partition
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Curtis A Barefoot, Roger Entringer, and Henda Swart. Vulnerability in graphs a comparative survey. Journal of Combinatorial Mathematics and Combinatorial Computing, 1:13-22, 1998. Google Scholar
  2. Ronald Becker, Isabella Lari, Mario Lucertini, and Bruno Simeone. Max-min partitioning of grid graphs into connected components. Networks: An International Journal, 32(2):115-125, 1998. Google Scholar
  3. Ronald Becker, Isabella Lari, Mario Lucertini, and Bruno Simeone. A polynomial-time algorithm for max-min partitioning of ladders. Theory of Computing Systems, 34(4):353-374, 2001. Google Scholar
  4. Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. In Algorithm Engineering, pages 117-158. Springer, 2016. Google Scholar
  5. Paolo M Camerini, Giulia Galbiati, and Francesco Maffioli. On the complexity of finding multi-constrained spanning trees. Discrete Applied Mathematics, 5(1):39-50, 1983. Google Scholar
  6. Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits, and Ziena Zeif. Balanced crown decomposition for connectivity constraints. arXiv preprint arXiv:2011.04528, 2020. Google Scholar
  7. L. Sunil Chandran, Yun Kuen Cheung, and Davis Issac. Spanning tree congestion and computation of generalized györi-lovász partition. In 45th International Colloquium on Automata, Languages, and Programming, volume 107 of LIPIcs, pages 32:1-32:14, 2018. Google Scholar
  8. Frédéric Chataigner, Liliane Benning Salgado, and Yoshiko Wakabayashi. Approximation and inapproximability results on balanced connected partitions of graphs. Discrete Mathematics and Theoretical Computer Science, 9(1), 2007. URL: http://dmtcs.episciences.org/384.
  9. Guangting Chen, Yong Chen, Zhi-Zhong Chen, Guohui Lin, Tian Liu, and An Zhang. Approximation algorithms for the maximally balanced connected graph tripartition problem. Journal of Combinatorial Optimization, pages 1-21, 2020. Google Scholar
  10. Jiangzhuo Chen, Robert D Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, and Adrian Vetta. (almost) tight bounds and existence theorems for single-commodity confluent flows. Journal of the ACM (JACM), 54(4):16, 2007. Google Scholar
  11. Yong Chen, Zhi-Zhong Chen, Guohui Lin, Yao Xu, and An Zhang. Approximation algorithms for maximally balanced connected graph partition. In International Conference on Combinatorial Optimization and Applications, pages 130-141. Springer, 2019. Google Scholar
  12. Janka Chlebíková. Approximating the maximally balanced connected partition problem in graphs. Information Processing Letters, 60(5):225-230, 1996. Google Scholar
  13. An-Chiang Chu, Bang Ye Wu, and Kun-Mao Chao. A linear-time algorithm for finding an edge-partition with max-min ratio at most two. Discrete Applied Mathematics, 161(7-8):932-943, 2013. Google Scholar
  14. Maria Chudnovsky and Paul Seymour. Claw-free graphs. I. orientable prismatic graphs. Journal of Combinatorial Theory, Series B, 97(6):867-903, 2007. Google Scholar
  15. Maria Chudnovsky and Paul Seymour. Claw-free graphs. II. non-orientable prismatic graphs. Journal of Combinatorial Theory, Series B, 98(2):249-290, 2008. Google Scholar
  16. Maria Chudnovsky and Paul Seymour. Claw-free graphs. III. circular interval graphs. Journal of Combinatorial Theory, Series B, 98(4):812-834, 2008. Google Scholar
  17. Maria Chudnovsky and Paul Seymour. Claw-free graphs. IV. decomposition theorem. Journal of Combinatorial Theory, Series B, 98(5):839-938, 2008. Google Scholar
  18. Maria Chudnovsky and Paul Seymour. Claw-free graphs. V. global structure. Journal of Combinatorial Theory, Series B, 98(6):1373-1410, 2008. Google Scholar
  19. Maria Chudnovsky and Paul Seymour. Claw-free graphs VI. colouring. Journal of Combinatorial Theory, Series B, 100(6):560-572, 2010. Google Scholar
  20. Maria Chudnovsky and Paul Seymour. Claw-free graphs. VII. quasi-line graphs. Journal of Combinatorial Theory, Series B, 102(6):1267-1294, 2012. Google Scholar
  21. Maria Chudnovsky and Paul D Seymour. The structure of claw-free graphs. Surveys in combinatorics, 327:153-171, 2005. Google Scholar
  22. Phillip EC Compeau, Pavel A Pevzner, and Glenn Tesler. How to apply de bruijn graphs to genome assembly. Nature biotechnology, 29(11):987-991, 2011. Google Scholar
  23. Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Dominating set is fixed parameter tractable in claw-free graphs. Theoretical Computer Science, 412(50):6982-7000, 2011. Google Scholar
  24. Yuri Faenza, Gianpaolo Oriolo, and Gautier Stauffer. Solving the weighted stable set problem in claw-free graphs via decomposition. Journal of the ACM (JACM), 61(4):1-41, 2014. Google Scholar
  25. Greg N. Frederickson. Optimal algorithms for tree partitioning. In Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, pages 168-177. ACM/SIAM, 1991. URL: http://dl.acm.org/citation.cfm?id=127787.127822.
  26. E Gyori. On division of graphs to connected subgraphs, combinatorics. In Colloquia Mathematica Societatis Janos Bolyai, 1976, 1976. Google Scholar
  27. Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized complexity of induced graph matching on claw-free graphs. Algorithmica, 70(3):513-560, 2014. Google Scholar
  28. Alexander Hoyer. On the Independent Spanning Tree Conjectures and Related Problems. PhD thesis, Georgia Institute of Technology, 2019. Google Scholar
  29. Davis Issac. On some covering, partition and connectivity problems in graphs. PhD thesis, Saarländische Universitäts-und Landesbibliothek, 2019. Google Scholar
  30. Takehiro Ito, Xiao Zhou, and Takao Nishizeki. Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size. Journal of discrete algorithms, 4(1):142-154, 2006. Google Scholar
  31. Sukhamay Kundu and Jayadev Misra. A linear tree partitioning algorithm. SIAM Journal on Computing, 6(1):151-154, 1977. Google Scholar
  32. László Lovász. A homology theory for spanning tress of a graph. Acta Mathematica Academiae Scientiarum Hungarica, 30(3-4):241-251, 1977. Google Scholar
  33. Christian Löwenstein, Dieter Rautenbach, and Friedrich Regen. On spanning tree congestion. Discrete mathematics, 309(13):4653-4655, 2009. Google Scholar
  34. Mario Lucertini, Yehoshua Perl, and Bruno Simeone. Most uniform path partitioning and its use in image processing. Discrete Applied Mathematics, 42(2-3):227-256, 1993. Google Scholar
  35. Rolf H Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm. Partitioning graphs to speedup dijkstra’s algorithm. Journal of Experimental Algorithmics (JEA), 11:2-8, 2007. Google Scholar
  36. Yehoshua Perl and Stephen R Schach. Max-min tree partitioning. Journal of the ACM (JACM), 28(1):5-15, 1981. Google Scholar
  37. Hitoshi Suzuki, Naomi Takahashi, and Takao Nishizeki. A linear algorithm for bipartition of biconnected graphs. Information Processing Letters, 33(5):227-231, 1990. Google Scholar
  38. Koichi Wada and Kimio Kawaguchi. Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 132-143. Springer, 1993. Google Scholar
  39. Xing Zhou, Huaimin Wang, Bo Ding, Tianjiang Hu, and Suning Shang. Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm. Expert Systems with Applications, 116:10-20, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact