DROPS

Volume

LIPIcs, Volume 18

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

FSTTCS 2012, December 15-17, 2012, Hyderabad, India

Editors: Deepak D'Souza, Jaikumar Radhakrishnan, and Kavitha Telikepalli

Document

Short Paper

DOI: 10.4230/LIPIcs.CP.2024.37

Computing Small Rainbow Cycle Numbers with SAT Modulo Symmetries (Short Paper)

Authors: Markus Kirchweger and Stefan Szeider

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract

Envy-freeness up to any good (EFX) is a key concept in Computational Social Choice for the fair division of indivisible goods, where no agent envies another’s allocation after removing any single item. A deeper understanding of EFX allocations is facilitated by exploring the rainbow cycle number (R_f(d)), the largest number of independent sets in a certain class of directed graphs. Upper bounds on R_f(d) provide guarantees to the feasibility of EFX allocations (Chaudhury et al., EC 2021). In this work, we precisely compute the numbers R_f(d) for small values of d, employing the SAT modulo Symmetries framework (Kirchweger and Szeider, CP 2021). SAT modulo Symmetries is tailored specifically for the constraint-based isomorph-free generation of combinatorial structures. We provide an efficient encoding for the rainbow cycle number, comparing eager and lazy approaches. To cope with the huge search space, we extend the encoding with invariant pruning, a new method that significantly speeds up computation.

Cite as

Markus Kirchweger and Stefan Szeider. Computing Small Rainbow Cycle Numbers with SAT Modulo Symmetries (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 37:1-37:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kirchweger_et_al:LIPIcs.CP.2024.37,
  author =	{Kirchweger, Markus and Szeider, Stefan},
  title =	{{Computing Small Rainbow Cycle Numbers with SAT Modulo Symmetries}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{37:1--37:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.37},
  URN =		{urn:nbn:de:0030-drops-207221},
  doi =		{10.4230/LIPIcs.CP.2024.37},
  annote =	{Keywords: EFX, rainbow cycle number, SAT modulo Symmetries, combinatorial search}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2024.69

Scheduling with Locality by Routing

Authors: Alison Hsiang-Hsuan Liu and Fu-Hong Liu

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

Abstract

This work examines a strongly NP-hard routing problem on trees, in which multiple servers need to serve a given set of requests (on vertices), where the routes of the servers start from a common source and end at their respective terminals. Each server can travel free of cost on its source-to-terminal path but has to pay for travel on other edges. The objective is to minimize the maximum cost over all servers. As the servers may pay different costs for traveling through a common edge, balancing the loads of the servers can be difficult. We propose a polynomial-time 4-approximation algorithm that applies the parametric pruning framework but consists of two phases. The first phase of the algorithm partitions the requests into packets, and the second phase of the algorithm assigns the packets to the servers. Unlike the standard parametric pruning techniques, the challenge of our algorithm design and analysis is to harmoniously relate the quality of the partition in the first phase, the balances of the servers' loads in the second phase, and the hypothetical optimal values of the framework. For the problem in general graphs, we show that there is no algorithm better than 2-approximate unless P = NP. The problem is a generalization of unrelated machine scheduling and other classic scheduling problems. It also models scheduling problems where the job processing times depend on the machine serving the job and the other jobs served by that machine. This modeling provides a framework that physicalizes scheduling problems through the graph’s point of view.

Cite as

Alison Hsiang-Hsuan Liu and Fu-Hong Liu. Scheduling with Locality by Routing. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 69:1-69:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2024.69,
  author =	{Liu, Alison Hsiang-Hsuan and Liu, Fu-Hong},
  title =	{{Scheduling with Locality by Routing}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{69:1--69:15},
  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.69},
  URN =		{urn:nbn:de:0030-drops-206250},
  doi =		{10.4230/LIPIcs.MFCS.2024.69},
  annote =	{Keywords: Makespan minimization, Approximation algorithms, Routing problems, Parametric pruning framework}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.28

Additive Spanner Lower Bounds with Optimal Inner Graph Structure

Authors: Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, and Zixuan Xu

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

Abstract

We construct n-node graphs on which any O(n)-size spanner has additive error at least +Ω(n^{3/17}), improving on the previous best lower bound of Ω(n^{1/7}) [Bodwin-Hoppenworth FOCS '22]. Our construction completes the first two steps of a particular three-step research program, introduced in prior work and overviewed here, aimed at producing tight bounds for the problem by aligning aspects of the upper and lower bound constructions. More specifically, we develop techniques that enable the use of inner graphs in the lower bound framework whose technical properties are provably tight with the corresponding assumptions made in the upper bounds. As an additional application of our techniques, we improve the corresponding lower bound for O(n)-size additive emulators to +Ω(n^{1/14}).

Cite as

Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, and Zixuan Xu. Additive Spanner Lower Bounds with Optimal Inner Graph Structure. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.28,
  author =	{Bodwin, Greg and Hoppenworth, Gary and Vassilevska Williams, Virginia and Wein, Nicole and Xu, Zixuan},
  title =	{{Additive Spanner Lower Bounds with Optimal Inner Graph Structure}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{28:1--28:17},
  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.28},
  URN =		{urn:nbn:de:0030-drops-201715},
  doi =		{10.4230/LIPIcs.ICALP.2024.28},
  annote =	{Keywords: Additive Spanners, Graph Theory}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.58

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Authors: Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos

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

Abstract

We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with m edges and n nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is (2+ε)-APSP with total update time Õ(m^{1/2}n^{3/2}) (when m = n^{1+c} for any constant 0 < c < 1). Prior to our work the fastest algorithm for weighted graphs with approximation at most 3 had total Õ(mn) update time for (1+ε)-APSP [Bernstein, SICOMP 2016]. Our second result is (2+ε, W_{u,v})-APSP with total update time Õ(nm^{3/4}), where the second term is an additive stretch with respect to W_{u,v}, the maximum weight on the shortest path from u to v. Our third result is (2+ε)-APSP for unweighted graphs in Õ(m^{7/4}) update time, which for sparse graphs (m = o(n^{8/7})) is the first subquadratic (2+ε)-approximation. Our last result for unweighted graphs is (1+ε, 2(k-1))-APSP, for k ≥ 2, with Õ(n^{2-1/k}m^{1/k}) total update time (when m = n^{1+c} for any constant c > 0). For comparison, in the special case of (1+ε, 2)-approximation, this improves over the state-of-the-art algorithm by [Henzinger, Krinninger, Nanongkai, SICOMP 2016] with total update time of Õ(n^{2.5}). All of our results are randomized, work against an oblivious adversary, and have constant query time.

Cite as

Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos. New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 58:1-58:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dory_et_al:LIPIcs.ICALP.2024.58,
  author =	{Dory, Michal and Forster, Sebastian and Nazari, Yasamin and de Vos, Tijn},
  title =	{{New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{58:1--58:19},
  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.58},
  URN =		{urn:nbn:de:0030-drops-202012},
  doi =		{10.4230/LIPIcs.ICALP.2024.58},
  annote =	{Keywords: Decremental Shortest Path, All-Pairs Shortest Paths}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.67

Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification

Authors: Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma

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

Abstract

In the Directed Steiner Network problem, the input is a directed graph G, a set T ⊆ V(G) of k terminals, and a demand graph D on T. The task is to find a subgraph H ⊆ G with the minimum number of edges such that for every (s,t) ∈ E(D), the solution H contains a directed s → t path. The goal of this paper is to investigate how the complexity of the problem depends on the demand pattern in planar graphs. Formally, if 𝒟 is a class of directed graphs, then the 𝒟-Steiner Network (𝒟-DSN) problem is the special case where the demand graph D is restricted to be from 𝒟. We give a complete characterization of the behavior of every 𝒟-DSN problem on planar graphs. We classify every class 𝒟 closed under transitive equivalence and identification of vertices into three cases: assuming ETH, either the problem is 1) solvable in time 2^O(k)⋅n^O(1), i.e., FPT parameterized by the number k of terminals, but not solvable in time 2^o(k)⋅n^O(1), 2) solvable in time f(k)⋅n^O(√k), but cannot be solved in time f(k)⋅n^o(√k), or 3) solvable in time f(k)⋅n^O(k), but cannot be solved in time f(k)⋅n^o(k). Our result is a far-reaching generalization and unification of earlier results on Directed Steiner Tree, Directed Steiner Network, and Strongly Connected Steiner Subgraph on planar graphs. As an important step of our lower bound proof, we discover a rare example of a genuinely planar problem (i.e., described by a planar graph and two sets of vertices) that cannot be solved in time f(k)⋅n^o(k): given two sets of terminals S and T with |S|+|T| = k, find a subgraph with minimum number of edges such that every vertex of T is reachable from every vertex of S.

Cite as

Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.ICALP.2024.67,
  author =	{Galby, Esther and Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and Sharma, Roohani},
  title =	{{Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{67:1--67:19},
  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.67},
  URN =		{urn:nbn:de:0030-drops-202104},
  doi =		{10.4230/LIPIcs.ICALP.2024.67},
  annote =	{Keywords: Directed Steiner Network, Sub-exponential algorithm}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.95

Fully Dynamic Strongly Connected Components in Planar Digraphs

Authors: Adam Karczmarz and Marcin Smulewicz

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

Abstract

In this paper we consider maintaining strongly connected components (SCCs) of a directed planar graph subject to edge insertions and deletions. We show a data structure maintaining an implicit representation of the SCCs within Õ(n^{6/7}) worst-case time per update. The data structure supports, in O(log²{n}) time, reporting vertices of any specified SCC (with constant overhead per reported vertex) and aggregating vertex information (e.g., computing the maximum label) over all the vertices of that SCC. Furthermore, it can maintain global information about the structure of SCCs, such as the number of SCCs, or the size of the largest SCC. To the best of our knowledge, no fully dynamic SCCs data structures with sublinear update time have been previously known for any major subclass of digraphs. Our result should be contrasted with the n^{1-o(1)} amortized update time lower bound conditional on SETH, which holds even for dynamically maintaining whether a general digraph has more than two SCCs.

Cite as

Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2024.95,
  author =	{Karczmarz, Adam and Smulewicz, Marcin},
  title =	{{Fully Dynamic Strongly Connected Components in Planar Digraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{95:1--95: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.95},
  URN =		{urn:nbn:de:0030-drops-202388},
  doi =		{10.4230/LIPIcs.ICALP.2024.95},
  annote =	{Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability, planar graphs}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.101

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch

Authors: Tsvi Kopelowitz, Ariel Korin, and Liam Roditty

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

Abstract

For an undirected unweighted graph G = (V,E) with n vertices and m edges, let d(u,v) denote the distance from u ∈ V to v ∈ V in G. An (α,β)-stretch approximate distance oracle (ADO) for G is a data structure that given u,v ∈ V returns in constant (or near constant) time a value dˆ(u,v) such that d(u,v) ≤ dˆ(u,v) ≤ α⋅ d(u,v) + β, for some reals α > 1, β. Thorup and Zwick [Mikkel Thorup and Uri Zwick, 2005] showed that one cannot beat stretch 3 with subquadratic space (in terms of n) for general graphs. Pǎtraşcu and Roditty [Mihai Pǎtraşcu and Liam Roditty, 2010] showed that one can obtain stretch 2 using O(m^{1/3}n^{4/3}) space, and so if m is subquadratic in n then the space usage is also subquadratic. Moreover, Pǎtraşcu and Roditty [Mihai Pǎtraşcu and Liam Roditty, 2010] showed that one cannot beat stretch 2 with subquadratic space even for graphs where m = Õ(n), based on the set-intersection hypothesis. In this paper we explore the conditions for which an ADO can beat stretch 2 while using subquadratic space. In particular, we show that if the maximum degree in G is Δ_G ≤ O(n^{1/k-ε}) for some 0 < ε ≤ 1/k, then there exists an ADO for G that uses Õ(n^{2-(kε)/3) space and has a (2,1-k)-stretch. For k = 2 this result implies a subquadratic sub-2 stretch ADO for graphs with Δ_G ≤ O(n^{1/2-ε}). Moreover, we prove a conditional lower bound, based on the set intersection hypothesis, which states that for any positive integer k ≤ log n, obtaining a sub-(k+2)/k stretch for graphs with Δ_G = Θ(n^{1/k}) requires Ω̃(n²) space. Thus, for graphs with maximum degree Θ(n^{1/2}), obtaining a sub-2 stretch requires Ω̃(n²) space.

Cite as

Tsvi Kopelowitz, Ariel Korin, and Liam Roditty. On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 101:1-101:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kopelowitz_et_al:LIPIcs.ICALP.2024.101,
  author =	{Kopelowitz, Tsvi and Korin, Ariel and Roditty, Liam},
  title =	{{On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{101:1--101:18},
  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.101},
  URN =		{urn:nbn:de:0030-drops-202443},
  doi =		{10.4230/LIPIcs.ICALP.2024.101},
  annote =	{Keywords: Graph algorithms, Approximate distance oracle, data structures, shortest path}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2023.43

Perfect Matchings and Popularity in the Many-To-Many Setting

Authors: Telikepalli Kavitha and Kazuhisa Makino

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract

We consider a matching problem in a bipartite graph G where every vertex has a capacity and a strict preference list ranking its neighbors. We assume that G admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible here and we seek one that is popular within the set of perfect matchings - it is known that such a matching exists in G and can be efficiently computed. Now we are in the weighted setting, i.e., there is a cost function on the edge set, and we seek a min-cost popular perfect matching in G. We show that such a matching can be computed in polynomial time. Our main technical result shows that every popular perfect matching in a hospitals/residents instance G can be realized as a popular perfect matching in the marriage instance obtained by cloning vertices. Interestingly, it is known that such a mapping does not hold for popular matchings in a hospitals/residents instance.

Cite as

Telikepalli Kavitha and Kazuhisa Makino. Perfect Matchings and Popularity in the Many-To-Many Setting. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kavitha_et_al:LIPIcs.FSTTCS.2023.43,
  author =	{Kavitha, Telikepalli and Makino, Kazuhisa},
  title =	{{Perfect Matchings and Popularity in the Many-To-Many Setting}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.43},
  URN =		{urn:nbn:de:0030-drops-194167},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.43},
  annote =	{Keywords: Bipartite graphs, Matchings under preferences, Capacities, Dual certificates}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.54

Popular Edges with Critical Nodes

Authors: Kushagra Chatterjee and Prajakta Nimbhorkar

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

In the popular edge problem, the input is a bipartite graph G = (A ∪ B,E) where A and B denote a set of men and a set of women respectively, and each vertex in A∪ B has a strict preference ordering over its neighbours. A matching M in G is said to be popular if there is no other matching M' such that the number of vertices that prefer M' to M is more than the number of vertices that prefer M to M'. The goal is to determine, whether a given edge e belongs to some popular matching in G. A polynomial-time algorithm for this problem appears in [Cseh and Kavitha, 2018]. We consider the popular edge problem when some men or women are prioritized or critical. A matching that matches all the critical nodes is termed as a feasible matching. It follows from [Telikepalli Kavitha, 2014; Kavitha, 2021; Nasre et al., 2021; Meghana Nasre and Prajakta Nimbhorkar, 2017] that, when G admits a feasible matching, there always exists a matching that is popular among all feasible matchings. We give a polynomial-time algorithm for the popular edge problem in the presence of critical men or women. We also show that an analogous result does not hold in the many-to-one setting, which is known as the Hospital-Residents Problem in literature, even when there are no critical nodes.

Cite as

Kushagra Chatterjee and Prajakta Nimbhorkar. Popular Edges with Critical Nodes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ISAAC.2022.54,
  author =	{Chatterjee, Kushagra and Nimbhorkar, Prajakta},
  title =	{{Popular Edges with Critical Nodes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.54},
  URN =		{urn:nbn:de:0030-drops-173399},
  doi =		{10.4230/LIPIcs.ISAAC.2022.54},
  annote =	{Keywords: Matching, Stable Matching, Popular feasible Matching}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2022.22

Stable Matchings with One-Sided Ties and Approximate Popularity

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract

We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices in A rank their neighbors in a strict order of preference while vertices in B are allowed to have weak rankings, i.e., ties are allowed in their preferences. Stable matchings always exist in G and are easy to find, however popular matchings need not exist and it is NP-complete to decide if one exists. This motivates the "approximately popular" matching problem. A well-known measure of approximate popularity is low unpopularity factor. We show that when each tie in G has length at most k, there always exists a stable matching whose unpopularity factor is at most k. Our proof is algorithmic and we compute such a stable matching in polynomial time. Our result can be considered to be a generalization of Gärdenfors' result (1975) which showed that when rankings are strict, every stable matching is popular. There are several applications where the size of the matching is its most important attribute. What one seeks here is a maximum matching M such that there is no maximum matching more popular than M. When rankings are weak, it is NP-hard to decide if G admits such a matching. When ties are one-sided and of length at most k, we show a polynomial time algorithm to find a maximum matching whose unpopularity factor within the set of maximum matchings is at most 2k.

Cite as

Telikepalli Kavitha. Stable Matchings with One-Sided Ties and Approximate Popularity. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.FSTTCS.2022.22,
  author =	{Kavitha, Telikepalli},
  title =	{{Stable Matchings with One-Sided Ties and Approximate Popularity}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.22},
  URN =		{urn:nbn:de:0030-drops-174144},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.22},
  annote =	{Keywords: Bipartite graphs, Maximum matchings, Unpopularity factor}
}

Document

DOI: 10.4230/LIPIcs.STACS.2022.41

Fairly Popular Matchings and Optimality

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract

We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices have strict preferences over their neighbors. A matching M is popular if for any matching N, the number of vertices that prefer M is at least the number that prefer N; thus M does not lose a head-to-head election against any matching where vertices are voters. It is easy to find popular matchings; however when there are edge costs, it is NP-hard to find (or even approximate) a min-cost popular matching. This hardness motivates relaxations of popularity. Here we introduce fairly popular matchings. A fairly popular matching may lose elections but there is no good matching (wrt popularity) that defeats a fairly popular matching. In particular, any matching that defeats a fairly popular matching does not occur in the support of any popular mixed matching. We show that a min-cost fairly popular matching can be computed in polynomial time and the fairly popular matching polytope has a compact extended formulation. We also show the following hardness result: given a matching M, it is NP-complete to decide if there exists a popular matching that defeats M. Interestingly, there exists a set K of at most m popular matchings in G (where |E| = m) such that if a matching is defeated by some popular matching in G then it has to be defeated by one of the matchings in K.

Cite as

Telikepalli Kavitha. Fairly Popular Matchings and Optimality. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.STACS.2022.41,
  author =	{Kavitha, Telikepalli},
  title =	{{Fairly Popular Matchings and Optimality}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{41:1--41:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.41},
  URN =		{urn:nbn:de:0030-drops-158516},
  doi =		{10.4230/LIPIcs.STACS.2022.41},
  annote =	{Keywords: Bipartite graphs, Stable matchings, Mixed matchings, Polytopes}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2021.25

Matchings, Critical Nodes, and Popular Solutions

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract

We consider a matching problem in a marriage instance G. Every node has a strict preference order ranking its neighbors. There is a set C of prioritized or critical nodes and we are interested in only those matchings that match as many critical nodes as possible. Such matchings are useful in several applications and we call them critical matchings. A stable matching need not be critical. We consider a well-studied relaxation of stability called popularity. Our goal is to find a popular critical matching, i.e., a weak Condorcet winner within the set of critical matchings where nodes are voters. We show that popular critical matchings always exist in G and min-size/max-size such matchings can be efficiently computed.

Cite as

Telikepalli Kavitha. Matchings, Critical Nodes, and Popular Solutions. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.FSTTCS.2021.25,
  author =	{Kavitha, Telikepalli},
  title =	{{Matchings, Critical Nodes, and Popular Solutions}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.25},
  URN =		{urn:nbn:de:0030-drops-155360},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.25},
  annote =	{Keywords: Bipartite graphs, Stable matchings, LP-duality}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2021.85

Maximum Matchings and Popularity

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract

Let G be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching M in G is a popular max-matching if for any maximum matching N in G, the number of nodes that prefer M is at least the number that prefer N. Popular max-matchings always exist in G and they are relevant in applications where the size of the matching is of higher priority than node preferences. Here we assume there is also a cost function on the edge set. So what we seek is a min-cost popular max-matching. Our main result is that such a matching can be computed in polynomial time. We show a compact extended formulation for the popular max-matching polytope and the algorithmic result follows from this. In contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard.

Cite as

Telikepalli Kavitha. Maximum Matchings and Popularity. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 85:1-85:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.ICALP.2021.85,
  author =	{Kavitha, Telikepalli},
  title =	{{Maximum Matchings and Popularity}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{85:1--85:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.85},
  URN =		{urn:nbn:de:0030-drops-141548},
  doi =		{10.4230/LIPIcs.ICALP.2021.85},
  annote =	{Keywords: Bipartite graphs, Popular matchings, Stable matchings, Dual certificates}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2020.25

Min-Cost Popular Matchings

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract

Let G = (A ∪ B, E) be a bipartite graph on n vertices where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if there is no matching N such that vertices that prefer N to M outnumber those that prefer M to N. Popular matchings always exist in G since every stable matching is popular. Thus it is easy to find a popular matching in G - however it is NP-hard to compute a min-cost popular matching in G when there is a cost function on the edge set; moreover it is NP-hard to approximate this to any multiplicative factor. An O^*(2ⁿ) algorithm to compute a min-cost popular matching in G follows from known results. Here we show: - an algorithm with running time O^*(2^{n/4}) ≈ O^*(1.19ⁿ) to compute a min-cost popular matching; - assume all edge costs are non-negative - then given ε > 0, a randomized algorithm with running time poly(n,1/(ε)) to compute a matching M such that cost(M) is at most twice the optimal cost and with high probability, the fraction of all matchings more popular than M is at most 1/2+ε.

Cite as

Telikepalli Kavitha. Min-Cost Popular Matchings. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.FSTTCS.2020.25,
  author =	{Kavitha, Telikepalli},
  title =	{{Min-Cost Popular Matchings}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.25},
  URN =		{urn:nbn:de:0030-drops-132668},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.25},
  annote =	{Keywords: Bipartite graphs, Stable matchings, Dual certificates}
}

76 Search Results for "Telikepalli, Kavitha"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as