Search Results

Documents authored by Redzic, Mirza

Document
DOI: 10.4230/LIPIcs.WG.2026.31
On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs

Authors: Alex Koutsoutis, Kilian Krause, Chun-Hung Liu, Mirza Redzic, and Torsten Ueckerdt

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract
We investigate the relationship between graph parameters, which measure the complexity of the tree decompositions of a given graph. The treewidth tw(G) of a graph G measures the largest number of vertices required in a bag of every tree decomposition of G. Similarly, the tree-independence number tree-α(G) and the tree-chromatic number tree-χ(G) measure the largest independence number, respectively the largest chromatic number, required in a bag of every tree decomposition of G. Recently, Dallard, Milanič, and Štorgel asked (JCTB, 2024) whether for all graphs G it holds that tw(G)+1 ≤ tree-α(G) ⋅ tree-χ(G). We provide a negative answer for this question in a strong form: for every function f: {ℕ} → {ℕ}, there exists a graph G such that tw(G) > tree-α(G) ⋅ f(tree-χ(G)). On the other hand, we complement this result with an upper bound, by showing that tw(G)+1 ≤ tree-α(G)² ⋅ tree-χ(G) for every graph G.
Cite as

Alex Koutsoutis, Kilian Krause, Chun-Hung Liu, Mirza Redzic, and Torsten Ueckerdt. On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 31:1-31:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koutsoutis_et_al:LIPIcs.WG.2026.31,
  author =	{Koutsoutis, Alex and Krause, Kilian and Liu, Chun-Hung and Redzic, Mirza and Ueckerdt, Torsten},
  title =	{{On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{31:1--31:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.31},
  URN =		{urn:nbn:de:0030-drops-261978},
  doi =		{10.4230/LIPIcs.WG.2026.31},
  annote =	{Keywords: Tree-independence number, Tree-chromatic number, Treewidth}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.94
When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?

Authors: Timo Fritsch, Marvin Künnemann, Mirza Redzic, and Julian Stieß

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Consider the fundamental task of finding independent sets of (constant) size k in a given n-node hypergraph. How much is the time complexity affected by the sparsity of the input, i.e., the number of hyperedges m? Turán’s theorem implies that the problem is trivial if m = O(n^{2-ε}) for some ε > 0. Above that threshold (i.e., if m = Θ(n^γ) for some γ ≥ 2), we give a perhaps surprising algorithm with running time O(min{ n^({ω/3}k) + m^{k/3}, n^k}) (for k divisible by 3), which is essentially conditionally optimal for all γ ≥ 2, assuming the k-clique and 3-uniform hyperclique hypotheses (here, ω ≤ 2.372 denotes the matrix multiplication exponent). In fact, we obtain a more detailed time complexity that is sensitive to the arity distribution of the hyperedges. To study such phenomena in more generality, we study the time complexity of finding solutions of (constant) size k in sparse instances of Boolean constraint satisfaction problems, where n and m denote the number of variables and constraints, respectively. Our results include, among others: - an essentially full classification of the influence of sparsity for Boolean constraint families of binary arity. Of particular technical interest is a conditionally tight algorithm for the family consisting of the binary NAND and the binary Implication constraints, with a running time of Θ(m^{ω k/6 ± c}). - the identification of a large class of constraint families ℱ that exhibits a sharp phase transition: there is a threshold γ_ℱ such that the problem is trivial for m = O(n^{γ_ℱ-ε}), but requires essentially brute-force running time Θ(n^{k±c}) for m = Ω(n^{γ_ℱ}), assuming the 3-uniform hyperclique hypothesis. In general, we observe a rich landscape of time complexities. Notably, in many cases the combination of constraints display higher time complexity than either constraint alone.
Cite as

Timo Fritsch, Marvin Künnemann, Mirza Redzic, and Julian Stieß. When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 94:1-94:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fritsch_et_al:LIPIcs.ICALP.2026.94,
  author =	{Fritsch, Timo and K\"{u}nnemann, Marvin and Redzic, Mirza and Stie{\ss}, Julian},
  title =	{{When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{94:1--94:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.94},
  URN =		{urn:nbn:de:0030-drops-264836},
  doi =		{10.4230/LIPIcs.ICALP.2026.94},
  annote =	{Keywords: Multivariate algorithmics, fine-grained complexity theory, classification theorems, algorithmic hypergraph theory}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.98
Fine-Grained Classification of Detecting Dominating Patterns

Authors: Jonathan Dransfeld, Marvin Künnemann, and Mirza Redzic

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the following generalization of dominating sets: Let G be a host graph and P be a pattern graph P. A dominating P-pattern in G is a subset S of vertices in G that (1) forms a dominating set in G and (2) induces a subgraph isomorphic to P. The graph theory literature studies the properties of dominating P-patterns for various patterns P, including cliques, matchings, independent sets, cycles and paths. Previous work (Kunnemann, Redzic 2024) obtains algorithms and conditional lower bounds for detecting dominating P-patterns particularly for P being a k-clique, a k-independent set and a k-matching. Their results give conditionally tight lower bounds if k is sufficiently large (where the bound depends the matrix multiplication exponent ω). We ask: Can we obtain a classification of the fine-grained complexity for all patterns P? Indeed, we define a graph parameter ρ(P) such that if ω = 2, then (n^ρ(P) m^{(|V(P)|-ρ(P))/2})^{1±o(1)} is the optimal running time assuming the Orthogonal Vectors Hypothesis, for all patterns P except the triangle K₃. Here, the host graph G has n vertices and m = Θ(n^α) edges, where 1 ≤ α ≤ 2. The parameter ρ(P) is closely related (but sometimes different) to a parameter δ(P) = max_{S ⊆ V(P)} |S|-|N(S)| studied in (Alon 1981) to tightly quantify the maximum number of occurrences of induced subgraphs isomorphic to P. Our results stand in contrast to the lack of a full fine-grained classification of detecting an arbitrary (not necessarily dominating) induced P-pattern.
Cite as

Jonathan Dransfeld, Marvin Künnemann, and Mirza Redzic. Fine-Grained Classification of Detecting Dominating Patterns. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 98:1-98:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dransfeld_et_al:LIPIcs.ESA.2025.98,
  author =	{Dransfeld, Jonathan and K\"{u}nnemann, Marvin and Redzic, Mirza},
  title =	{{Fine-Grained Classification of Detecting Dominating Patterns}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{98:1--98:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.98},
  URN =		{urn:nbn:de:0030-drops-245679},
  doi =		{10.4230/LIPIcs.ESA.2025.98},
  annote =	{Keywords: fine-grained complexity theory, domination in graphs, subgraph isomorphism, classification theorem, parameterized algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.78
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs

Authors: Nick Fischer, Marvin Künnemann, Mirza Redžić, and Julian Stieß

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

Abstract
Is detecting a k-clique in k-partite regular (hyper-)graphs as hard as in the general case? Intuition suggests yes, but proving this - especially for hypergraphs - poses notable challenges. Concretely, we consider a strong notion of regularity in h-uniform hypergraphs, where we essentially require that any subset of at most h-1 is incident to a uniform number of hyperedges. Such notions are studied intensively in the combinatorial block design literature. We show that any f(k)n^{g(k)}-time algorithm for detecting k-cliques in such graphs transfers to an f'(k)n^{g(k)}-time algorithm for the general case, establishing a fine-grained equivalence between the h-uniform hyperclique hypothesis and its natural regular analogue. Equipped with this regularization result, we then fully resolve the fine-grained complexity of optimizing Boolean constraint satisfaction problems over assignments with k non-zeros. Our characterization depends on the maximum degree d of a constraint function. Specifically, if d ≤ 1, we obtain a linear-time solvable problem, if d = 2, the time complexity is essentially equivalent to k-clique detection, and if d ≥ 3 the problem requires exhaustive-search time under the 3-uniform hyperclique hypothesis. To obtain our hardness results, the regularization result plays a crucial role, enabling a very convenient approach when applied carefully. We believe that our regularization result will find further applications in the future.
Cite as

Nick Fischer, Marvin Künnemann, Mirza Redžić, and Julian Stieß. The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 78:1-78:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.ICALP.2025.78,
  author =	{Fischer, Nick and K\"{u}nnemann, Marvin and Red\v{z}i\'{c}, Mirza and Stie{\ss}, Julian},
  title =	{{The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{78:1--78: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.78},
  URN =		{urn:nbn:de:0030-drops-234559},
  doi =		{10.4230/LIPIcs.ICALP.2025.78},
  annote =	{Keywords: fine-grained complexity theory, clique detections in hypergraphs, constraint satisfaction, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.9
Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs

Authors: Marvin Künnemann and Mirza Redzic

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
The study of domination in graphs has led to a variety of dominating set problems studied in the literature. Most of these follow the following general framework: Given a graph G and an integer k, decide if there is a set S of k vertices such that (1) some inner connectivity property ϕ(S) (e.g., connectedness) is satisfied, and (2) each vertex v satisfies some domination property ρ(S, v) (e.g., there is some s ∈ S that is adjacent to v). Since many real-world graphs are sparse, we seek to determine the optimal running time of such problems in both the number n of vertices and the number m of edges in G. While the classic dominating set problem admits a rather limited improvement in sparse graphs (Fischer, Künnemann, Redzic SODA'24), we show that natural variants studied in the literature admit much larger speed-ups, with a diverse set of possible running times. Specifically, using fast matrix multiplication we devise efficient algorithms which in particular yield the following conditionally optimal running times if the matrix multiplication exponent ω is equal to 2: - r-Multiple k-Dominating Set (each vertex v must be adjacent to at least r vertices in S): If r ≤ k-2, we obtain a running time of (m/n)^{r} n^{k-r+o(1)} that is conditionally optimal assuming the 3-uniform hyperclique hypothesis. In sparse graphs, this fully interpolates between n^{k-1± o(1)} and n^{2± o(1)}, depending on r. Curiously, when r = k-1, we obtain a randomized algorithm beating (m/n)^{k-1} n^{1+o(1)} and we show that this algorithm is close to optimal under the k-clique hypothesis. - H-Dominating Set (S must induce a pattern H). We conditionally settle the complexity of three such problems: (a) Dominating Clique (H is a k-clique), (b) Maximal Independent Set of size k (H is an independent set on k vertices), (c) Dominating Induced Matching (H is a perfect matching on k vertices). For all sufficiently large k, we provide algorithms with running time (m/n)m^{(k-1)/2+o(1)} for (a) and (b), and m^{k/2+o(1)} for (c). We show that these algorithms are essentially optimal under the k-Orthogonal Vectors Hypothesis (k-OVH). This is in contrast to H being the k-Star, which is susceptible only to a very limited improvement, with the best algorithm running in time n^{k-1 ± o(1)} in sparse graphs under k-OVH.
Cite as

Marvin Künnemann and Mirza Redzic. Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kunnemann_et_al:LIPIcs.IPEC.2024.9,
  author =	{K\"{u}nnemann, Marvin and Redzic, Mirza},
  title =	{{Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.9},
  URN =		{urn:nbn:de:0030-drops-222353},
  doi =		{10.4230/LIPIcs.IPEC.2024.9},
  annote =	{Keywords: Fine-grained complexity theory, Dominating set, Sparsity in graphs, Conditionally optimal algorithms}
}
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