relation.dot

digraph {
  // weakly polynomial
  semidefinite_programming [label="Semidefinite Programming"];
  second_order_cone_programming [label="Second-order cone programming "];
  quadratic_programming [label="Quadratic Programming"];
  convex_programming [label="Convex Programming"];
  geometric_programming [label="Geometric Programming"];
  quasiconvex_programming [label="Quasiconvex Programming"];
  linear_programming [label="linear programming"];
  ILP_TUM [label="ILP over TUM"];
  ILP_TDI [label="ILP with TDI"];
  ILP_nearly_TUM[label="ILP with Nearly TUM"];
  violator_space [label="Violator Space"];
  lp_type [label="LP-type"];
  
  independent_arc_cover_partition [label="Independent Arc Cover Partition"];
  ILP_nearly_TUM->independent_arc_cover_partition;
  max_weight_independent_set_interval_graph [label="Maximum weight independent set interval graph"];
  max_independent_set_interval_graph [label="Maximum independent set interval graph"];
  linear_programming -> ILP_TDI -> ILP_TUM;
  linear_programming -> ILP_nearly_TUM -> ILP_TUM;
  ILP_TUM->max_weight_independent_set_interval_graph->max_independent_set_interval_graph;
  quasiconvex_programming -> convex_programming -> semidefinite_programming -> second_order_cone_programming -> quadratic_programming -> linear_programming;
  convex_programming -> geometric_programming;
  violator_space -> lp_type -> linear_programming;
  // optimization problems
  min_cost_multi_commodity_transshipment [label="minimum cost multi-commodity transshipment"];
  max_flow [label="maximum flow"];

  weighted_bipartite_matching [label="max weight bipartite matching"];
  bipartite_matching [label="cardinality bipartite matching"];
  shortest_path_nonneg_weight [label="non-negative weighted shortest path"];
  shortest_path_weight [label="weighted shortest path"];
  shortest_path [label="shortest path"];
  shortest_odd_path [label="shortest odd path"];
  weighted_matching [label="maximum weight matching"];
  min_cost_perfect_matching [label="minimum cost perfect matching"];
  min_size_bipartite_vertex_cover [label="minimum size bipartite vertex cover"];
  stable_marriage [label="stable marriage problem"];
  stable_roommates [label="stable roommates problem"]
  stable_roommates -> stable_marriage;
  max_weight_stable_matching [label="max weight stable bipartite matching"];
  max_weight_stable_matching -> stable_marriage;
  capacited_bipartite_matching [label="capacited bipartite matching"];

  closure_problem [label="closure problem"]
  max_flow->closure_problem;

  submodular_flow [label="submodular flow"];
  polymatroid_intersection [label="polymatroid intersection"];
  
  all_pairs_shortest_path [label="all pairs shortest path"];
  min_cost_flow [label="minimum cost flow(transshipment)"];
  degree_constrained_orientation [label="degree constrained orientation"];
  max_flow_int [label="maximum flow with integer weights"];
  submodular_min [label="submodular minimization"];
  symmetric_submodular_min [label="symmetric submodular minimization"];
  symmetric_submodular_function_hereditary [label="symmetric submodular minimization over hereditary system"]
  hypergraph_min_cut [label="hypergraph global min cut"];
  element_connectivity [label="element connectivity"];

  submodular_flow -> degree_constrained_k_edge_connected_orientation;
  degree_constrained_k_edge_connected_orientation -> k_edge_connected_orientation;
  degree_constrained_k_edge_connected_orientation -> degree_constrained_orientation;
  submodular_flow -> min_cost_flow;
  linear_programming -> submodular_min -> symmetric_submodular_function_hereditary;
  submodular_min -> directed_min_cut;
  symmetric_submodular_function_hereditary -> symmetric_submodular_min;
  symmetric_submodular_min -> hypergraph_min_cut;
  symmetric_submodular_min -> element_connectivity;
  hypergraph_min_cut -> min_cut;
  min_cost_multi_commodity_transshipment -> min_cost_flow;
  min_cost_multi_commodity_transshipment -> all_pairs_shortest_path;
  min_cost_flow -> max_flow;
  max_flow -> max_flow_int;
  min_cost_flow -> weighted_bipartite_matching -> bipartite_matching -> regular_bipartite_matching;
  capacited_bipartite_matching -> bipartite_matching;
  max_flow_int -> bipartite_matching;
  min_cost_flow -> shortest_path_weight;
  submodular_flow -> polymatroid_intersection;
  linear_programming -> submodular_flow;
  linear_programming -> min_cost_multi_commodity_transshipment;
  shortest_path_weight -> shortest_path_nonneg_weight;
  shortest_path_nonneg_weight -> shortest_path;
  max_flow_int -> degree_constrained_orientation;
  degree_constrained_orientation -> bipartite_matching;
  degree_constrained_orientation -> eulerian_orientation;
  min_cost_perfect_matching -> weighted_matching;
  weighted_matching -> weighted_bipartite_matching;
  bipartite_matching -> min_size_bipartite_vertex_cover;

  degree_constrained_subgraphs -> b_matching;
  capacited_b_matching -> b_matching -> bipartite_b_matching->weighted_bipartite_matching;
  b_matching -> min_cost_perfect_matching;
  optimization_incidence_matrix_undirected [label="optimization on incidence matrix(undirected)"]
  optimization_incidence_matrix_directed [label="optimization on incidence matrix(directed)"]
  optimization_incidence_matrix_bidirected [label="optimization on incidence matrix(bidirected)"]
  optimization_incidence_matrix_bidirected -> optimization_incidence_matrix_undirected;
  optimization_incidence_matrix_bidirected -> optimization_incidence_matrix_directed;
  optimization_incidence_matrix_undirected -> capacited_b_matching;
  ILP_TDI -> optimization_incidence_matrix_bidirected;
  ILP_TUM -> optimization_incidence_matrix_directed;
  optimization_incidence_matrix_directed -> min_cost_flow;

  min_cost_flow -> shortest_s_t_cycle;
  
  // scheduling
  //single_machine_total_weighted_completion_time; // greedy
   //Minimizing Makespan with Preemptions on N machines, polytime
   //Qm | prmp | Cmax
   //Qm | rj,prmp | Cmax
   //Pm || sum Cj
   //Qm | prmp | sum Cj 
   //Qm | prmp | Lmax
   //F2 || Cmax
   //F2 | block | Cmax 
   //J2 || Cmax
   //O2 || Cmax 
   // Om | prmp | Cmax
   // Om | prmp | Lmax
   //Om | rj,pij = 1 | Cmax
  // matroids
  polymatroid_intersection [label="polymatroid intersection"];
  polymatroid_optimization [label="polymatroid optimization"];
  minimum_spanning_arborescence [label="minimum spanning arborescence"];
  matroid_optimization [label="matroid optimization"];
  matroid_intersection [label="matriod intersection"];
  minimum_spanning_tree [label="minimum spanning tree"];
  matriod_partition [label="matriod partition"];
  forest_decomposition [label="forest decomposition"];
  rooted_k_edge_connection [label="rooted $k$-edge-connection"];
  regular_bipartite_matching [label="matching on regular bipartite graphs"]
  polymatroid_intersection -> polymatroid_optimization;
  polymatroid_intersection -> matroid_intersection;
  polymatroid_optimization -> matroid_optimization;
  matroid_intersection -> matroid_optimization -> minimum_spanning_tree; 
  matroid_intersection -> weighted_bipartite_matching;
  matroid_intersection -> rooted_k_edge_connection;
  matroid_intersection -> matriod_union_independence_oracle;
  matriod_union_independence_oracle -> matriod_partition -> forest_decomposition;
  matriod_partition->maximum_density_subgraph;
  rooted_k_edge_connection -> minimum_spanning_arborescence;
  minimum_spanning_arborescence -> minimum_spanning_tree;

  minimum_t_join -> minimum_mean_length_circuit;
  chinese_postman_problem;
  eulerian_orientation [label="eulerian orientation"];
  directed_min_cut [label="global directed minimum cut"];
  min_cut [label="global minimum cut"];
  edge_connectivity [label="edge connectivity"];
  directed_min_cut -> min_cut;
  min_cut -> edge_connectivity;

  // String matching problems
  exact_string_matching [label="exact string matching"];
  n_dimensional_pattern_matching [label="n dimensional pattern matching"];
  exact_string_matching_with_dont_cares [label="exact string matching with don't cares"];
  regular_expression_matching [label="regular expression matching"];
  regular_expression_substring_matching [label="regular expression substring matching"];
  regular_expression_substring_matching -> exact_string_matching_with_dont_cares;
  regular_expression_substring_matching -> regular_expression_matching;
  exact_string_matching_with_dont_cares -> exact_string_matching;
  n_dimensional_pattern_matching -> exact_string_matching;

  // DP
  generic_shortest_path_superior [label="generic shortest path superior"];
  generic_shortest_path_dag [label="generic shortest path for DAGs"];
  count_paths_dag [label="number of paths in a DAG"];
  longest_path_dag [label="longest path in a DAG"];
  
  widest_path [label="widest path problem"];
  undirected_widest_path [label="undirected widest path problem"];
  
  generic_shortest_path_superior -> widest_path;
  widest_path -> undirected_widest_path;
  //all_pairs_widest_path;
  minimum_spanning_tree -> undirected_widest_path;
  generic_shortest_path_superior -> shortest_path_nonneg_weight;
  generic_shortest_path_dag -> count_paths_dag;
  generic_shortest_path_dag -> longest_path_dag;
  
  // Sequence Alignment
  cyclic_alignment -> global_alignment;
  cyclic_alignment -> cyclic_longest_common_subsequence;
  alignment_boundary -> global_alignment;
  local_alignment;
  tree_edit_distance -> levenshtein_distance;
  global_alignment -> levenshtein_distance -> longest_common_subsequence;
  alignment_boundary -> fitting_alignment;
  alignment_boundary -> overlapping_alignment -> semiglobal_alignment;
  fitting_alignment -> exact_string_matching_with_dont_cares;
  exact_string_matching -> cyclic_string_equivalence;
  cyclic_longest_common_subsequence -> longest_common_subsequence -> longest_increasing_subsequence
  longest_common_subsequence -> shortest_common_supersequence;
  
  longest_palindromic_substring;
  minimum_palindromic_factorization;

  comparison_sort -> integer_sort;

  max_clique_perfect_graph [label="maximum clique on perfect graph"];
  graph_coloring_perfect_graph [label="graph coloring on perfect graph"];

  
  tree_isomorphism [label="tree isomorphism"];
  k_core_number [label="k-core number"];
  shortest_even_cycle [label="shortest_even_cycle"];
  // Done
  // sequential knapsack
  
  circular_arc_maximum_independent_set;
  circular_arc_minimum_clique_cover;
  circular_arc_minimum_dominating_set;
  proper_circular_arc_maximum_weight_clique;
  proper_circular_arc_coloring;

  selection_column_sorted_matrix;
  selection_sorted_matrix;
  search_sorted_matrx;
  // Todo
  // Modular decomposition http://en.wikipedia.org/wiki/Modular_decomposition
  // reconize total unimodularity 
  // stable matching(bipartite), egalitarian(maximum weight), minimum regret

  // The Generalized Distributive Law
  // http://cstheory.stackexchange.com/questions/750/have-any-generalizations-of-maximum-weight-matching-been-studied
  // generalized problem over semirings
  //longest_alternating_subsequence
}