commit eade7c24f28a2143201855e30b4e0b0b1638ae20 parent 2d2ad7228a6d9691982621ee08a72e0367a69a34 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Sat, 21 Jun 2025 20:15:46 +0200 Merge branch 'master' of a3nm.net:git/wiki_research Diffstat:
69 files changed, 509 insertions(+), 22 deletions(-)
diff --git a/1_critical b/1_critical @@ -0,0 +1,7 @@ +# 1 critical + +The [structure] with a single [domain_element] and every [relation] contains only the [tuple] mentioning only that element + +aka "well of positivity" in [gogacz2014all] + +Up: [dependency_expressiveness] diff --git a/2_disjoint_paths_undirected b/2_disjoint_paths_undirected @@ -0,0 +1,5 @@ +# 2 disjoint paths undirected + +Studied in [humeau2025two] + +Up: [disjoint_paths_undirected] diff --git a/2sat b/2sat @@ -1,16 +1,16 @@ # 2SAT -[satisfiability_boolean] of [2cnf] +The [satisfiability_boolean] problem over [2CNF] -Can be solved in [linear_time] via [strongly_connected_component], is [nl_complete] +It is tractable: +- Can be solved in [linear_time] via [strongly_connected_components] +- Is [nl_complete] However: -- The [max_sat] problem of satisfying the largest number of clauses of a [2cnf] is [nptime]-hard ([garey_johnson] LO5) -- The [sharp_satisfiability] problem of counting the satisfying assignments is [nptime]-hard, even for [monotone2cnf] +- [MAX_2SAT] is [NP_hard] +- The [sharp_satisfiability] problem of counting the satisfying assignments is [NP_hard] even for [monotone2cnf] -Generalization: [max_2sat] - -See also: [3sat] +See also: [3sat], [Max_2sat] Up: [sat_variants] diff --git a/3sat b/3sat @@ -0,0 +1,11 @@ +# 3SAT + +The [Boolean_satisfiability] problem on [3CNF] formulas + +It is [np_complete] + +[3sat_variants] + +Up: [sat_variants] + +See also: [2sat], [schaefers_dichotomy_theorem] diff --git a/acyclic_sjfcq b/acyclic_sjfcq @@ -0,0 +1,7 @@ +# Acyclic SJFCQ + +A [SJFCQ] which is [CQ_acyclic] + +Up: [conjunctive_query_acyclic], [SJFCQ] + +Aliases: acyclic SJFCQs diff --git a/algorithms_on_compressed_data b/algorithms_on_compressed_data @@ -0,0 +1,11 @@ +# Algorithms on compressed data + +name given in [lohrey2024enumeration] + +- [pattern_matching_compressed] +- [enumeration_slp] +- [lohrey2024enumeration] for [enumeration_mso] + +Up: [compression], [algorithms] + +See also: [compression_algorithm], [SLP] diff --git a/automata_nondeterministic_partially_ordered b/automata_nondeterministic_partially_ordered @@ -0,0 +1,9 @@ +# Automata nondeterministic partially ordered + +- [automaton_universality]: [kroetzsch2017complexity] + +Up: [automata_nondeterministic] + +See also: [partial_order] + +Aliases: nondeterministic partially ordered automaton, nondeterministic partially ordered automata diff --git a/berkholz2017answering b/berkholz2017answering @@ -0,0 +1,10 @@ +# Berkholz2017answering + +"Answering Conjunctive Queries under Updates" + +[academic_paper] by [christoph_berkholz], [jens_keppeler], [nicole_schweikardt] + +- [q_hierarchical]: [CQs] for which an [enumeration_constant_delay] [data_structure] can be [maintained_under_updates] +- [lower_bounds] assuming [omv_conjecture] + +Up: [incremental_maintenance_enumeration] diff --git a/circuit_restructuring b/circuit_restructuring @@ -0,0 +1,7 @@ +# Circuit restructuring + +The [computational_problem] of changing a [structured_circuit] to follow a different [vtree]. + +Studied for [probabilistic_circuits] in [zhang2024restructuring]. + +Up: [computational_problem], [structuredness] diff --git a/common_non_subsequence b/common_non_subsequence @@ -0,0 +1,7 @@ +# Common non subsequence + +Given a set S of strings, a *common non subsequence* is a string T which is a [subsequence] of no string in S + +[computational_problem]: [shortest_common_non_subsequence] + +Up: [subsequence] diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic @@ -9,7 +9,7 @@ the evaluation problem is in the complexity class [logcfl], and the the complexi We can test in linear time if a [hypergraph] is acyclic and if so build the join tree: [gyo] algorithm - not so obvious to understand where the [linear_time] claim comes from... -For Boolean queries, even with [self_join], if the query is not acyclic then we can reduce from a hard problem ([triangle_detection] ou [hyperclique_detection]) +For Boolean queries, even with [self_joins], if the query is not acyclic then we can reduce from a hard problem ([triangle_detection] ou [hyperclique_detection]) Special case: [conjunctive_query_hierarchical] @@ -17,6 +17,10 @@ Testing if a CQ is acyclic ([elimination_order]): - while there is a vertex v whose [closed_neighborhood] (includes v itself) is included in some edge, then delete the vertex +Special case: + +- [acyclic_SJFCQ] + See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_query_cyclic] Up: [conjunctive_query] diff --git a/consistent_subsequence b/consistent_subsequence @@ -0,0 +1,9 @@ +# Consistent subsequence + +Given a positive set of strings P and negative set of strings N, a *consistent subsequence* is a string S which: +- is a [subsequence] of every string in P ([common_subsequence]) +- and is a [subsequence] of no string in N ([common_non_subsequence]) + +[Computational_problem]: [consistent_subsequence_problem] + +Up: [subsequence] diff --git a/consistent_subsequence_problem b/consistent_subsequence_problem @@ -0,0 +1,5 @@ +# Consistent subsequence problem + +shortest consistent subsequence, and longest consistent subsequence, can be solved in [PTIME] for fixed number of positive and negative strings, see [crochemore2003directed] Section 4.6 + +Up: [computational_problem], [consistent_subsequence] diff --git a/context_free_grammar b/context_free_grammar @@ -40,9 +40,10 @@ ## Extensions - [probabilistic_grammar] +- [multiple_context_free_grammar] See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series], [Hyperedge_replacement_grammar] -Up: [formal_language_theory] +Up: [formal_language_theory], [formal_grammar] Aliases: CFG, CFGs, context free grammars, context-free grammars diff --git a/context_free_language_slender b/context_free_language_slender @@ -0,0 +1,9 @@ +# Context free language slender + +A [context_free_language] which is [language_slender] + +[koechlin2022new]: any such language admits an [unambiguous_CFG], so it is not [inherently_ambiguous] + +Up: [context_free_language], [language_slender] + +See also: [context_free_grammar_slender] diff --git a/database_theory_complexity b/database_theory_complexity @@ -0,0 +1,9 @@ +# Complexity measures in database theory + +- [combined_complexity] +- [data_complexity] +- [query_complexity] + +introduced in [vardi1982complexity] + +Up: [database_theory] diff --git a/database_theory_techniques b/database_theory_techniques @@ -0,0 +1,6 @@ +# Database theory techniques + +- [shredding], going from high arity to [arity_two] +- [ucq_to_cq] + +Up: [database_theory] diff --git a/decision_problem b/decision_problem @@ -6,4 +6,4 @@ Up: [computational_problem], [boolean] See also: [decision], [decidability] -Aliases: decision problems, decide +Aliases: decision problems, decide, deciding diff --git a/disjoint_paths_undirected b/disjoint_paths_undirected @@ -0,0 +1,15 @@ +# Disjoint paths on undirected graphs + +Given an [undirected_graph] G and vertices s_1, t_1, ..., s_k, t_k, decide whether there exist k [disjoint_paths] connecting s_i and t_i for each i + +It is is [NP_complete] if k is not fixed ([karp1975computational], cited in [liu2025disjoint]) + +- For any constant k, by [Robertson_Seymour] it is [PTIME], in O(n^3), and even in [almost_linear_time] by [korhonen2024minor] +- It is [FPT] parameterized by k + - cf also [lokshtanov2021exponential], on [planar_graphs], for the dependency on k + +Cf [liu2025disjoint] for a review and for a generalization to [modularity_constraints] + +Special case: [2_disjoint_paths_undirected] + +Up: [disjoint_paths] on [undirected_graphs] diff --git a/element_distinctness_problem b/element_distinctness_problem @@ -0,0 +1,9 @@ +# Element distinctness problem + +https://en.wikipedia.org/wiki/Element_distinctness_problem + +The [computational_problem] of testing if all elements of [list] are distinct + +Up: [computational_problem], [list] + +See also: [sorting], [hash_function] diff --git a/exact_matching b/exact_matching @@ -1,7 +1,7 @@ # Exact matching -- Input: [graph_bipartite] G with bicolored edges, integer k -- Output: does G contain a matching with exactly k red edges +- Input: [bipartite_graph] G with bicolored edges, integer k +- Output: does G contain a [perfect_matching] with exactly k red edges [maalouly2022exact]: this is in [rp] and not known to be in [ptime] diff --git a/fekete_lemma b/fekete_lemma @@ -0,0 +1,7 @@ +# Fekete lemma + +https://fr.wikipedia.org/wiki/Lemme_sous-additif + +If a [sequence] is [subadditive], i.e., u_{i+j} \leq u_i + u_j, then the [limit] of u_n/n at infinity exists (it may be minus infinity). This is a sufficient condition. + +Up: [lemma], [subadditive] diff --git a/first_order_projection b/first_order_projection @@ -0,0 +1,11 @@ +# First order projection + +A very limited kind of [reduction] defined via [first_order_logic] + +- [arratia2003note] +- [allender2020note] +- [allender1993first] + +Up: [reduction] + +See also: [first_order_logic] diff --git a/flat_wall_theorem b/flat_wall_theorem @@ -0,0 +1,7 @@ +# Flat wall theorem + +Explained in [kawarabayashi2018new] + +Up: [theorem] + +See also: [Robertson_seymour] diff --git a/formal_language_theory b/formal_language_theory @@ -1,6 +1,6 @@ # Formal language theory -Studies [formal_language] +Studies [formal_languages] ## Concepts @@ -9,6 +9,7 @@ Studies [formal_language] - [empty_word] - [formal_language] - [prefix], [suffix], [subword], [subsequence] +- [chomsky_hierarchy] ## Operations diff --git a/frederickson1993optimal b/frederickson1993optimal @@ -0,0 +1,10 @@ +# frederickson1993optimal + +Presents an [algorithm] the k smallest elements of a [min_heap] in O(k), when k is much smaller than the size of the heap +- the elements are not [sorted] +- in fact according to [gawrychowski2024revisiting] Lemma 5.4 we can even get the k-th element + - which then makes it easy to get the k smallest elements + +Up: [academic_paper] about [heap] + +See also: [selection_algorithm] diff --git a/graph_matching_covered b/graph_matching_covered @@ -0,0 +1,13 @@ +# Matching-covered graph + +A *matching-covered graph* is a [graph] where every [edge] is contained in a [perfect_matching] + +Discussed in [he2017perfect] + +Can be [graph_decomposed] with [bricks] and [braces] by the [tight_cut_decomposition], cf [lovasz1987matching] cited in [he2017perfect] + +Up: [graph] + +See also: [matching] + +Aliases: matching covered graph, matching-covered graph diff --git a/graph_minor_testing b/graph_minor_testing @@ -0,0 +1,11 @@ +# Graph minor testing + +Given [undirected_graphs] G and H, decide whether G a [graph_minor] of H + +Can be done in [almost_linear_time] for fixed H [korhonen2024minor] + +Special cases: +- [planarity_testing] +- [disjoint_paths] + +Up: [computational_problem], [graph_minor] diff --git a/greenlaw1995limits b/greenlaw1995limits @@ -0,0 +1,7 @@ +# Greenlaw1995limits + +https://homes.cs.washington.edu/~ruzzo/papers/limits.pdf + +discusses [p_complete] as a limit to [parallelism] + +Up: [books] on [p_complete] diff --git a/hamiltonian_cycle b/hamiltonian_cycle @@ -8,6 +8,8 @@ - [hamiltonian_cycle_square] on [graph_square] - [hamiltonian_cycle_multiple] going multiple times over each [vertex] +Special case: [Knight's_tour] + Up: [problem] on [graph] See also: [graph_eulerian], [hamiltonian_path] diff --git a/hamiltonian_path b/hamiltonian_path @@ -0,0 +1,9 @@ +# Hamiltonian path + +A [simple_path] that goes via all vertices of a [graph] + +The [computational_problem] of [deciding] whether such a path exists in an input [undirected_graph] is [np_complete] + +See also: [hamiltonian_cycle], [traveling_salesperson_problem], [k_path], [path_length], [eulerian_path] + +Up: [path] diff --git a/hole b/hole @@ -10,3 +10,5 @@ - [antihole] Up: [cycle_induced] + +Aliases: holes diff --git a/incidence_poset b/incidence_poset @@ -0,0 +1,11 @@ +# Incidence poset + +A [partial_order] defined from an [undirected_graph]: +- elements are the [vertices] and the [edges] +- We set x <= y iff x is a [vertex], y is an [edge], and x belongs to y + +It has [partial_order_height] 2 + +Up: [graph_theory] + +See also: [incidence_graph] diff --git a/interactive_boolean_evaluation b/interactive_boolean_evaluation @@ -0,0 +1,9 @@ +# Interactive boolean evaluation + +- [stochastic_boolean_function_evaluation] + +Connected problem in [clustering]: [black2024clustering] + +See also: [human_assisted_graph_search], [graph_learning] + +Up: [boolean_function] diff --git a/matrix_identity b/matrix_identity @@ -0,0 +1,7 @@ +# Matrix identity + +The [square_matrix] with 0 everywhere except that it has 1 on the [main_diagonal] + +Up: [matrix] + +See also: [identity_element] diff --git a/max_2sat b/max_2sat @@ -0,0 +1,11 @@ +# Max 2sat + +The [computational_problem] [MAX_SAT] on an input [2CNF] + +It is [NP_hard]: cf [garey_johnson] LO5 + +Generalization: [max_csp] + +Up: [max_sat], [2CNF] + +See also: [2SAT] diff --git a/maximum_matching_bipartite b/maximum_matching_bipartite @@ -0,0 +1,8 @@ +# Maximum matching bipartite + +The [maximum_matching_problem] on [bipartite_graphs] + +- [Network_flow] encoding +- More efficient: [Hopcroft_karp] algorithm + +Up: [maximum_matching_problem], [graph_bipartite] diff --git a/metacomplexity b/metacomplexity @@ -0,0 +1,7 @@ +# Metacomplexity + +https://simons.berkeley.edu/programs/Meta-Complexity2023 + +Complexity of problems where we ask what is the complexity of an input, e.g., [kolmogorof_complexity], [minimum_circuit_size_problem] + +Up: [computational_complexity] diff --git a/mildly_context_sensitive_grammar b/mildly_context_sensitive_grammar @@ -0,0 +1,5 @@ +# Mildly context sensitive grammar + +https://en.wikipedia.org/wiki/Mildly_context-sensitive_grammar_formalism + +Up: [grammar_variants], [formal_grammar] diff --git a/monotone b/monotone @@ -4,4 +4,6 @@ Something that grows when the input grows Up: [mathematics] -See also: [homomorphism_closed], [positive_vs_monotone], [positive], [Preserved_under_extensions] +See also: [homomorphism_closed], [positive_vs_monotone], [positive], [Preserved_under_extensions], [monotonic_sequence] + +Aliases: monotonicity diff --git a/monotonic_sequence b/monotonic_sequence @@ -0,0 +1,9 @@ +# Monotonic sequence + +https://en.wikipedia.org/wiki/Monotonic_sequence + +A [sequence] which is [monotone] +- can be increasing or decreasing +- strictly or not + +Up: [sequence], [monotone] diff --git a/multiple_context_free_grammar b/multiple_context_free_grammar @@ -0,0 +1,7 @@ +# Multiple context free grammar + +[seki1991multiple] + +Up: [context_free_grammar] + +Aliases: MCFG, MCFGs diff --git a/network_creation_game b/network_creation_game @@ -0,0 +1,6 @@ +# Network creation game + +- [fabrikant2003network] +- [alon2010basic] + +Up: [game_on_graphs] diff --git a/parameterized_algorithm b/parameterized_algorithm @@ -0,0 +1,7 @@ +# Parameterized algorithm + +An [algorithm] with a [parameter] used in the [computational_complexity] analysis + +Up: [parameterized_complexity], [algorithm] + +Aliases: algorithm_parameterized diff --git a/polynomial_homogeneous b/polynomial_homogeneous @@ -0,0 +1,10 @@ +# Homogeneous polynomial + +A [multivariate_polynomial] whose nonzero terms all have the same [degree] +- i.e., the total sum of the exponents of every [monomial] is the same + +https://en.wikipedia.org/wiki/Homogeneous_polynomial + +Up: [polynomial] + +Aliases: homogeneous polynomial diff --git a/polynomial_multivariate b/polynomial_multivariate @@ -3,3 +3,5 @@ A [polynomial] which involves multiple [variables] Up: [polynomial] + +Aliases: multivariate polynomial, multivariate polynomials diff --git a/poset_width b/poset_width @@ -0,0 +1,9 @@ +# Poset width + +The *width* of a [poset] is the [cardinality] of its largest [antichain] + +Can be computed in [PTIME] via [dilworths_theorem] using a [flow_algorithm] + +Up: [partial_order] + +See also: [dilworths_theorem], [chain_partitioning], [partial_order_height] diff --git a/priority_queue b/priority_queue @@ -0,0 +1,16 @@ +# Priority queue + +https://en.wikipedia.org/wiki/Priority_queue + +[implementations]: +- [leftist_heap] + +[Academic_papers]: +- [thorup2007equivalence]: [equivalence] between [priority_queue] and [sorting] + +Special cases: +- [priority_queue_monotone] + +Up: [queue] + +See also: [predecessor_problem], [prefix_U1] diff --git a/priority_queue_monotone b/priority_queue_monotone @@ -0,0 +1,7 @@ +# Priority queue monotone + +https://en.wikipedia.org/wiki/Monotone_priority_queue + +A [priority_queue] where the sequence of the priorities of extracted items is a [monotonic_sequence] + +Up: [priority_queue], [monotone] diff --git a/probabilistic_grammar b/probabilistic_grammar @@ -0,0 +1,7 @@ +# Probabilistic grammar + +A [context_free_grammar] where for each [nonterminal] you have a [probability_distribution] on the applicable [productions] + +Can be used when generating [words] of the [grammar] + +Up: [context_free_grammar] diff --git a/production b/production @@ -0,0 +1,10 @@ +# Production + +A pair of [proto_words]: expresses that the [LHS] can be rewritten to the [RHS] + +- For [CFGs], the [LHS] is always a [nonterminal] +- For [noncontracting_grammars], the [RHS] must be at least as long as the [LHS] + +Up: [formal_grammar] + +Aliases: productions diff --git a/provenance_games b/provenance_games @@ -0,0 +1,7 @@ +# Provenance for games + +[Academic_papers] by [val_tannen] and [erich_graedel] + +- [buchi_games] + +See also: [provenance_logics] diff --git a/provenance_reasoning b/provenance_reasoning @@ -0,0 +1,7 @@ +# Provenance for reasoning + +With [description_logics]: +- [ceylan2022explanations] +- [bourgaux2023semiring] + +Up: [provenance] for [reasoning] diff --git a/pushdown_automaton_deterministic b/pushdown_automaton_deterministic @@ -0,0 +1,10 @@ +# Pushdown automaton deterministic + +- [universality_automata_pushdown_deterministic] +- [equivalence_automata_pushdown_deterministic] + +Up: [pushdown_automaton] + +Aliases: deterministic pushdown automaton + +Aliases: DPDA, DPDAs diff --git a/rabin1963probabilistic b/rabin1963probabilistic @@ -0,0 +1,7 @@ +# Rabin1963probabilistic + +[academic_paper] by [rabin] + +Up: [automata_probabilistic], [academic_paper] + +See also: [isolated_cut_point] diff --git a/reachability_all_pairs b/reachability_all_pairs @@ -0,0 +1,13 @@ +# All pairs reachability + +- On [undirected_graphs]: + - Easy, it suffices to compute [connected_components] +- On [directed_graphs]: + - amounts to [transitive_closure] + - can be done in time O(mn) + - the result may have [quadratic] size, even if the [graph] is [sparse_graph] + - equivalent to [boolean_matrix_multiplication] + +Up: [reachability] + +See also: [all_pairs_shortest_path] diff --git a/recamans_sequence b/recamans_sequence @@ -0,0 +1,5 @@ +# Recaman's sequence + +https://en.wikipedia.org/wiki/Recam%C3%A1n%27s_sequence + +Up: [sequence] diff --git a/satisfiability_weighted_monotone_cnf b/satisfiability_weighted_monotone_cnf @@ -0,0 +1,7 @@ +# Satisfiability weighted monotone CNF + +Given a [monotone_cnf] and weight k, decide if there is a satisfying assignment of [hamming_weight] at most k + +It is [np_hard] by immediate reduction from [vertex_cover] + +Up: [satisfiability_weighted], [monotone_cnf] diff --git a/sentence b/sentence @@ -0,0 +1,7 @@ +# Sentence + +A logic [formula] without [free_variables] + +Up: [logic] + +See also: [boolean_query] diff --git a/shortest_common_non_subsequence b/shortest_common_non_subsequence @@ -0,0 +1,11 @@ +# Shortest common non subsequence + +Given a set S of strings, find the shortest [common_non_subsequence] + +can be solved in [PTIME], cf [crochemore2003directed] section 4.4 + +[timkovsky1989complexity] + +Up: [computational_problem], [common_non_subsequence] + +See also: [shortest_distinguishing_subsequence], [shortest_common_supersequence] diff --git a/simple_regular_expressions b/simple_regular_expressions @@ -0,0 +1,8 @@ +# Simple regular expressions + +defined in [figueira2024boundedness] + +allows w^* for a [word] w, or a [regular_expression] without [Kleene_star] +- allows [regular_expression_repetition] + +Up: [regular_expression] diff --git a/sjfcq b/sjfcq @@ -4,6 +4,8 @@ [dichotomy] for [pqe] in [dalvi2007efficient] +Special case: [acyclic_SJFCQ] + Up: [conjunctive_query], [self_join] Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free, self-join-free CQ, self-join-free CQs, conjunctive query self join free, SJFCQs diff --git a/topological_minor b/topological_minor @@ -4,6 +4,8 @@ [graph_minor] and topological minors are equivalent if the minor is [graph_cubic] +See [grohe2021finding] for the [computational_problem] of finding a [topological_embedding] + Up: [graph_minor] See also: [excluded_topological_minor], [subdivision] diff --git a/uc2rpq_boundedness b/uc2rpq_boundedness @@ -0,0 +1,5 @@ +# UC2RPQ boundedness + +- [barcelo2019boundedness]: the problem is [EXPSPACE_complete] + +Up: [boundedness], [UC2RPQ] diff --git a/ucq_to_cq b/ucq_to_cq @@ -1,10 +1,10 @@ -# Ucq to cq +# UCQ to CQ -techniques to replace [UCQs] by [CQs] in [hardness] [proofs] +Techniques to replace [UCQs] by [CQs] in [hardness] [proofs] - e.g., - taking a [disjunction] on [path] lengths - increasing the [arity] with an extra [attribute] - cf [ability_to_count] in [atserias2008digraph] -Up: [union_of_conjunctive_queries] +Up: [database_theory_techniques] diff --git a/ucrpq_boundedness b/ucrpq_boundedness @@ -0,0 +1,6 @@ +# UCRPQ boundedness + +- [figueira2024boundedness]: for [UCRPQs] with [simple_regular_expressions] + - the problem is then [Pi2_complete] + +Up: [boundedness], [UCRPQ] diff --git a/univeral_hashing b/univeral_hashing @@ -0,0 +1,11 @@ +# Univeral hashing + +https://en.wikipedia.org/wiki/Universal_hashing + +A guarantee on [hash_function] on the fact that the probability of collisions is what you would obtain if the hashing function were truly random + +Can be achieved in a [field] with x -> ax + b + +Can be useful to scramble inputs to a [boolean_function] ([scrambling_technique]) + +Up: [hash_function] diff --git a/vertex_cover b/vertex_cover @@ -17,15 +17,12 @@ A vertex cover in a [graph] is a subset of vertices such that every edge is inci ## [computational_problem] - [minimum_vertex_cover] - -## [theorems] - -- [koenigs_theorem] in [graph_bipartite] relates vertex covers to [maximum_matchings] +- can be studied in [parameterized_complexity] ## Connections - A vertex cover is at least as large as a [maximum_matching], because each edge in the matching must be covered by a vertex and these vertices must be different for each edge. - - [koenigs_theorem]: on [graph_bipartite] they are equal + - [koenigs_theorem]: on [bipartite_graphs] they have the same size - The [complement] of a vertex cover is an [independent_set] so [minimum_vertex_cover] corresponds to [maximal_independent_set] See also: [edge_cover], [vertex_packing], [independent_set], [hitting_set], [set_cover] diff --git a/wang2021query b/wang2021query @@ -0,0 +1,11 @@ +# Wang2021query + +"Query evaluation by circuits" + +[academic_paper] by [yilei_wang], [ke_yi] + +Assumes [degree_constraints] on the [database] + +Connections to [optimal_joins] / [polymatroid_bound] + +Up: [academic_paper] on [enumeration_cqs]