commit 8c5731e1a62cecadd941aa725372a7f1a808f936
parent 08167f073b1ca86ab5c04929cf11369cb416a4a4
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 27 Oct 2025 10:19:03 +0100
commit with codex
Diffstat:
24 files changed, 114 insertions(+), 18 deletions(-)
diff --git a/3sat_3_occurrences b/3sat_3_occurrences
@@ -1,12 +0,0 @@
-# 3SAT 3 occurrences
-
-[3SAT] where each variable occurs at most 3 times:
-
-- do you have exactly 3 literals per clause, or at most 3 literals per clause?
- - if 3 literals per clause:
- - [3SAT_3_occurrences_exactly3] ([PTIME])
- - note: if you go beyond [3SAT] and allow larger clauses, then it is still [NP_complete]: cf [tovey1984simplified]
- - if at most 3 literals per clause:
- - [3SAT_3_occurrences_atmost3]
-
-Up: [3sat_variants]
diff --git a/acyclic_free_connex b/acyclic_free_connex
@@ -9,3 +9,5 @@ When a query is not acyclic free-connex you can often reduce from [boolean_matri
Up: [conjunctive_query_acyclic]
See also: [enumeration_cqs]
+
+Aliases: Acyclic free connex CQ, acyclic free connex CQs
diff --git a/chinese_postman_problem b/chinese_postman_problem
@@ -1,8 +1,10 @@
# Chinese postman problem
+https://en.wikipedia.org/wiki/Chinese_postman_problem
+
The [computational_problem] of computing the shortest [path] or [circuit] that visits every [edge] of a [graph] at least once
-Can be posed for [graph_directed] or [graph_undirected]
+Can be posed for [graph_directed] or [graph_undirected]. It is [PTIME] in both cases
[NP_complete] on:
- [Undirected_graphs] when traversal cost is different per direction: [windy_postman_problem]
diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic
@@ -25,4 +25,4 @@ See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_
Up: [conjunctive_query], [query_acyclic]
-Aliases: acyclic conjunctive query, acyclic conjunctive queries, acyclic CQ, acyclic CQs, CQ acyclic, acyclic queries, acyclic query
+Aliases: acyclic conjunctive query, acyclic conjunctive queries, acyclic CQ, acyclic CQs, CQ acyclic, acyclic queries, acyclic query, ACQ, ACQs
diff --git a/disjoint_path_2 b/disjoint_path_2
@@ -0,0 +1,15 @@
+# Two-disjoint path problem
+
+The [decision_problem], given a [directed_graph] and sources s1 and s2 and sinks t1 and t2, of determining whether there are vertex-disjoint [simple_paths] from s1 to t1 and s2 to t2
+
+It is [NP_hard], cf [fortune1980directed]
+
+The "[simple_path] via node" problem is already [NP_hard]
+
+Not to be confused with the problem of finding two vertex-disjoint paths from {s1, s2} to {t1, t2}, which can be solved in [PTIME] using [network_flows]; in that case you cannot enforce which pairs of vertices are being connected by the two paths
+
+Up: [disjoint_paths]
+
+See also: [edge_connectedness], [simple_path_RPQ]
+
+Aliases: two disjoint path problem, two disjoint paths, Disjoint path 2, twodisjoint path problem, two disjoint simple path, two disjoint simple paths, two disjoint simple path problem, two disjoint simple paths problem
diff --git a/disjoint_paths_undirected b/disjoint_paths_undirected
@@ -13,3 +13,5 @@ Cf [liu2025disjoint] for a review and for a generalization to [modularity_constr
Special case: [2_disjoint_paths_undirected]
Up: [disjoint_paths] on [undirected_graphs]
+
+Aliases: undirected k disjoint paths, undirected k disjoint path problem
diff --git a/exact_matching b/exact_matching
@@ -5,4 +5,6 @@
[maalouly2022exact]: this is in [RP] and not known to be in [ptime]
+Variant: [exact_matching_parity]
+
Up: [matching]
diff --git a/exact_matching_parity b/exact_matching_parity
@@ -0,0 +1,14 @@
+# Exact matching parity
+
+- in [bipartite_graphs], can decide in [PTIME] whether there is a [perfect_matching] with an even number of red edges
+ - proof in [datta2010perfect]
+ - generalization to [maximum_matching]
+ - https://cstheory.stackexchange.com/a/41357
+ - unknown for other moduli?
+ - unknown for non-bipartite graphs?
+- for general graphs and constant number of colors it can be done in [PTIME]
+ - [RP] algorithm from [mulmuley1987matching]
+ - cf [marx2004list]
+ - https://cstheory.stackexchange.com/a/41343
+
+Up: [matching_variants], [exact_matching]
diff --git a/graph_basic_notions b/graph_basic_notions
@@ -27,6 +27,7 @@
- [graph_representation]
- [adjacency_matrix]
- [adjacency_list]
+- [line_graph]
Up: [graph]
diff --git a/graph_outerplanar b/graph_outerplanar
@@ -0,0 +1,9 @@
+# Outerplanar graph
+
+https://en.wikipedia.org/wiki/Outerplanar_graph
+
+A [planar_graph] where all vertices are on the outer face of the drawing
+
+Up: [planar_graph]
+
+Aliases: outerplanar graph, outerplanar graphs
diff --git a/graph_square b/graph_square
@@ -4,6 +4,14 @@
Some are [Hamiltonian]: [graph_square_hamiltonian]
+Three variants:
+- connecting vertices with a distance *at most* two: this is the usual notion of graph square
+ - testing if an [undirected_graph] is a graph square in this sense is [NP_hard], cf [motwani1994computing]
+- connecting vertices with a distance *exactly* two: studied in [bai2024characterizing]
+ - testing if an [undirected_graph] is a graph square in this sense is [PTIME]
+- connecting vertices with a [walk] of length *exactly* two (but potentially also an edge): studied in [kutz2009digraph]
+ - testing if an [undirected_graph] is a graph square in this sense is [NP_hard]
+
Up: [graph_exponentiation]
See also: [radoszewski2011hamiltonian], [graph_cube]
diff --git a/graph_square_hamiltonian b/graph_square_hamiltonian
@@ -2,6 +2,9 @@
An [undirected_graph] whose [graph_square] is a [Hamiltonian_graph]
-The [recognition_problem] is [NP_hard], cf https://en.wikipedia.org/wiki/Graph_power#Computational_complexity
+The [recognition_problem] is [NP_hard]
+- cf https://en.wikipedia.org/wiki/Graph_power#Computational_complexity
Up: [graph_square]
+
+See also: [graph_square_hamiltonian_variants]
diff --git a/join b/join
@@ -5,5 +5,8 @@
- [join_path]
- [self_join]
- [optimal_joins]
+- [inequality_join]
Up: [databases]
+
+Aliases: joins
diff --git a/line_graph b/line_graph
@@ -0,0 +1,13 @@
+# Line graph
+
+https://en.wikipedia.org/wiki/Line_graph
+
+The *line graph* of an [undirected_graph] G = (V, E) is the [graph] G' where the [vertices] of G' are E and where there is an edge in G' connecting two edges of E if they share a vertex in G
+
+They can be recognized in [linear_time]
+
+They have a [Hamiltonian_cycle] if the original graph has a [Hamiltonian_cycle]: cf [balakrishnan2012textbook], Corollary 6.5.5 and [harary1965eulerian]
+
+Up: [graph_basic_notions]
+
+See also: [dual_hypergraph]
diff --git a/matching b/matching
@@ -3,7 +3,6 @@
Structure in [graph] et [graph_bipartite]: a subset of edges where no two edges share a vertex
- [maximum_matching]
-- [exact_matching]
- [perfect_matching]
Problems:
@@ -15,6 +14,11 @@ Algorithms [graph_algorithm]:
- [hungarian_algorithm]
+Variants:
+
+- [matching_variants]
+- [exact_matching]
+
Also the [linear_relaxation]: see [fractional_edge_packing]
See also: [independent_set], [induced_matching], [graph_matching_covered], [deficiency]
diff --git a/planar_graph b/planar_graph
@@ -23,6 +23,10 @@ Specific algorithms:
- [fkt_algorithm]
+Special cases:
+
+- [graph_outerplanar]
+
Generalizations:
- to [hypergraphs]: [planar_hypergraph]
diff --git a/polytree b/polytree
@@ -4,11 +4,11 @@ https://en.wikipedia.org/wiki/Polytree
A polytree is a [directed_acyclic_graph] whose underlying [undirected_graph] is a [tree]
-A polytree is always a [multitree]
+A polytree is always a [multitree], but not vice-versa
In a polytree, we can do [transitive_closure] in [output_linear] time, and do [enumeration] of reachable leaves with linear preprocessing and constant delay
- this is like [boolean_matrix_multiplication] when there are no duplicate ways to obtain ones
- - like [context_free_grammar_unambiguous]
+ - like [CFG_parsing] for [unambiguous_CFGs]
- like [circuit] [deterministic]
Up: [graph_family]
diff --git a/rpq_simple_paths b/rpq_simple_paths
@@ -8,6 +8,8 @@ For instance:
- [simple_path_rpq_enumeration]
- [rpq_counting_simple_paths]
+It is tractable on [outerplanar_graphs] by [nedev2000polynomial]
+
Up: [rpq_semantics], [RPQ], [simple_paths]
Aliases: RPQ simple path, simple path RPQ, simple path RPQs
diff --git a/shuffle b/shuffle
@@ -8,3 +8,5 @@ A [word] w is a *shuffle* of two [words] u and v if we can interleave the charac
- see [berstel2002shuffle]
Up: [formal_language_operator]
+
+Aliases: interleaving
diff --git a/simple_path_parity_problem b/simple_path_parity_problem
@@ -0,0 +1,11 @@
+# Simple path parity problem
+
+[Computational_problem] of deciding if there is a [simple_path] in a [graph] from a vertex s to a vertex t that has even length (or odd length)
+
+This is [NP_complete] in general graphs by reduction from [two_disjoint_simple_path]
+
+But on [planar_graphs] it is in [PTIME] by [nedev1999finding]
+- shown by reduction to [undirected_k_disjoint_path_problem]
+- also and on [outerplanar_graphs] it is in [PTIME] even for [simple_path_RPQ] by [nedev2000polynomial]
+
+Up: [simple_path_problem]
diff --git a/simple_path_problem b/simple_path_problem
@@ -5,5 +5,6 @@
Obviously [PTIME] by computing a [shortest_path]
- [simple_path_rpq_problem]
+- [simple_path_parity_problem]
Up: [computational_problem], [simple_path]
diff --git a/vector_addition_system b/vector_addition_system
@@ -11,6 +11,7 @@ Also called "vector addition system with states" (VASS)
Generalizations:
- [vector_addition_tree_automata]
- [vector_addition_system_pushdown]
+- [vector_addition_system_nested]
Complexity of the [reachability] problem: [ackermann_function]
- https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/
diff --git a/vector_addition_system_nested b/vector_addition_system_nested
@@ -0,0 +1,7 @@
+# VASS with nested zero tests
+
+studied in [guttenberg2025reachability]
+
+Up: [vector_addition_system]
+
+Aliases: VASS with nested zero tests
diff --git a/xsat b/xsat
@@ -4,6 +4,8 @@ A [Boolean_satisfiability_problem] formed as a [conjunction] of [clauses], in ea
Also called "1-in-3-SAT" in the case of [3SAT]
+Relevant: https://cstheory.stackexchange.com/q/32208
+
Up: [sat_variants]
See also: [exact_cover], [hitting_set]
