18 Search Results for "Oum, Sang-il"

Document
DOI: 10.4230/LIPIcs.ICDT.2026.11
Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy

Authors: Christoph Berkholz and Harry Vinall-Smeeth

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
A common theme in factorised databases and knowledge compilation is the representation of solution sets in a useful yet succinct data structure. In this paper, we study the representation of the result of join queries (or, equivalently, the set of homomorphisms between two relational structures). We focus on the very general format of {∪,×}-circuits - also known as d-representations or DNNF circuits - and aim to find the limits of this approach. In prior work, it has been shown that there always exists a {∪,×}-circuit of size N^O(subw) representing the query result, where N is the size of the database and subw the submodular width of the query. If the arity of all relations is bounded by a constant, then subw is linear in the treewidth tw of the query. In this setting, the authors of this paper proved a lower bound of N^Ω(tw^ε) on the circuit size (ICALP 2023), where ε > 0 depends on the excluded grid theorem. Our first main contribution is to improve this lower bound to N^Ω(tw), which is tight up to a constant factor in the exponent. Our second contribution is a N^Ω(subw^{1/4}) lower bound on the circuit size for join queries over relations of unbounded arity. Both lower bounds are unconditional lower bounds on the circuit size for well-chosen database instances. Their proofs use a combination of structural (hyper)graph theory with communication complexity in a simple yet novel way. While the second lower bound is asymptotically equivalent to Marx’s conditional bound on the decision complexity (JACM 2013), our N^Θ(tw) bound in the bounded arity setting is tight, while the best conditional bound on the decision complexity is N^Ω(tw/log tw). Note that removing this logarithmic factor in the decision setting is a major open problem.
Cite as

Christoph Berkholz and Harry Vinall-Smeeth. Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{berkholz_et_al:LIPIcs.ICDT.2026.11,
  author =	{Berkholz, Christoph and Vinall-Smeeth, Harry},
  title =	{{Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.11},
  URN =		{urn:nbn:de:0030-drops-256255},
  doi =		{10.4230/LIPIcs.ICDT.2026.11},
  annote =	{Keywords: join queries, homomorphisms, factorised databases, succinct representation, knowledge compilation, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.42
Computing Twin-Width via Treedepth and Vertex Integrity

Authors: Robert Ganian and Mathis Rocton

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

Abstract
Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known. A recent approach towards breaking this barrier focuses on first developing fixed-parameter algorithms for computing or approximating twin-width under parameterizations distinct from twin-width. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, thereby breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically. As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.
Cite as

Robert Ganian and Mathis Rocton. Computing Twin-Width via Treedepth and Vertex Integrity. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.STACS.2026.42,
  author =	{Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width via Treedepth and Vertex Integrity}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{42:1--42: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.42},
  URN =		{urn:nbn:de:0030-drops-255318},
  doi =		{10.4230/LIPIcs.STACS.2026.42},
  annote =	{Keywords: twin-width, fixed-parameter algorithms, treedepth, vertex integrity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.51
Structural Parameterization of Steiner Tree Packing

Authors: Niko Hastrich and Kirill Simonov

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

Abstract
Steiner Tree Packing (STP) is a notoriously hard problem in classical complexity theory, which is of practical relevance to VLSI circuit design. Previous research has approached this problem by providing heuristic or approximate algorithms. In this paper, we show the first FPT algorithms for STP parameterized by structural parameters of the input graph. In particular, we show that STP is fixed-parameter tractable by the tree-cut width as well as the fracture number of the input graph. To achieve our results, we generalize techniques from Edge-Disjoint Paths (EDP) to Generalized Steiner Tree Packing (GSTP), which generalizes both STP and EDP. First, we derive the notion of the augmented graph for GSTP analogous to EDP. We then show that GSTP is FPT by - the tree-cut width of the augmented graph, - the fracture number of the augmented graph, - the slim tree-cut width of the input graph. The latter two results were previously known for EDP; our results generalize these to GSTP and improve the running time for the parameter fracture number. On the other hand, it was open whether EDP is FPT parameterized by the tree-cut width of the augmented graph, despite extensive research on the structural complexity of the problem. We settle this question affirmatively.
Cite as

Niko Hastrich and Kirill Simonov. Structural Parameterization of Steiner Tree Packing. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hastrich_et_al:LIPIcs.STACS.2026.51,
  author =	{Hastrich, Niko and Simonov, Kirill},
  title =	{{Structural Parameterization of Steiner Tree Packing}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{51:1--51:18},
  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.51},
  URN =		{urn:nbn:de:0030-drops-255405},
  doi =		{10.4230/LIPIcs.STACS.2026.51},
  annote =	{Keywords: Steiner tree packing, structural parameters, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.4
On the Complexity of Secluded Path Problems

Authors: Tesshu Hanaka and Daisuke Tsuru

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
This paper investigates the complexity of finding secluded paths in graphs. We focus on the Short Secluded Path problem and a natural new variant we introduce, Shortest Secluded Path. Formally, given an undirected graph G = (V, E), two vertices s,t ∈ V, and two integers k,l, the Short Secluded Path problem asks whether there exists an s-t path of length at most k with at most l neighbors. This problem is known to be computationally hard: it is W[1]-hard when parameterized by the path length k or by cliquewidth, and para-NP-complete when parameterized by the number l of neighbors. The fixed-parameter tractability is known for k+l or treewidth. In this paper, we expand the parameterized complexity landscape by designing (1) an XP algorithm parameterized by cliquewidth and (2) fixed-parameter algorithms parameterized by neighborhood diversity and twin cover number, respectively. As a byproduct, our results also provide parameterized algorithms for the classic s-t k-Path problem. Furthermore, we introduce the Shortest Secluded Path problem, which seeks a shortest s-t path with the minimum number of neighbors. In contrast to the hardness of the original problem, we reveal that this variant is solvable in polynomial time on unweighted graphs. We complete this by showing that for edge-weighted graphs, the problem becomes W[1]-hard yet remains in XP when parameterized by the shortest path distance between s and t.
Cite as

Tesshu Hanaka and Daisuke Tsuru. On the Complexity of Secluded Path Problems. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.IPEC.2025.4,
  author =	{Hanaka, Tesshu and Tsuru, Daisuke},
  title =	{{On the Complexity of Secluded Path Problems}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.4},
  URN =		{urn:nbn:de:0030-drops-251361},
  doi =		{10.4230/LIPIcs.IPEC.2025.4},
  annote =	{Keywords: Secluded path, Parameterized complexity, Polynomial-time algorithm}
}
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.85
Towards the Proximity Conjecture on Group-Labeled Matroids

Authors: Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi

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

Abstract
Consider a matroid M whose ground set is equipped with a labeling to an abelian group. A basis of M is called F-avoiding if the sum of the labels of its elements is not in a forbidden label set F. Hörsch, Imolay, Mizutani, Oki, and Schwarcz (2024) conjectured that if an F-avoiding basis exists, then any basis can be transformed into an F-avoiding basis by exchanging at most |F| elements. This proximity conjecture is known to hold for certain specific groups; in the case where |F| ≤ 2; or when the matroid is subsequence-interchangeably base orderable (SIBO), which is a weakening of the so-called strongly base orderable (SBO) property. In this paper, we settle the proximity conjecture for sparse paving matroids or in the case where |F| ≤ 4. Related to the latter result, we present the first known example of a non-SIBO matroid. We further address the setting of multiple group-label constraints, showing proximity results for the cases of two labelings, SIBO matroids, matroids representable over a fixed, finite field, and sparse paving matroids.
Cite as

Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi. Towards the Proximity Conjecture on Group-Labeled Matroids. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garamvolgyi_et_al:LIPIcs.ICALP.2025.85,
  author =	{Garamv\"{o}lgyi, D\'{a}niel and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s and Yamaguchi, Yutaro},
  title =	{{Towards the Proximity Conjecture on Group-Labeled Matroids}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{85:1--85: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.85},
  URN =		{urn:nbn:de:0030-drops-234628},
  doi =		{10.4230/LIPIcs.ICALP.2025.85},
  annote =	{Keywords: sparse paving matroid, subsequence-interchangeable base orderability, congruency constraint, multiple labelings}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.167
Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO

Authors: Nikolas Mählmann

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

Abstract
The graph parameter shrub-depth is a dense analog of tree-depth. We characterize classes of bounded shrub-depth by forbidden induced subgraphs. The obstructions are well-controlled flips of large half-graphs and of disjoint unions of many long paths. Applying this characterization, we show that on every hereditary class of unbounded shrub-depth, MSO is more expressive than FO. This confirms a conjecture of [Gajarský and Hliněný; LMCS 2015] who proved that on classes of bounded shrub-depth FO and MSO have the same expressive power. Combined, the two results fully characterize the hereditary classes on which FO and MSO coincide, answering an open question by [Elberfeld, Grohe, and Tantau; LICS 2012]. Our work is inspired by the notion of stability from model theory. A graph class 𝒞 is MSO-stable, if no MSO-formula can define arbitrarily long linear orders in graphs from 𝒞. We show that a hereditary graph class is MSO-stable if and only if it has bounded shrub-depth. As a key ingredient, we prove that every hereditary class of unbounded shrub-depth FO-interprets the class of all paths. This improves upon a result of [Ossona de Mendez, Pilipczuk, and Siebertz; Eur. J. Comb. 2025] who showed the same statement for FO-transductions instead of FO-interpretations.
Cite as

Nikolas Mählmann. Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 167:1-167:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mahlmann:LIPIcs.ICALP.2025.167,
  author =	{M\"{a}hlmann, Nikolas},
  title =	{{Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{167:1--167: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.167},
  URN =		{urn:nbn:de:0030-drops-235444},
  doi =		{10.4230/LIPIcs.ICALP.2025.167},
  annote =	{Keywords: Shrub-Depth, Forbidden Induced Subgraphs, MSO, Stability Theory}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.15
Structure-Guided Automated Reasoning

Authors: Max Bannach and Markus Hecher

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Algorithmic meta-theorems state that problems definable in a fixed logic can be solved efficiently on structures with certain properties. An example is Courcelle’s Theorem, which states that all problems expressible in monadic second-order logic can be solved efficiently on structures of small treewidth. Such theorems are usually proven by algorithms for the model-checking problem of the logic, which is often complex and rarely leads to highly efficient solutions. Alternatively, we can solve the model-checking problem by grounding the given logic to propositional logic, for which dedicated solvers are available. Such encodings will, however, usually not preserve the input’s treewidth. This paper investigates whether all problems definable in monadic second-order logic can efficiently be encoded into SAT such that the input’s treewidth bounds the treewidth of the resulting formula. We answer this in the affirmative and, hence, provide an alternative proof of Courcelle’s Theorem. Our technique can naturally be extended: There are treewidth-aware reductions from the optimization version of Courcelle’s Theorem to MAXSAT and from the counting version of the theorem to #SAT. By using encodings to SAT, we obtain, ignoring polynomial factors, the same running time for the model-checking problem as we would with dedicated algorithms. Another immediate consequence is a treewidth-preserving reduction from the model-checking problem of monadic second-order logic to integer linear programming (ILP). We complement our upper bounds with new lower bounds based on ETH; and we show that the block size of the input’s formula and the treewidth of the input’s structure are tightly linked. Finally, we present various side results needed to prove the main theorems: A treewidth-preserving cardinality constraints, treewidth-preserving encodings from CNFs into DNFs, and a treewidth-aware quantifier elimination scheme for QBF implying a treewidth-preserving reduction from QSAT to SAT. We also present a reduction from projected model counting to #SAT that increases the treewidth by at most a factor of 2^{k+3.59}, yielding a algorithm for projected model counting that beats the currently best running time of 2^{2^{k+4}}⋅poly(|ψ|).
Cite as

Max Bannach and Markus Hecher. Structure-Guided Automated Reasoning. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.STACS.2025.15,
  author =	{Bannach, Max and Hecher, Markus},
  title =	{{Structure-Guided Automated Reasoning}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.15},
  URN =		{urn:nbn:de:0030-drops-228408},
  doi =		{10.4230/LIPIcs.STACS.2025.15},
  annote =	{Keywords: automated reasoning, treewidth, satisfiability, max-sat, sharp-sat, monadic second-order logic, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.6
Twin-Width One

Authors: Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We investigate the structure of graphs of twin-width at most 1, and obtain the following results: - Graphs of twin-width at most 1 are permutation graphs. In particular they have an intersection model and a linear structure. - There is always a 1-contraction sequence closely following a given permutation diagram. - Based on a recursive decomposition theorem, we obtain a simple algorithm running in linear time that produces a 1-contraction sequence of a graph, or guarantees that it has twin-width more than 1. - We characterise distance-hereditary graphs based on their twin-width and deduce a linear time algorithm to compute optimal sequences on this class of graphs.
Cite as

Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht. Twin-Width One. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.STACS.2025.6,
  author =	{Ahn, Jungho and Jacob, Hugo and K\"{o}hler, Noleen and Paul, Christophe and Reinald, Amadeus and Wiederrecht, Sebastian},
  title =	{{Twin-Width One}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.6},
  URN =		{urn:nbn:de:0030-drops-228319},
  doi =		{10.4230/LIPIcs.STACS.2025.6},
  annote =	{Keywords: Twin-width, Hereditary graph classes, Intersection model}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.8
The Parameterized Complexity of Learning Monadic Second-Order Logic

Authors: Steffen van Bergerem, Martin Grohe, and Nina Runde

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
Within the model-theoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning concepts definable in monadic second-order logic (MSO). We show that the problem of learning an MSO-definable concept from a training sequence of labeled examples is fixed-parameter tractable on graphs of bounded clique-width, and that it is hard for the parameterized complexity class para-NP on general graphs. It turns out that an important distinction to be made is between 1-dimensional and higher-dimensional concepts, where the instances of a k-dimensional concept are k-tuples of vertices of a graph. For the higher-dimensional case, we give a learning algorithm that is fixed-parameter tractable in the size of the graph, but not in the size of the training sequence, and we give a hardness result showing that this is optimal. By comparison, in the 1-dimensional case, we obtain an algorithm that is fixed-parameter tractable in both.
Cite as

Steffen van Bergerem, Martin Grohe, and Nina Runde. The Parameterized Complexity of Learning Monadic Second-Order Logic. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanbergerem_et_al:LIPIcs.CSL.2025.8,
  author =	{van Bergerem, Steffen and Grohe, Martin and Runde, Nina},
  title =	{{The Parameterized Complexity of Learning Monadic Second-Order Logic}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.8},
  URN =		{urn:nbn:de:0030-drops-227651},
  doi =		{10.4230/LIPIcs.CSL.2025.8},
  annote =	{Keywords: monadic second-order definable concept learning, agnostic probably approximately correct learning, parameterized complexity, clique-width, fixed-parameter tractable, Boolean classification, supervised learning, monadic second-order logic}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.18
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Authors: Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, - Independent Set can be solved in time 2^𝒪(dk) ⋅ n^𝒪(1) using 𝒪(dk²log n) space; - Max Cut can be solved in time n^𝒪(dk) using 𝒪(dk log n) space; and - Dominating Set can be solved in time 2^𝒪(dk) ⋅ n^𝒪(1) using n^𝒪(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.
Cite as

Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen. Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ESA.2023.18,
  author =	{Bergougnoux, Benjamin and Chekan, Vera and Ganian, Robert and Kant\'{e}, Mamadou Moustapha and Mnich, Matthias and Oum, Sang-il and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan},
  title =	{{Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.18},
  URN =		{urn:nbn:de:0030-drops-186710},
  doi =		{10.4230/LIPIcs.ESA.2023.18},
  annote =	{Keywords: Parameterized complexity, shrubdepth, space complexity, algebraic methods}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.40
Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k

Authors: Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Sang-il Oum

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

Abstract
Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field F, the list contains only finitely many F-representable matroids, due to the well-quasi-ordering of F-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these F-representable excluded minors in general. We consider the class of matroids of path-width at most k for fixed k. We prove that for a finite field F, every F-representable excluded minor for the class of matroids of path-width at most k has at most 2^{|𝔽|^{O(k²)}} elements. We can therefore compute, for any integer k and a fixed finite field F, the set of F-representable excluded minors for the class of matroids of path-width k, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an F-represented matroid is at most k. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most k has at most 2^{2^{O(k²)}} vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.
Cite as

Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Sang-il Oum. Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kante_et_al:LIPIcs.STACS.2022.40,
  author =	{Kant\'{e}, Mamadou Moustapha and Kim, Eun Jung and Kwon, O-joung and Oum, Sang-il},
  title =	{{Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{40:1--40:14},
  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.40},
  URN =		{urn:nbn:de:0030-drops-158507},
  doi =		{10.4230/LIPIcs.STACS.2022.40},
  annote =	{Keywords: path-width, matroid, linear rank-width, graph, forbidden minor, vertex-minor, pivot-minor}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.70
Γ-Graphic Delta-Matroids and Their Applications

Authors: Donggyu Kim, Duksang Lee, and Sang-il Oum

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
For an abelian group Γ, a Γ-labelled graph is a graph whose vertices are labelled by elements of Γ. We prove that a certain collection of edge sets of a Γ-labelled graph forms a delta-matroid, which we call a Γ-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet to find a maximum weight feasible set in such a delta-matroid. We present two algorithmic applications on graphs; Maximum Weight Packing of Trees of Order Not Divisible by k and Maximum Weight S-Tree Packing. We also discuss various properties of Γ-graphic delta-matroids.
Cite as

Donggyu Kim, Duksang Lee, and Sang-il Oum. Γ-Graphic Delta-Matroids and Their Applications. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.ISAAC.2021.70,
  author =	{Kim, Donggyu and Lee, Duksang and Oum, Sang-il},
  title =	{{\Gamma-Graphic Delta-Matroids and Their Applications}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{70:1--70:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.70},
  URN =		{urn:nbn:de:0030-drops-155038},
  doi =		{10.4230/LIPIcs.ISAAC.2021.70},
  annote =	{Keywords: delta-matroid, group-labelled graph, greedy algorithm, tree packing}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2020.1
How to Decompose a Graph into a Tree-Like Structure (Invited Talk)

Authors: Sang-il Oum

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Many NP-hard problems on graphs are known to be tractable if we restrict the input to have a certain decomposition into a tree-like structure. Width parameters of graphs are measures on how easy it is to decompose the input graph into a tree-like structure. The tree-width is one of the most well-studied width parameters of graphs and the rank-width is a generalization of tree-width into dense graphs. This talk will present a survey on width parameters of graphs such as tree-width and rank-width and discuss known algorithms to find a decomposition of an input graph into such tree-like structures efficiently.
Cite as

Sang-il Oum. How to Decompose a Graph into a Tree-Like Structure (Invited Talk). In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{oum:LIPIcs.ISAAC.2020.1,
  author =	{Oum, Sang-il},
  title =	{{How to Decompose a Graph into a Tree-Like Structure}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.1},
  URN =		{urn:nbn:de:0030-drops-133458},
  doi =		{10.4230/LIPIcs.ISAAC.2020.1},
  annote =	{Keywords: tree-width, rank-width}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.5
A Polynomial Kernel for 3-Leaf Power Deletion

Authors: Jungho Ahn, Eduard Eiben, O-joung Kwon, and Sang-il Oum

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
For a non-negative integer 𝓁, a graph G is an 𝓁-leaf power of a tree T if V(G) is equal to the set of leaves of T, and distinct vertices v and w of G are adjacent if and only if the distance between v and w in T is at most 𝓁. Given a graph G, 3-Leaf Power Deletion asks whether there is a set S ⊆ V(G) of size at most k such that G\S is a 3-leaf power of some treeT. We provide a polynomial kernel for this problem. More specifically, we present a polynomial-time algorithm for an input instance (G,k) to output an equivalent instance (G',k') such that k'≤ k and G' has at most O(k^14) vertices.
Cite as

Jungho Ahn, Eduard Eiben, O-joung Kwon, and Sang-il Oum. A Polynomial Kernel for 3-Leaf Power Deletion. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.MFCS.2020.5,
  author =	{Ahn, Jungho and Eiben, Eduard and Kwon, O-joung and Oum, Sang-il},
  title =	{{A Polynomial Kernel for 3-Leaf Power Deletion}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.5},
  URN =		{urn:nbn:de:0030-drops-126763},
  doi =		{10.4230/LIPIcs.MFCS.2020.5},
  annote =	{Keywords: 𝓁-leaf power, parameterized algorithms, kernelization}
}
  • Refine by Type
  • 18 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 7 2025
  • 1 2023
  • 1 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 7 Oum, Sang-il
  • 3 Kwon, O-joung
  • 2 Ahn, Jungho
  • 2 Ganian, Robert
  • 2 Jeong, Jisu
  • Show More...

  • Refine by Series/Journal
  • 18 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Fixed parameter tractability
  • 5 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Mathematics of computing → Combinatorial algorithms
  • 2 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 4 fixed-parameter tractability
  • 3 rank-width
  • 2 Parameterized complexity
  • 2 linear rank-width
  • 2 monadic second-order logic
  • 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