commit 90079cb6170f3f34b77d0eee72c4f105fd5e3bad
parent 6351deef3e0951e493be347c97eca2642db6ade5
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 8 Sep 2026 17:43:14 +0200
commit with codex
Diffstat:
5 files changed, 22 insertions(+), 2 deletions(-)
diff --git a/directed_triangle_decomposition b/directed_triangle_decomposition
@@ -0,0 +1,11 @@
+# Directed triangle decomposition problem
+
+Given a [directed_graph] G, decide if the edge set of G can be partitioned into disjoint [triangles]
+
+According to [bonnet2018complexity] Lemma 2, it is [NP_hard] (and admits no [subexponential] algorithm under [ETH]) even if the input graph is [Eulerian] and has no 2-cycles and is [tripartite_graph] with edges oriented in pattern A -> B -> C -> A.
+
+Up: [decision_problem], [graph_partition_edges], [triangle]
+
+See also: [holyer1981np]
+
+Aliases: Directed triangle decomposition problem
diff --git a/eulerian_circuit b/eulerian_circuit
@@ -4,7 +4,7 @@ A [Eulerian_trail] which is a [cycle_circuit], i.e., starts and ends at the same
An [undirected_graph] has a Eulerian circuit if and only if it is [graph_connected] and the [degree] of each [vertex] is even (this implies in particular that the graph is [bridgeless])
-The number of Eulerian circuits in [directed_graphs] can be computed in [PTIME] by the [BEST_theorem]
+If we add forbidden "transitions" aka pairs of incident edges that are not allowed to be consecutive, the [computational_problem] of [deciding] if there is a suitable Eulerian circuit becomes [NP_hard] even if the [degree] of the graph is bounded, specifically for [undirected_graphs] of [maximal_degree] 8 and [directed_graphs] of [maximal_degree] 4, see [dvorak2004eulerian]
- [Eulerian_circuit_counting]
diff --git a/graph_partition_edges b/graph_partition_edges
@@ -7,7 +7,11 @@ Partitioning the edges of a [graph] into specified patterns
- Partitioning into [P3] is in [PTIME], it can be done by reduction to [perfect_matching]
- Also discussed in [diwan2015p3]
- In fact for simple undirected graphs a solution always exist when the connected components have an even number of edges, see [diwan2017decomposing]
+- partitioning into triangles: [directed_triangle_decomposition]
+- partitioning into copies of a fixed graph: [Holyer's_conjecture]
Variant: partitioning the vertices, see [graph_partition]
Up: [computational_problem] on [graph]
+
+Aliases: graph edge partition
diff --git a/holyers_conjecture b/holyers_conjecture
@@ -0,0 +1,5 @@
+# Holyer's conjecture
+
+Proved in [dor1997graph]: [graph_partition_edges] is [NP_hard] whenever the fixed graph is [graph_connected] and has three edges or more
+
+Up: [graph_partition_edges]
diff --git a/vector_addition_system b/vector_addition_system
@@ -26,7 +26,7 @@ They correspond to [Minsky_machines] but without zero tests
Restrictions:
- [1_VASS], with only one counter
- - see also [one_conter_automata]
+ - see also [one_counter_automata]
Up: [automata]
