commit 5d9248142db68b3a81efd276bff7e0c675279c6b
parent ae8d9586d5a40be2f7d7dd807e15db5f9ded48a8
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 1 Jun 2025 19:39:07 +0200
commit with codex
Diffstat:
12 files changed, 93 insertions(+), 0 deletions(-)
diff --git a/benameur2024cops b/benameur2024cops
@@ -0,0 +1,14 @@
+# Benameur2024cops
+
+they study [hunters_and_rabbit_directed]
+
+- they show that the cop number is at most the [directed_pathwidth] + 1, but can be arbitrarily smaller
+- it is the [directed_pathwidth] or the [directed_pathwidth] + 1 in the [monotone_strategy] case
+
+- lower bound: minimum [outdegree] of an [induced_subgraph], which can be computed in [ptime]
+ - just do [binary_search] on the value, then iteratively remove vertices with too small outdegree, and check if the remaining graph is empty or not
+- upper bound: minimum [feedback_vertex_set]
+
+also [benameur2024complexity]
+
+Up: [hunters_and_rabbit]
diff --git a/graph_partition_edges b/graph_partition_edges
@@ -0,0 +1,10 @@
+# Graph partition edges
+
+Partitioning the edges of a [graph] into specified patterns
+
+- [dyer1985complexity] [np_hard] to partition into [connected] [subgraphs] of size 3 even in case of [planar_graphs], and other results
+- [bulteau2016decomposing]: also in the case of [graph_cubic]
+
+Variant: partitioning the vertices, see [graph_partition]
+
+Up: [computational_problem] on [graph]
diff --git a/lempel_ziv b/lempel_ziv
@@ -0,0 +1,5 @@
+# Lempel-Ziv
+
+fast computation: [ellert2023sublinear]
+
+Up: [compression_string]
diff --git a/maximum_matching_counting b/maximum_matching_counting
@@ -0,0 +1,5 @@
+# Maximum matching counting
+
+- on [graph_bipartite]: [maximum_matching_counting_bipartite]
+
+Up: [counting] of [maximum_matching]
diff --git a/optimal_joins_sampling b/optimal_joins_sampling
@@ -0,0 +1,5 @@
+# Optimal joins sampling
+
+[wang2024join]
+
+Up: [optimal_joins], [sampling_cqs]
diff --git a/sharpp_hard b/sharpp_hard
@@ -0,0 +1,5 @@
+# SharpP-hard
+
+depends on the notion of [reduction]: [sharpP_Hard_reductions]
+
+Up: [hardness] for [sharpp]
diff --git a/subgraph_listing b/subgraph_listing
@@ -0,0 +1,10 @@
+# Subgraph listing
+
+- [clique_listing]
+- [triangle_listing]
+- [cycle_listing], cf for instance [jin2023listing]
+- cases that are [subquadratic], cf [bringmann2024fine]
+
+Up: [listing], [subgraph]
+
+See also: [subgraph_enumeration]
diff --git a/subsequence_order b/subsequence_order
@@ -0,0 +1,7 @@
+# Subsequence order
+
+The [partial_order] on [words] given by the [subsequence] relation
+
+By [Higman's_lemma], it is a [well_quasi_order] on [words]
+
+Up: [subsequence], [order]
diff --git a/universality_automata_pushdown b/universality_automata_pushdown
@@ -0,0 +1,6 @@
+# Universality automata pushdown
+
+- [universality_automata_pushdown_nondeterministic] is [undecidable]
+- [universality_automata_pushdown_deterministic]
+
+Up: [universality_automata], [pushdown_automata]
diff --git a/universality_automata_pushdown_deterministic b/universality_automata_pushdown_deterministic
@@ -0,0 +1,11 @@
+# Universality automata pushdown deterministic
+
+It is in [PTIME], like [Universality_automata_deterministic]
+
+cf https://cstheory.stackexchange.com/questions/55099/the-complexity-of-the-universality-problem-for-deterministic-pushdown-automata
+
+Up: [universality_automata_pushdown], [Automata_pushdown_deterministic]
+
+Aliases: DPDA universality
+
+See also: [universality_automata_pushdown_nondeterministic]
diff --git a/universality_automata_pushdown_nondeterministic b/universality_automata_pushdown_nondeterministic
@@ -0,0 +1,7 @@
+# Universality automata pushdown nondeterministic
+
+It is [undecidable] cf https://cstheory.stackexchange.com/questions/55099/the-complexity-of-the-universality-problem-for-deterministic-pushdown-automata
+
+Up: [universality_automata_pushdown], [pushdown_automaton_nondeterministic]
+
+See also: [universality_automata_pushdown_deterministic]
diff --git a/variety_positive b/variety_positive
@@ -0,0 +1,8 @@
+# Variety positive
+
+A generalization of [varieties] of [formal_languages]
+- not closed under [complementation] (so only [intersection] and [union])
+
+Up: [variety]
+
+Aliases: positive variety
