Search Results

Documents authored by Király, Tamás

Document
DOI: 10.4230/LIPIcs.ESA.2024.22
Hypergraph Connectivity Augmentation in Strongly Polynomial Time

Authors: Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We consider hypergraph network design problems where the goal is to construct a hypergraph that satisfies certain connectivity requirements. For graph network design problems where the goal is to construct a graph that satisfies certain connectivity requirements, the number of edges in every feasible solution is at most quadratic in the number of vertices. In contrast, for hypergraph network design problems, we might have feasible solutions in which the number of hyperedges is exponential in the number of vertices. This presents an additional technical challenge in hypergraph network design problems compared to graph network design problems: in order to solve the problem in polynomial time, we first need to show that there exists a feasible solution in which the number of hyperedges is polynomial in the input size. The central theme of this work is to overcome this additional technical challenge for certain hypergraph network design problems. We show that these hypergraph network design problems admit solutions in which the number of hyperedges is polynomial in the number of vertices and moreover, can be solved in strongly polynomial time. Our work improves on the previous fastest pseudo-polynomial run-time for these problems. As applications of our results, we derive the first strongly polynomial time algorithms for (i) degree-specified hypergraph connectivity augmentation using hyperedges and (ii) degree-specified hypergraph node-to-area connectivity augmentation using hyperedges.
Cite as

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni. Hypergraph Connectivity Augmentation in Strongly Polynomial Time. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.ESA.2024.22,
  author =	{B\'{e}rczi, Krist\'{o}f and Chandrasekaran, Karthekeyan and Kir\'{a}ly, Tam\'{a}s and Kulkarni, Shubhang},
  title =	{{Hypergraph Connectivity Augmentation in Strongly Polynomial Time}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.22},
  URN =		{urn:nbn:de:0030-drops-210938},
  doi =		{10.4230/LIPIcs.ESA.2024.22},
  annote =	{Keywords: Hypergraphs, Hypergraph Connectivity, Submodular Functions, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.25
Multiway Cuts with a Choice of Representatives

Authors: Kristóf Bérczi, Tamás Király, and Daniel P. Szabo

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
In the Multiway Cut problem, we are given an undirected graph with nonnegative edge weights and a subset of k terminals, and the goal is to determine a set of edges of minimum total weight whose removal disconnects each terminal from the rest. The problem is APX-hard for k ≥ 3, and an extensive line of research has concentrated on closing the gap between the best upper and lower bounds for approximability and inapproximability, respectively. In this paper, we study several generalizations of Multiway Cut where the terminals can be chosen as representatives from sets of candidates T₁,…,T_q. In this setting, one is allowed to choose these representatives so that the minimum-weight cut separating these sets via their representatives is as small as possible. We distinguish different cases depending on (A) whether the representative of a candidate set has to be separated from the other candidate sets completely or only from the representatives, and (B) whether there is a single representative for each candidate set or the choice of representative is independent for each pair of candidate sets. For fixed q, we give approximation algorithms for each of these problems that match the best known approximation guarantee for Multiway Cut. Our technical contribution is a new extension of the CKR relaxation that preserves approximation guarantees. For general q, we show o(log q)-inapproximability for all cases where the choice of representatives may depend on the pair of candidate sets, as well as for the case where the goal is to separate a fixed node from a single representative from each candidate set. As a positive result, we give a 2-approximation algorithm for the case where we need to choose a single representative from each candidate set. This is a generalization of the (2-2/k)-approximation for k-Cut, and we can solve it by relating the tree case to optimization over a gammoid.
Cite as

Kristóf Bérczi, Tamás Király, and Daniel P. Szabo. Multiway Cuts with a Choice of Representatives. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.MFCS.2024.25,
  author =	{B\'{e}rczi, Krist\'{o}f and Kir\'{a}ly, Tam\'{a}s and Szabo, Daniel P.},
  title =	{{Multiway Cuts with a Choice of Representatives}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.25},
  URN =		{urn:nbn:de:0030-drops-205813},
  doi =		{10.4230/LIPIcs.MFCS.2024.25},
  annote =	{Keywords: Approximation algorithms, Multiway cut, CKR relaxation, Steiner multicut}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.23
Splitting-Off in Hypergraphs

Authors: Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of that vertex while preserving their degrees. Lovász [Lov{á}sz, 1974; Lov{á}sz, 1993] and Mader [Mader, 1978] showed the existence of this operation while preserving global and local connectivities respectively in graphs under certain conditions. These results have far-reaching applications in graph algorithms literature [Lovász, 1976; Mader, 1978; Frank, 1993; Frank and Király, 2002; Király and Lau, 2008; Frank, 1992; Goemans and Bertsimas, 1993; Frank, 1994; Bang-Jensen et al., 1995; Frank, 2011; Nagamochi and Ibaraki, 2008; Nagamochi et al., 1997; Henzinger and Williamson, 1996; Goemans, 2001; Jordán, 2003; Kriesell, 2003; Jain et al., 2003; Chan et al., 2011; Bhalgat et al., 2008; Lau, 2007; Chekuri and Shepherd, 2008; Nägele and Zenklusen, 2020; Blauth and Nägele, 2023]. In this work, we introduce a splitting-off operation in hypergraphs. We show that there exists a local connectivity preserving complete splitting-off in hypergraphs and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs. We illustrate the usefulness of our splitting-off operation in hypergraphs by showing two applications: (1) we give a constructive characterization of k-hyperedge-connected hypergraphs and (2) we give an alternate proof of an approximate min-max relation for max Steiner rooted-connected orientation of graphs and hypergraphs (due to Király and Lau [Király and Lau, 2008]). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams' strong orientation theorem and uses tools developed for hypergraphs.
Cite as

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni. Splitting-Off in Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.ICALP.2024.23,
  author =	{B\'{e}rczi, Krist\'{o}f and Chandrasekaran, Karthekeyan and Kir\'{a}ly, Tam\'{a}s and Kulkarni, Shubhang},
  title =	{{Splitting-Off in Hypergraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.23},
  URN =		{urn:nbn:de:0030-drops-201660},
  doi =		{10.4230/LIPIcs.ICALP.2024.23},
  annote =	{Keywords: Hypergraphs, Hypergraph Connectivity, Splitting-off, Constructive Characterizations, Hypergraph Orientations, Submodular Functions, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.2
Global and Fixed-Terminal Cuts in Digraphs

Authors: Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, and Chao Xu

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
The computational complexity of multicut-like problems may vary significantly depending on whether the terminals are fixed or not. In this work we present a comprehensive study of this phenomenon in two types of cut problems in directed graphs: double cut and bicut. 1. Fixed-terminal edge-weighted double cut is known to be solvable efficiently. We show that fixed-terminal node-weighted double cut cannot be approximated to a factor smaller than 2 under the Unique Games Conjecture (UGC), and we also give a 2-approximation algorithm. For the global version of the problem, we prove an inapproximability bound of 3/2 under UGC. 2. Fixed-terminal edge-weighted bicut is known to have an approximability factor of 2 that is tight under UGC. We show that the global edge-weighted bicut is approximable to a factor strictly better than 2, and that the global node-weighted bicut cannot be approximated to a factor smaller than 3/2 under UGC. 3. In relation to these investigations, we also prove two results on undirected graphs which are of independent interest. First, we show NP-completeness and a tight inapproximability bound of 4/3 for the node-weighted 3-cut problem under UGC. Second, we show that for constant k, there exists an efficient algorithm to solve the minimum {s,t}-separating k-cut problem. Our techniques for the algorithms are combinatorial, based on LPs and based on the enumeration of approximate min-cuts. Our hardness results are based on combinatorial reductions and integrality gap instances.
Cite as

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, and Chao Xu. Global and Fixed-Terminal Cuts in Digraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.APPROX-RANDOM.2017.2,
  author =	{B\'{e}rczi, Krist\'{o}f and Chandrasekaran, Karthekeyan and Kir\'{a}ly, Tam\'{a}s and Lee, Euiwoong and Xu, Chao},
  title =	{{Global and Fixed-Terminal Cuts in Digraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.2},
  URN =		{urn:nbn:de:0030-drops-75511},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.2},
  annote =	{Keywords: Directed Graphs, Arborescence, Graph Cuts, Hardness of Approximation}
}
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 About DROPS Imprint Privacy Contact