Search Results

Documents authored by Louis, Anand

Document
DOI: 10.4230/LIPIcs.SWAT.2024.33
Sparse Cuts in Hypergraphs from Random Walks on Simplicial Complexes

Authors: Anand Louis, Rameesh Paul, and Arka Ray

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
There are a lot of recent works on generalizing the spectral theory of graphs and graph partitioning to k-uniform hypergraphs. There have been two broad directions toward this goal. One generalizes the notion of graph conductance to hypergraph conductance [Louis, Makarychev - TOC'16; Chan, Louis, Tang, Zhang - JACM'18]. In the second approach, one can view a hypergraph as a simplicial complex and study its various topological properties [Linial, Meshulam - Combinatorica'06; Meshulam, Wallach - RSA'09; Dotterrer, Kaufman, Wagner - SoCG'16; Parzanchevski, Rosenthal - RSA'17] and spectral properties [Kaufman, Mass - ITCS'17; Dinur, Kaufman - FOCS'17; Kaufman, Openheim - STOC'18; Oppenheim - DCG'18; Kaufman, Openheim - Combinatorica'20]. In this work, we attempt to bridge these two directions of study by relating the spectrum of up-down walks and swap walks on the simplicial complex, a downward closed set system, to hypergraph expansion. More precisely, we study the simplicial complex obtained by downward closing the given hypergraph and random walks between its levels X(l), i.e., the sets of cardinality l. In surprising contrast to random walks on graphs, we show that the spectral gap of swap walks and up-down walks between level m and l with 1 < m ⩽ l cannot be used to infer any bounds on hypergraph conductance. Moreover, we show that the spectral gap of swap walks between X(1) and X(k-1) cannot be used to infer any bounds on hypergraph conductance. In contrast, we give a Cheeger-like inequality relating the spectra of walks between level 1 and l for any l ⩽ k to hypergraph expansion. This is a surprising difference between swaps walks and up-down walks! Finally, we also give a construction to show that the well-studied notion of link expansion in simplicial complexes cannot be used to bound hypergraph expansion in a Cheeger-like manner.
Cite as

Anand Louis, Rameesh Paul, and Arka Ray. Sparse Cuts in Hypergraphs from Random Walks on Simplicial Complexes. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.SWAT.2024.33,
  author =	{Louis, Anand and Paul, Rameesh and Ray, Arka},
  title =	{{Sparse Cuts in Hypergraphs from Random Walks on Simplicial Complexes}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.33},
  URN =		{urn:nbn:de:0030-drops-200739},
  doi =		{10.4230/LIPIcs.SWAT.2024.33},
  annote =	{Keywords: Sparse Cuts, Random Walks, Link Expansion, Hypergraph Expansion, Simplicial Complexes, High Dimensional Expander, Threshold Rank}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.43
Approximating CSPs with Outliers

Authors: Suprovat Ghoshal and Anand Louis

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

Abstract
Constraint satisfaction problems (CSPs) are ubiquitous in theoretical computer science. We study the problem of Strong-CSP s, i.e. instances where a large induced sub-instance has a satisfying assignment. More formally, given a CSP instance 𝒢(V, E, [k], {Π_{ij}}_{(i,j) ∈ E}) consisting of a set of vertices V, a set of edges E, alphabet [k], a constraint Π_{ij} ⊂ [k] × [k] for each (i,j) ∈ E, the goal of this problem is to compute the largest subset S ⊆ V such that the instance induced on S has an assignment that satisfies all the constraints. In this paper, we study approximation algorithms for UniqueGames and related problems under the Strong-CSP framework when the underlying constraint graph satisfies mild expansion properties. In particular, we show that given a StrongUniqueGames instance whose optimal solution S^* is supported on a regular low threshold rank graph, there exists an algorithm that runs in time exponential in the threshold rank, and recovers a large satisfiable sub-instance whose size is independent on the label set size and maximum degree of the graph. Our algorithm combines the techniques of Barak-Raghavendra-Steurer (FOCS'11), Guruswami-Sinop (FOCS'11) with several new ideas and runs in time exponential in the threshold rank of the optimal set. A key component of our algorithm is a new threshold rank based spectral decomposition, which is used to compute a "large" induced subgraph of "small" threshold rank; our techniques build on the work of Oveis Gharan and Rezaei (SODA'17), and could be of independent interest.
Cite as

Suprovat Ghoshal and Anand Louis. Approximating CSPs with Outliers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ghoshal_et_al:LIPIcs.APPROX/RANDOM.2022.43,
  author =	{Ghoshal, Suprovat and Louis, Anand},
  title =	{{Approximating CSPs with Outliers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.43},
  URN =		{urn:nbn:de:0030-drops-171656},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.43},
  annote =	{Keywords: Constraint Satisfaction Problems, Strong Unique Games, Threshold Rank}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.84
Exact Recovery Algorithm for Planted Bipartite Graph in Semi-Random Graphs

Authors: Akash Kumar, Anand Louis, and Rameesh Paul

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The problem of finding the largest induced balanced bipartite subgraph in a given graph is NP-hard. This problem is closely related to the problem of finding the smallest Odd Cycle Transversal. In this work, we consider the following model of instances: starting with a set of vertices V, a set S ⊆ V of k vertices is chosen and an arbitrary d-regular bipartite graph is added on it; edges between pairs of vertices in S× (V⧵S) and (V⧵S) × (V⧵S) are added with probability p. Since for d = 0, the problem reduces to recovering a planted independent set, we don't expect efficient algorithms for k = o(√n). This problem is a generalization of the planted balanced biclique problem where the bipartite graph induced on S is a complete bipartite graph; [Yevgeny Levanzov, 2018] gave an algorithm for recovering S in this problem when k = Ω(√n). Our main result is an efficient algorithm that recovers (w.h.p.) the planted bipartite graph when k = Ω_p(√{n log n}) for a large range of parameters. Our results also hold for a natural semi-random model of instances, which involve the presence of a monotone adversary. Our proof shows that a natural SDP relaxation for the problem is integral by constructing an appropriate solution to it’s dual formulation. Our main technical contribution is a new approach for construction the dual solution where we calibrate the eigenvectors of the adjacency matrix to be the eigenvectors of the dual matrix. We believe that this approach may have applications to other recovery problems in semi-random models as well. When k = Ω(√n), we give an algorithm for recovering S whose running time is exponential in the number of small eigenvalues in graph induced on S; this algorithm is based on subspace enumeration techniques due to the works of [Alexandra Kolla and Madhur Tulsiani, 2007; Arora et al., 2010; Kolla, 2011].
Cite as

Akash Kumar, Anand Louis, and Rameesh Paul. Exact Recovery Algorithm for Planted Bipartite Graph in Semi-Random Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 84:1-84:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.ICALP.2022.84,
  author =	{Kumar, Akash and Louis, Anand and Paul, Rameesh},
  title =	{{Exact Recovery Algorithm for Planted Bipartite Graph in Semi-Random Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{84:1--84:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.84},
  URN =		{urn:nbn:de:0030-drops-164251},
  doi =		{10.4230/LIPIcs.ICALP.2022.84},
  annote =	{Keywords: SDP duality, Planted models, Semi-random models, Exact recovery, Threshold rank, Spectral embedding, Subspace enumeration}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.27
Planted Models for the Densest k-Subgraph Problem

Authors: Yash Khanna and Anand Louis

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

Abstract
Given an undirected graph G, the Densest k-subgraph problem (DkS) asks to compute a set S ⊂ V of cardinality |S| ≤ k such that the weight of edges inside S is maximized. This is a fundamental NP-hard problem whose approximability, inspite of many decades of research, is yet to be settled. The current best known approximation algorithm due to Bhaskara et al. (2010) computes a 𝒪(n^{1/4 + ε}) approximation in time n^{𝒪(1/ε)}, for any ε > 0. We ask what are some "easier" instances of this problem? We propose some natural semi-random models of instances with a planted dense subgraph, and study approximation algorithms for computing the densest subgraph in them. These models are inspired by the semi-random models of instances studied for various other graph problems such as the independent set problem, graph partitioning problems etc. For a large range of parameters of these models, we get significantly better approximation factors for the Densest k-subgraph problem. Moreover, our algorithm recovers a large part of the planted solution.
Cite as

Yash Khanna and Anand Louis. Planted Models for the Densest k-Subgraph Problem. 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. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.FSTTCS.2020.27,
  author =	{Khanna, Yash and Louis, Anand},
  title =	{{Planted Models for the Densest k-Subgraph Problem}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{27:1--27:18},
  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.27},
  URN =		{urn:nbn:de:0030-drops-132682},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.27},
  annote =	{Keywords: Densest k-Subgraph, Semi-Random models, Planted Models, Semidefinite Programming, Approximation Algorithms, Beyond Worst Case Analysis}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.23
Planted Models for k-Way Edge and Vertex Expansion

Authors: Anand Louis and Rakesh Venkat

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a 2-partition of the vertex set of the graph that minimizes the considered objective. However, for many natural applications, one might require a graph to be partitioned into k parts, for some k >=slant 2. For a k-partition S_1, ..., S_k of the vertex set of a graph G = (V,E), the k-way edge expansion (resp. vertex expansion) of {S_1, ..., S_k} is defined as max_{i in [k]} Phi(S_i), and the balanced k-way edge expansion (resp. vertex expansion) of G is defined as min_{{S_1, ..., S_k} in P_k} max_{i in [k]} Phi(S_i) , where P_k is the set of all balanced k-partitions of V (i.e each part of a k-partition in P_k should have cardinality |V|/k), and Phi(S) denotes the edge expansion (resp. vertex expansion) of S subset V. We study a natural planted model for graphs where the vertex set of a graph has a k-partition S_1, ..., S_k such that the graph induced on each S_i has large expansion, but each S_i has small edge expansion (resp. vertex expansion) in the graph. We give bi-criteria approximation algorithms for computing the balanced k-way edge expansion (resp. vertex expansion) of instances in this planted model.
Cite as

Anand Louis and Rakesh Venkat. Planted Models for k-Way Edge and Vertex Expansion. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.FSTTCS.2019.23,
  author =	{Louis, Anand and Venkat, Rakesh},
  title =	{{Planted Models for k-Way Edge and Vertex Expansion}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.23},
  URN =		{urn:nbn:de:0030-drops-115857},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.23},
  annote =	{Keywords: Vertex Expansion, k-way partitioning, Semi-Random models, Planted Models, Approximation Algorithms, Beyond Worst Case Analysis}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.28
Approximation Algorithms for Partially Colorable Graphs

Authors: Suprovat Ghoshal, Anand Louis, and Rahul Raychaudhury

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

Abstract
Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For alpha <= 1 and k in Z^+, we say that a graph G=(V,E) is alpha-partially k-colorable, if there exists a subset S subset V of cardinality |S| >= alpha |V| such that the graph induced on S is k-colorable. Partial k-colorability is a more robust structural property of a graph than k-colorability. For graphs that arise in practice, partial k-colorability might be a better notion to use than k-colorability, since data arising in practice often contains various forms of noise. We give a polynomial time algorithm that takes as input a (1 - epsilon)-partially 3-colorable graph G and a constant gamma in [epsilon, 1/10], and colors a (1 - epsilon/gamma) fraction of the vertices using O~(n^{0.25 + O(gamma^{1/2})}) colors. We also study natural semi-random families of instances of partially 3-colorable graphs and partially 2-colorable graphs, and give stronger bi-criteria approximation guarantees for these family of instances.
Cite as

Suprovat Ghoshal, Anand Louis, and Rahul Raychaudhury. Approximation Algorithms for Partially Colorable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ghoshal_et_al:LIPIcs.APPROX-RANDOM.2019.28,
  author =	{Ghoshal, Suprovat and Louis, Anand and Raychaudhury, Rahul},
  title =	{{Approximation Algorithms for Partially Colorable Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.28},
  URN =		{urn:nbn:de:0030-drops-112438},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.28},
  annote =	{Keywords: Approximation Algorithms, Vertex Coloring, Semi-random Models}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.101
Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery

Authors: Anand Louis and Rakesh Venkat

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph are a O(sqrt{log n})-approximation algorithm due to Feige et al. [Uriel Feige et al., 2008], and O(sqrt{OPT log d}) bound in graphs having vertex degrees at most d due to Louis et al. [Louis et al., 2013]. We study a natural semi-random model of graphs with sparse vertex cuts. For certain ranges of parameters, we give an algorithm to recover the planted sparse vertex cut exactly. For a larger range of parameters, we give a constant factor bi-criteria approximation algorithm to compute the graph's balanced vertex expansion. Our algorithms are based on studying a semidefinite programming relaxation for the balanced vertex expansion of the graph. In addition to being a family of instances that will help us to better understand the complexity of the computation of vertex expansion, our model can also be used in the study of community detection where only a few nodes from each community interact with nodes from other communities. There has been a lot of work on studying random and semi-random graphs with planted sparse edge cuts. To the best of our knowledge, our model of semi-random graphs with planted sparse vertex cuts has not been studied before.
Cite as

Anand Louis and Rakesh Venkat. Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 101:1-101:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.ICALP.2018.101,
  author =	{Louis, Anand and Venkat, Rakesh},
  title =	{{Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{101:1--101:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.101},
  URN =		{urn:nbn:de:0030-drops-91057},
  doi =		{10.4230/LIPIcs.ICALP.2018.101},
  annote =	{Keywords: Semi-Random models, Vertex Expansion, Approximation Algorithms, Beyond Worst Case Analysis}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.37
Finding Pseudorandom Colorings of Pseudorandom Graphs

Authors: Akash Kumar, Anand Louis, and Madhur Tulsiani

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
We consider the problem of recovering a planted pseudorandom 3-coloring in expanding and low threshold-rank graphs. Alon and Kahale [SICOMP 1997] gave a spectral algorithm to recover the coloring for a random graph with a planted random 3-coloring. We show that their analysis can be adapted to work when coloring is pseudorandom i.e., all color classes are of equal size and the size of the intersection of the neighborhood of a random vertex with each color class has small variance. We also extend our results to partial colorings and low threshold-rank graphs to show the following: * For graphs on n vertices with threshold-rank r, for which there exists a 3-coloring that is eps-pseudorandom and properly colors the induced subgraph on (1-gamma)n vertices, we show how to recover the coloring for (1 - O(gamma + eps)) n vertices in time (rn)^{O(r)}. * For expanding graphs on n vertices, which admit a pseudorandom 3-coloring properly coloring all the vertices, we show how to recover such a coloring in polynomial time. Our results are obtained by combining the method of Alon and Kahale, with eigenspace enumeration methods used for solving constraint satisfaction problems on low threshold-rank graphs.
Cite as

Akash Kumar, Anand Louis, and Madhur Tulsiani. Finding Pseudorandom Colorings of Pseudorandom Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 37:1-37:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.FSTTCS.2017.37,
  author =	{Kumar, Akash and Louis, Anand and Tulsiani, Madhur},
  title =	{{Finding Pseudorandom Colorings of Pseudorandom Graphs}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{37:1--37:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.37},
  URN =		{urn:nbn:de:0030-drops-83956},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.37},
  annote =	{Keywords: Graph Coloring, Expanders, Spectral algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.339
Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion

Authors: Anand Louis and Yury Makarychev

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

Abstract
The expansion of a hypergraph, a natural extension of the notion of expansion in graphs, is defined as the minimum over all cuts in the hypergraph of the ratio of the number of the hyperedges cut to the size of the smaller side of the cut. We study the Hypergraph Small Set Expansion problem, which, for a parameter 's' such that 0 < s < 1/2, asks to compute the cut having the least expansion while having at most 's' fraction of the vertices on the smaller side of the cut. We present two algorithms. Our first algorithm gives a multiplicative polylogarithmic approximation. Our second algorithm gives a bound that is a function of the expansion of the hypergraph but is independent of the size of the hypergraph. Using these results, we also obtain similar guarantees for the Small Set Vertex Expansion problem.
Cite as

Anand Louis and Yury Makarychev. Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 339-355, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.APPROX-RANDOM.2014.339,
  author =	{Louis, Anand and Makarychev, Yury},
  title =	{{Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{339--355},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.339},
  URN =		{urn:nbn:de:0030-drops-47079},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.339},
  annote =	{Keywords: Approximation Algorithms, Graph Expansion, Hypergraph Expansion, Vertex Expansion}
}
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