wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

directed_triangle_decomposition (531B)

      1 # Directed triangle decomposition problem
      2 
      3 Given a [directed_graph] G, decide if the edge set of G can be partitioned into disjoint [triangles]
      4 
      5 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.
      6 
      7 Up: [decision_problem], [graph_partition_edges], [triangle]
      8 
      9 See also: [holyer1981np]
     10 
     11 Aliases: Directed triangle decomposition problem