8 Search Results for "Adler, Isolde"

Document
Track A: Algorithms, Complexity and Games
Computing Tree Decompositions with Small Independence Number

Authors: Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič

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

Abstract
The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum weight independent set, can be solved in time n^𝒪(k) if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov in [SODA 2018] gave an algorithm that given an n-vertex graph G and an integer k, in time n^𝒪(k³) either constructs a tree decomposition of G whose independence number is 𝒪(k³) or correctly reports that the tree-independence number of G is larger than k. In this paper, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time 2^𝒪(k²) n^𝒪(k) and either outputs a tree decomposition of G with independence number at most 8k, or determines that the tree-independence number of G is larger than k. This implies 2^𝒪(k²) n^𝒪(k)-time algorithms for various problems, like maximum weight independent set, parameterized by the tree-independence number k without needing the decomposition as an input. Assuming Gap-ETH, an n^Ω(k) factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k ≥ 4 it is NP-hard to decide if a given graph has the tree-independence number at most k.

Cite as

Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing Tree Decompositions with Small Independence Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

```@InProceedings{dallard_et_al:LIPIcs.ICALP.2024.51,
author =	{Dallard, Cl\'{e}ment and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Milani\v{c}, Martin},
title =	{{Computing Tree Decompositions with Small Independence Number}},
booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
pages =	{51:1--51:18},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-322-5},
ISSN =	{1868-8969},
year =	{2024},
volume =	{297},
editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.51},
URN =		{urn:nbn:de:0030-drops-201945},
doi =		{10.4230/LIPIcs.ICALP.2024.51},
annote =	{Keywords: tree-independence number, approximation, parameterized algorithms}
}```
Document
Track A: Algorithms, Complexity and Games
Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces

Authors: Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht

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

Abstract
In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minors if and only if it is planar. In particular, for every non-planar graph H they gave examples showing that the Erdős-Pósa property does not hold for H. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. Liu’s proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known. In this paper, we initiate the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph H, there exists a unique (up to a suitable equivalence relation on graph parameters) graph parameter EP_H such that H has the Erdős-Pósa property in a minor-closed graph class 𝒢 if and only if sup{EP_H(G) ∣ G ∈ 𝒢} is finite. We prove this conjecture for the class ℋ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar H ∈ ℋ, the parameter EP_H(G) is precisely the maximum order of a Robertson-Seymour counterexample to the Erdős-Pósa property of H which can be found as a minor in G. Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in ℋ.

Cite as

Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 114:1-114:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

```@InProceedings{paul_et_al:LIPIcs.ICALP.2024.114,
author =	{Paul, Christophe and Protopapas, Evangelos and Thilikos, Dimitrios M. and Wiederrecht, Sebastian},
title =	{{Delineating Half-Integrality of the Erd\H{o}s-P\'{o}sa Property for Minors: The Case of Surfaces}},
booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
pages =	{114:1--114:19},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-322-5},
ISSN =	{1868-8969},
year =	{2024},
volume =	{297},
editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.114},
URN =		{urn:nbn:de:0030-drops-202576},
doi =		{10.4230/LIPIcs.ICALP.2024.114},
annote =	{Keywords: Erd\H{o}s-P\'{o}sa property, Erd\H{o}s-P\'{o}sa pair, Graph parameters, Graph minors, Universal obstruction, Surface containment}
}```
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
On Homomorphism Indistinguishability and Hypertree Depth

Authors: Benjamin Scheidt

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

Abstract
GC^k is a logic introduced by Scheidt and Schweikardt (2023) to express properties of hypergraphs. It is similar to first-order logic with counting quantifiers (C) adapted to the hypergraph setting. It has distinct sets of variables for vertices and for hyperedges and requires vertex variables to be guarded by hyperedge variables on every quantification. We prove that two hypergraphs G, H satisfy the same sentences in the logic GC^k with guard depth at most k if, and only if, they are homomorphism indistinguishable over the class of hypergraphs of strict hypertree depth at most k. This lifts the analogous result for tree depth ≤ k and sentences of first-order logic with counting quantifiers of quantifier rank at most k due to Grohe (2020) from graphs to hypergraphs. The guard depth of a formula is the quantifier rank with respect to hyperedge variables, and strict hypertree depth is a restriction of hypertree depth as defined by Adler, Gavenčiak and Klimošová (2012). To justify this restriction, we show that for every H, the strict hypertree depth of H is at most 1 larger than its hypertree depth, and we give additional evidence that strict hypertree depth can be viewed as a reasonable generalisation of tree depth for hypergraphs.

Cite as

Benjamin Scheidt. On Homomorphism Indistinguishability and Hypertree Depth. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 152:1-152:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

```@InProceedings{scheidt:LIPIcs.ICALP.2024.152,
author =	{Scheidt, Benjamin},
title =	{{On Homomorphism Indistinguishability and Hypertree Depth}},
booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
pages =	{152:1--152:18},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-322-5},
ISSN =	{1868-8969},
year =	{2024},
volume =	{297},
editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.152},
URN =		{urn:nbn:de:0030-drops-202958},
doi =		{10.4230/LIPIcs.ICALP.2024.152},
annote =	{Keywords: homomorphism indistinguishability, counting logics, guarded logics, hypergraphs, incidence graphs, tree depth, elimination forest, hypertree width}
}```
Document
Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation

Authors: Benjamin Scheidt and Nicole Schweikardt

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We introduce the 2-sorted counting logic GC^k and its restriction RGC^k that express properties of hypergraphs. These logics have available k variables to address hyperedges, an unbounded number of variables to address vertices of a hypergraph, and atomic formulas E(e,v) to express that a vertex v is contained in a hyperedge e. We show that two hypergraphs H,H' satisfy the same sentences of the logic RGC^k if, and only if, they are homomorphism indistinguishable over the class of hypergraphs of generalised hypertree width at most k. Here, H,H' are called homomorphism indistinguishable over a class 𝒞 if for every hypergraph G ∈ 𝒞 the number of homomorphisms from G to H equals the number of homomorphisms from G to H'. This result can be viewed as a lifting (from graphs to hypergraphs) of a result by Dvořák (2010) stating that any two (undirected, simple, finite) graphs H,H' are indistinguishable by the k+1-variable counting logic C^{k+1} if, and only if, they are homomorphism indistinguishable over the class of graphs of tree-width at most k.

Cite as

Benjamin Scheidt and Nicole Schweikardt. Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 79:1-79:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

```@InProceedings{scheidt_et_al:LIPIcs.MFCS.2023.79,
author =	{Scheidt, Benjamin and Schweikardt, Nicole},
title =	{{Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation}},
booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages =	{79:1--79:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-292-1},
ISSN =	{1868-8969},
year =	{2023},
volume =	{272},
editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.79},
URN =		{urn:nbn:de:0030-drops-186131},
doi =		{10.4230/LIPIcs.MFCS.2023.79},
annote =	{Keywords: counting logics, guarded logics, homomorphism counting, hypertree decompositions, hypergraphs, incidence graphs, quantum graphs}
}```
Document
GSF-Locality Is Not Sufficient For Proximity-Oblivious Testing

Authors: Isolde Adler, Noleen Köhler, and Pan Peng

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
In Property Testing, proximity-oblivious testers (POTs) form a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on the proximity parameter, but the basic test itself is independent of the proximity parameter. In their seminal work, Goldreich and Ron [STOC 2009; SICOMP 2011] show that the graph properties that allow constant-query proximity-oblivious testing in the bounded-degree model are precisely the properties that can be expressed as a generalised subgraph freeness (GSF) property that satisfies the non-propagation condition. It is left open whether the non-propagation condition is necessary. Indeed, calling properties expressible as a generalised subgraph freeness property GSF-local properties, they ask whether all GSF-local properties are non-propagating. We give a negative answer by exhibiting a property of graphs that is GSF-local and propagating. Hence in particular, our property does not admit a POT, despite being GSF-local. We prove our result by exploiting a recent work of the authors which constructed a first-order (FO) property that is not testable [SODA 2021], and a new connection between FO properties and GSF-local properties via neighbourhood profiles.

Cite as

Isolde Adler, Noleen Köhler, and Pan Peng. GSF-Locality Is Not Sufficient For Proximity-Oblivious Testing. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 34:1-34:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

```@InProceedings{adler_et_al:LIPIcs.CCC.2021.34,
author =	{Adler, Isolde and K\"{o}hler, Noleen and Peng, Pan},
title =	{{GSF-Locality Is Not Sufficient For Proximity-Oblivious Testing}},
booktitle =	{36th Computational Complexity Conference (CCC 2021)},
pages =	{34:1--34:27},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-193-1},
ISSN =	{1868-8969},
year =	{2021},
volume =	{200},
editor =	{Kabanets, Valentine},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.34},
URN =		{urn:nbn:de:0030-drops-143082},
doi =		{10.4230/LIPIcs.CCC.2021.34},
annote =	{Keywords: Property testing, proximity-oblivous testing, locality, first-order logic, lower bound}
}```
Document
Faster Property Testers in a Variation of the Bounded Degree Model

Authors: Isolde Adler and Polly Fahey

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

Abstract
Property testing algorithms are highly efficient algorithms, that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions), that are necessary to transform a graph into one with property P. Much research has focussed on the query complexity of such algorithms, i. e. the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. In (Adler, Harwath STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time. In this paper we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. We also show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true. We argue that our model is natural and our meta-theorem showing constant-time CMSO testability supports this.

Cite as

Isolde Adler and Polly Fahey. Faster Property Testers in a Variation of the Bounded Degree Model. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

```@InProceedings{adler_et_al:LIPIcs.FSTTCS.2020.7,
author =	{Adler, Isolde and Fahey, Polly},
title =	{{Faster Property Testers in a Variation of the Bounded Degree Model}},
booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages =	{7:1--7:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-174-0},
ISSN =	{1868-8969},
year =	{2020},
volume =	{182},
editor =	{Saxena, Nitin and Simon, Sunil},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.7},
URN =		{urn:nbn:de:0030-drops-132482},
doi =		{10.4230/LIPIcs.FSTTCS.2020.7},
annote =	{Keywords: Constant Time Algorithms, Logic and Databases, Property Testing, Bounded Degree Model}
}```
Document
Connected Search for a Lazy Robber

Authors: Isolde Adler, Christophe Paul, and Dimitrios M. Thilikos

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

Abstract
The node search game against a lazy (or, respectively, agile) invisible robber has been introduced as a search-game analogue of the treewidth parameter (and, respectively, pathwidth). In the connected variants of the above two games, we additionally demand that, at each moment of the search, the clean territories are connected. The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of connected pathwidth. It is known that the price of connectivty to search for an agile robber is bounded by 2, that is the connected pathwidth of a graph is at most twice (plus some constant) its pathwidth. In this paper, we investigate the connected search game against a lazy robber. A lazy robber moves only when the searchers' strategy threatens the location that he currently occupies. We introduce two alternative graph-theoretic formulations of this game, one in terms of connected tree decompositions, and one in terms of (connected) layouts, leading to the graph parameter of connected treewidth. We observe that connected treewidth parameter is closed under contractions and prove that for every k >= 2, the set of contraction obstructions of the class of graphs with connected treewidth at most k is infinite. Our main result is a complete characterization of the obstruction set for k=2. One may observe that, so far, only a few complete obstruction sets are explicitly known for contraction closed graph classes. We finally show that, in contrast to the agile robber game, the price of connectivity is unbounded.

Cite as

Isolde Adler, Christophe Paul, and Dimitrios M. Thilikos. Connected Search for a Lazy Robber. 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. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

```@InProceedings{adler_et_al:LIPIcs.FSTTCS.2019.7,
author =	{Adler, Isolde and Paul, Christophe and Thilikos, Dimitrios M.},
title =	{{Connected Search for a Lazy Robber}},
booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages =	{7:1--7:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-131-3},
ISSN =	{1868-8969},
year =	{2019},
volume =	{150},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.7},
URN =		{urn:nbn:de:0030-drops-115695},
doi =		{10.4230/LIPIcs.FSTTCS.2019.7},
annote =	{Keywords: Graph searching, Tree-decomposition, Obstructions}
}```
Document
Property Testing for Bounded Degree Databases

Authors: Isolde Adler and Frederik Harwath

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Aiming at extremely efficient algorithms for big data sets, we introduce property testing of relational databases of bounded degree. Our model generalises the bounded degree model for graphs (Goldreich and Ron, STOC 1997). We prove that in this model, if the databases have bounded tree-width, then every query definable in monadic second-order logic with modulo counting is testable with a constant number of oracle queries and polylogarithmic running time. This is the first logical meta-theorem in property testing of sparse models. Furthermore, we discuss conditions for the existence of uniform and non-uniform testers.

Cite as

Isolde Adler and Frederik Harwath. Property Testing for Bounded Degree Databases. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

```@InProceedings{adler_et_al:LIPIcs.STACS.2018.6,
author =	{Adler, Isolde and Harwath, Frederik},
title =	{{Property Testing for Bounded Degree Databases}},
booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages =	{6:1--6:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-062-0},
ISSN =	{1868-8969},
year =	{2018},
volume =	{96},
editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.6},
URN =		{urn:nbn:de:0030-drops-85288},
doi =		{10.4230/LIPIcs.STACS.2018.6},
annote =	{Keywords: logic and databases, property testing, logical meta-theorems, bounded degree model, sublinear algorithms}
}```
• Refine by Author
• 2 Paul, Christophe
• 2 Scheidt, Benjamin
• 2 Thilikos, Dimitrios M.
• 1 Dallard, Clément

• Refine by Classification
• 3 Theory of computation → Finite Model Theory
• 2 Mathematics of computing → Graph theory
• 2 Mathematics of computing → Hypergraphs
• 2 Theory of computation → Streaming, sublinear and near linear time algorithms
• 1 Mathematics of computing → Graph algorithms

• Refine by Keyword
• 2 counting logics
• 2 guarded logics
• 2 hypergraphs
• 2 incidence graphs
• 1 Bounded Degree Model