12 Search Results for "Koutis, Ioannis"

Document
DOI: 10.4230/LIPIcs.STACS.2026.38
Fully Dynamic Spectral Sparsification for Directed Hypergraphs

Authors: Sebastian Forster, Gramoz Goranci, and Ali Momeni

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of directed hypergraphs. Our algorithm achieves a near-optimal size of O(n² / ε ² log ⁷ m) and amortized update time of O(r² log ³ m), where n is the number of vertices, and m and r respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any k hyperedge insertions or deletions can be processed with O(kr² log ³ m) amortized work and O(log ² m) depth. This constitutes the first spectral-based sparsification algorithm in this setting.
Cite as

Sebastian Forster, Gramoz Goranci, and Ali Momeni. Fully Dynamic Spectral Sparsification for Directed Hypergraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.STACS.2026.38,
  author =	{Forster, Sebastian and Goranci, Gramoz and Momeni, Ali},
  title =	{{Fully Dynamic Spectral Sparsification for Directed Hypergraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.38},
  URN =		{urn:nbn:de:0030-drops-255272},
  doi =		{10.4230/LIPIcs.STACS.2026.38},
  annote =	{Keywords: Spectral sparsification, Dynamic algorithms, (Directed) hypergraphs, Data structures}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.60
Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation

Authors: Yannic Maus and Tijn de Vos

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We give new, improved bounds for approximating the sparsest cut value or in other words the conductance ϕ of a graph in the CONGEST model. As our main result, we present an algorithm running in O(log² n/ϕ) rounds in which every vertex outputs a value ̃ ϕ satisfying ϕ ≤ ̃ ϕ ≤ √{2.01ϕ}. In most regimes, our algorithm improves significantly over the previously fastest algorithm for the problem [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to k-way conductance. We obtain these results, by approximating the eigenvalues of the normalized Laplacian matrix L: = I-Deg^{-1/2}ADeg^ {-1/2}, where, A is the adjacency matrix and Deg is the diagonal matrix with the weighted degrees on the diagonal. We show our algorithms are near-optimal by proving a lower bound for computing the smallest non-trivial eigenvalue of L, even in the stronger LOCAL model The previous state of the art sparsest cut algorithm is in the technical realm of expander decompositions. Our algorithms, on the other hand, are relatively simple and easy to implement. At the core, they rely on the well-known power method, which comes down to repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the CONGEST model. All our algorithms apply to weighted, undirected graphs. Our lower bounds apply even in unweighted graphs.
Cite as

Yannic Maus and Tijn de Vos. Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 60:1-60:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{maus_et_al:LIPIcs.DISC.2025.60,
  author =	{Maus, Yannic and de Vos, Tijn},
  title =	{{Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{60:1--60:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.60},
  URN =		{urn:nbn:de:0030-drops-248763},
  doi =		{10.4230/LIPIcs.DISC.2025.60},
  annote =	{Keywords: CONGEST, Sparsest Cut, Laplacian, Eigenvalues, Spectral Graph Theory}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.92
Fully Dynamic Algorithms for Transitive Reduction

Authors: Gramoz Goranci, Adam Karczmarz, Ali Momeni, and Nikos Parotsidis

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Given a directed graph G, a transitive reduction G^t of G (first studied by Aho, Garey, Ullman [SICOMP `72]) is a minimal subgraph of G that preserves the reachability relation between every two vertices in G. In this paper, we study the computational complexity of transitive reduction in the dynamic setting. We obtain the first fully dynamic algorithms for maintaining a transitive reduction of a general directed graph undergoing updates such as edge insertions or deletions. Our first algorithm achieves O(m+n log n) amortized update time, which is near-optimal for sparse directed graphs, and can even support extended update operations such as inserting a set of edges all incident to the same vertex, or deleting an arbitrary set of edges. Our second algorithm relies on fast matrix multiplication and achieves O(m+ n^{1.585}) worst-case update time.
Cite as

Gramoz Goranci, Adam Karczmarz, Ali Momeni, and Nikos Parotsidis. Fully Dynamic Algorithms for Transitive Reduction. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 92:1-92:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{goranci_et_al:LIPIcs.ICALP.2025.92,
  author =	{Goranci, Gramoz and Karczmarz, Adam and Momeni, Ali and Parotsidis, Nikos},
  title =	{{Fully Dynamic Algorithms for Transitive Reduction}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{92:1--92:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.92},
  URN =		{urn:nbn:de:0030-drops-234697},
  doi =		{10.4230/LIPIcs.ICALP.2025.92},
  annote =	{Keywords: Spectral sparsification, Dynamic algorithms, (Directed) hypergraphs, Data structures}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.35
Near-Optimal Directed Low-Diameter Decompositions

Authors: Karl Bringmann, Nick Fischer, Bernhard Haeupler, and Rustam Latypov

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Low Diameter Decompositions (LDDs) are invaluable tools in the design of combinatorial graph algorithms. While historically they have been applied mainly to undirected graphs, in the recent breakthrough for the negative-length Single Source Shortest Path problem, Bernstein, Nanongkai, and Wulff-Nilsen [FOCS '22] extended the use of LDDs to directed graphs for the first time. Specifically, their LDD deletes each edge with probability at most O(1/D ⋅ log²n), while ensuring that each strongly connected component in the remaining graph has a (weak) diameter of at most D. In this work, we make further advancements in the study of directed LDDs. We reveal a natural and intuitive (in hindsight) connection to Expander Decompositions, and leveraging this connection along with additional techniques, we establish the existence of an LDD with an edge-cutting probability of O(1/D ⋅ log n log log n). This improves the previous bound by nearly a logarithmic factor and closely approaches the lower bound of Ω(1/D ⋅ log n). With significantly more technical effort, we also develop two efficient algorithms for computing our LDDs: a deterministic algorithm that runs in time Õ(m poly(D)) and a randomized algorithm that runs in near-linear time Õ(m). We believe that our work provides a solid conceptual and technical foundation for future research relying on directed LDDs, which will undoubtedly follow soon.
Cite as

Karl Bringmann, Nick Fischer, Bernhard Haeupler, and Rustam Latypov. Near-Optimal Directed Low-Diameter Decompositions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ICALP.2025.35,
  author =	{Bringmann, Karl and Fischer, Nick and Haeupler, Bernhard and Latypov, Rustam},
  title =	{{Near-Optimal Directed Low-Diameter Decompositions}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.35},
  URN =		{urn:nbn:de:0030-drops-234125},
  doi =		{10.4230/LIPIcs.ICALP.2025.35},
  annote =	{Keywords: Low Diameter Decompositions, Expander Decompositions, Directed Graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.72
k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5

Authors: Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye, and Adrian Vetta

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
A graph G = (V,E) is a k-leaf power if there is a tree T whose leaves are the vertices of G, with the property that a pair of distinct leaves u and v share an edge in G if and only if they are distance at most k apart in T. For k ≤ 4, it is known that there exists a finite set F_k of graphs such that the class ℒ(k) of k-leaf power graphs is characterized as the set of strongly chordal graphs that do not contain any graph in F_k as an induced subgraph. We prove no such characterization holds for k ≥ 5. That is, for any k ≥ 5, there is no finite set F_k of graphs such that ℒ(k) is equivalent to the set of strongly chordal graphs that do not contain as an induced subgraph any graph in F_k.
Cite as

Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye, and Adrian Vetta. k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 72:1-72:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{duprelatour_et_al:LIPIcs.ICALP.2025.72,
  author =	{Dupr\'{e} la Tour, Max and Lafond, Manuel and Ndiaye, Ndiam\'{e} and Vetta, Adrian},
  title =	{{k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{72:1--72:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.72},
  URN =		{urn:nbn:de:0030-drops-234499},
  doi =		{10.4230/LIPIcs.ICALP.2025.72},
  annote =	{Keywords: Leaf Powers, Forbidden Graph Characterizations, Strongly Chordal Graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.45
Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs

Authors: Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We consider the distributed and parallel construction of low-diameter decompositions with strong diameter. We present algorithms for arbitrary undirected, weighted graphs and also for undirected, weighted graphs that can be separated through k ∈ Õ(1) shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor K_r. Our algorithms work in the PRAM, CONGEST, and the novel HYBRID communication model and are competitive in all relevant parameters. Given 𝒟 > 0, our low-diameter decomposition algorithm divides the graph into connected clusters of strong diameter 𝒟. For an arbitrary graph, an edge e ∈ E of length 𝓁_e is cut between two clusters with probability O(𝓁_e⋅log(n)/𝒟). If the graph can be separated by k ∈ Õ(1) paths, the probability improves to O(𝓁_e⋅log(log n)/𝒟). In either case, the decompositions can be computed in Õ(1) depth and Õ(m) work in the PRAM and Õ(1) time in the HYBRID model. In CONGEST, the runtimes are Õ(HD + √n) and Õ(HD) respectively. All these results hold w.h.p. Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replace exact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting [STOC '22]. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficient parallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Thereby, we do not require complex embeddings whose implementation is unknown in the distributed and parallel setting.
Cite as

Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann. Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 45:1-45:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dou_et_al:LIPIcs.ITCS.2025.45,
  author =	{Dou, Jinfeng and G\"{o}tte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian},
  title =	{{Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{45:1--45:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.45},
  URN =		{urn:nbn:de:0030-drops-226734},
  doi =		{10.4230/LIPIcs.ITCS.2025.45},
  annote =	{Keywords: Distributed Graph Algorithms, Network Decomposition, Excluded Minor}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.31
Sidestepping Barriers for Dominating Set in Parameterized Complexity

Authors: Ioannis Koutis, Michał Włodarczyk, and Meirav Zehavi

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We study the classic Dominating Set problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterization. Our results span several parameterization regimes, including: (i,ii,iii) time/ratio-tradeoff for the parameters treewidth, vertex modulator to constant treewidth and solution size; (iv,v) FPT-algorithms for the parameters vertex cover number and feedback edge set number; and (vi) compression for the parameter feedback edge set number.
Cite as

Ioannis Koutis, Michał Włodarczyk, and Meirav Zehavi. Sidestepping Barriers for Dominating Set in Parameterized Complexity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{koutis_et_al:LIPIcs.IPEC.2023.31,
  author =	{Koutis, Ioannis and W{\l}odarczyk, Micha{\l} and Zehavi, Meirav},
  title =	{{Sidestepping Barriers for Dominating Set in Parameterized Complexity}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.31},
  URN =		{urn:nbn:de:0030-drops-194506},
  doi =		{10.4230/LIPIcs.IPEC.2023.31},
  annote =	{Keywords: Dominating Set, Parameterized Complexity, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.9
Fast Exact Algorithms Using Hadamard Product of Polynomials

Authors: V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay

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

Abstract
Let C be an arithmetic circuit of poly(n) size given as input that computes a polynomial f in F[X], where X={x_1,x_2,...,x_n} and F is any field where the field arithmetic can be performed efficiently. We obtain new algorithms for the following two problems first studied by Koutis and Williams [Ioannis Koutis, 2008; Ryan Williams, 2009; Ioannis Koutis and Ryan Williams, 2016]. - (k,n)-MLC: Compute the sum of the coefficients of all degree-k multilinear monomials in the polynomial f. - k-MMD: Test if there is a nonzero degree-k multilinear monomial in the polynomial f. Our algorithms are based on the fact that the Hadamard product f o S_{n,k}, is the degree-k multilinear part of f, where S_{n,k} is the k^{th} elementary symmetric polynomial. - For (k,n)-MLC problem, we give a deterministic algorithm of run time O^*(n^(k/2+c log k)) (where c is a constant), answering an open question of Koutis and Williams [Ioannis Koutis and Ryan Williams, 2016]. As corollaries, we show O^*(binom{n}{downarrow k/2})-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating Set, m-Dimensional k-Matching. - For k-MMD problem, we give a randomized algorithm of run time 4.32^k * poly(n,k). Our algorithm uses only poly(n,k) space. This matches the run time of a recent algorithm [Cornelius Brand et al., 2018] for k-MMD which requires exponential (in k) space. Other results include fast deterministic algorithms for (k,n)-MLC and k-MMD problems for depth three circuits.
Cite as

V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Fast Exact Algorithms Using Hadamard Product of Polynomials. 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. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2019.9,
  author =	{Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha},
  title =	{{Fast Exact Algorithms Using Hadamard Product of Polynomials}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{9:1--9:14},
  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.9},
  URN =		{urn:nbn:de:0030-drops-115711},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.9},
  annote =	{Keywords: Hadamard Product, Multilinear Monomial Detection and Counting, Rectangular Permanent, Symmetric Polynomial}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.25
Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors

Authors: Andreas Björklund and Ryan Williams

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We show that the permanent of an n x n matrix over any finite ring of r <= n elements can be computed with a deterministic 2^{n-Omega(n/r)} time algorithm. This improves on a Las Vegas algorithm running in expected 2^{n-Omega(n/(r log r))} time, implicit in [Björklund, Husfeldt, and Lyckberg, IPL 2017]. For the permanent over the integers of a 0/1-matrix with exactly d ones per row and column, we provide a deterministic 2^{n-Omega(n/(d^{3/4)})} time algorithm. This improves on a 2^{n-Omega(n/d)} time algorithm in [Cygan and Pilipczuk ICALP 2013]. We also show that the number of Hamiltonian cycles in an n-vertex directed graph of average degree delta can be computed by a deterministic 2^{n-Omega(n/(delta))} time algorithm. This improves on a Las Vegas algorithm running in expected 2^{n-Omega(n/poly(delta))} time in [Björklund, Kaski, and Koutis, ICALP 2017]. A key tool in our approach is a reduction from computing the permanent to listing pairs of dissimilar vectors from two sets of vectors, i.e., vectors over a finite set that differ in each coordinate, building on an observation of [Bax and Franklin, Algorithmica 2002]. We propose algorithms that can be used both to derandomise the construction of Bax and Franklin, and efficiently list dissimilar pairs using several algorithmic tools. We also give a simple randomised algorithm resulting in Monte Carlo algorithms within the same time bounds. Our new fast algorithms for listing dissimilar vector pairs from two sets of vectors are inspired by recent algorithms for detecting and counting orthogonal vectors by [Abboud, Williams, and Yu, SODA 2015] and [Chan and Williams, SODA 2016].
Cite as

Andreas Björklund and Ryan Williams. Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2019.25,
  author =	{Bj\"{o}rklund, Andreas and Williams, Ryan},
  title =	{{Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.25},
  URN =		{urn:nbn:de:0030-drops-106018},
  doi =		{10.4230/LIPIcs.ICALP.2019.25},
  annote =	{Keywords: permanent, Hamiltonian cycle, orthogonal vectors}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.84
Spectrally Robust Graph Isomorphism

Authors: Alexandra Kolla, Ioannis Koutis, Vivek Madan, and Ali Kemal Sinop

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

Abstract
We initiate the study of spectral generalizations of the graph isomorphism problem. b) The Spectral Graph Dominance (SGD) problem: On input of two graphs G and H does there exist a permutation pi such that G preceq pi(H)? c) The Spectrally Robust Graph Isomorphism (kappa-SRGI) problem: On input of two graphs G and H, find the smallest number kappa over all permutations pi such that pi(H) preceq G preceq kappa c pi(H) for some c. SRGI is a natural formulation of the network alignment problem that has various applications, most notably in computational biology. G preceq c H means that for all vectors x we have x^T L_G x <= c x^T L_H x, where L_G is the Laplacian G. We prove NP-hardness for SGD. We also present a kappa^3-approximation algorithm for SRGI for the case when both G and H are bounded-degree trees. The algorithm runs in polynomial time when kappa is a constant.
Cite as

Alexandra Kolla, Ioannis Koutis, Vivek Madan, and Ali Kemal Sinop. Spectrally Robust Graph Isomorphism. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 84:1-84:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kolla_et_al:LIPIcs.ICALP.2018.84,
  author =	{Kolla, Alexandra and Koutis, Ioannis and Madan, Vivek and Sinop, Ali Kemal},
  title =	{{Spectrally Robust Graph Isomorphism}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{84:1--84:13},
  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.84},
  URN =		{urn:nbn:de:0030-drops-90887},
  doi =		{10.4230/LIPIcs.ICALP.2018.84},
  annote =	{Keywords: Network Alignment, Graph Isomorphism, Graph Similarity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.91
Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

Authors: Andreas Björklund, Petteri Kaski, and Ioannis Koutis

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We are motivated by a tantalizing open question in exact algorithms: can we detect whether an n-vertex directed graph G has a Hamiltonian cycle in time significantly less than 2^n? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant 0<lambda<1 and prime p we can count the Hamiltonian cycles modulo p^((1-lambda)n/(3p)) in expected time less than c^n for a constant c<2 that depends only on p and lambda. Such an algorithm was previously known only for the case of counting modulo two [Bj\"orklund and Husfeldt, FOCS 2013]. 2. We show that we can detect a Hamiltonian cycle in O^*(3^(n-alpha(G))) time and polynomial space, where alpha(G) is the size of the maximum independent set in G. In particular, this yields an O^*(3^(n/2)) time algorithm for bipartite directed graphs, which is faster than the exponential-space algorithm in [Cygan et al., STOC 2013]. Our algorithms are based on the algebraic combinatorics of "incidence assignments" that we can capture through evaluation of determinants of Laplacian-like matrices, inspired by the Matrix--Tree Theorem for directed graphs. In addition to the novel algorithms for directed Hamiltonicity, we use the Matrix--Tree Theorem to derive simple algebraic algorithms for detecting out-branchings. Specifically, we give an O^*(2^k)-time randomized algorithm for detecting out-branchings with at least k internal vertices, improving upon the algorithms of [Zehavi, ESA 2015] and [Bj\"orklund et al., ICALP 2015]. We also present an algebraic algorithm for the directed k-Leaf problem, based on a non-standard monomial detection problem.
Cite as

Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 91:1-91:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2017.91,
  author =	{Bj\"{o}rklund, Andreas and Kaski, Petteri and Koutis, Ioannis},
  title =	{{Directed Hamiltonicity and Out-Branchings via Generalized Laplacians}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{91:1--91:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.91},
  URN =		{urn:nbn:de:0030-drops-74208},
  doi =		{10.4230/LIPIcs.ICALP.2017.91},
  annote =	{Keywords: counting, directed Hamiltonicity, graph Laplacian, independent set, k-internal out-branching}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.266
Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices

Authors: Ioannis Koutis, Alex Levin, and Richard Peng

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We present three spectral sparsification algorithms that, on input a graph G with n vertices and m edges, return a graph H with n vertices and O(n log n/epsilon^2) edges that provides a strong approximation of G. Namely, for all vectors x and any epsilon>0, we have (1-epsilon) x^T L_G x <= x^T L_H x <= (1+epsilon) x^T L_G x, where L_G and L_H are the Laplacians of the two graphs. The first algorithm is a simple modification of the fastest known algorithm and runs in tilde{O}(m log^2 n) time, an O(log n) factor faster than before. The second algorithm runs in tilde{O}(m log n) time and generates a sparsifier with tilde{O}(n log^3 n) edges. The third algorithm applies to graphs where m>n log^5 n and runs in tilde{O}(m log_{m/ n log^5 n} n time. In the range where m>n^{1+r} for some constant r this becomes softO(m). The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of dense SDD matrices.
Cite as

Ioannis Koutis, Alex Levin, and Richard Peng. Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 266-277, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{koutis_et_al:LIPIcs.STACS.2012.266,
  author =	{Koutis, Ioannis and Levin, Alex and Peng, Richard},
  title =	{{Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{266--277},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.266},
  URN =		{urn:nbn:de:0030-drops-34348},
  doi =		{10.4230/LIPIcs.STACS.2012.266},
  annote =	{Keywords: Spectral sparsification, linear system solving}
}
  • Refine by Type
  • 12 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2023
  • 2 2019
  • 1 2018
  • Show More...

  • Refine by Author
  • 4 Koutis, Ioannis
  • 2 Björklund, Andreas
  • 2 Goranci, Gramoz
  • 2 Momeni, Ali
  • 1 Arvind, V.
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Sparsification and spanners
  • 1 Mathematics of computing → Combinatorial algorithms
  • Show More...

  • Refine by Keyword
  • 3 Spectral sparsification
  • 2 (Directed) hypergraphs
  • 2 Data structures
  • 2 Dynamic algorithms
  • 1 Approximation Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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