Translating between the representations of an acyclic convex geometry of bounded degree

Basic Information

• Paper ID: 2506.24052
• Title: Translating between the representations of an acyclic convex geometry of bounded degree
• Authors: Oscar Defrain, Arthur Ohana, Simon Vilmin (Aix-Marseille Université, CNRS, LIS)
• Classification: cs.DS (Data Structures and Algorithms), cs.DM (Discrete Mathematics), math.CO (Combinatorics)
• Publication Time/Conference: Accepted at ISAAC 2025 (36th International Symposium on Algorithms and Computation)
• Paper Link: https://arxiv.org/abs/2506.24052

Abstract

This paper investigates the conversion problem between irreducible closed sets and implicational bases in closure systems. The complexity status of this problem remains unknown and is known to generalize the celebrated hypergraph dualization problem, even in the case of acyclic convex geometries. The paper focuses on the degree parameter—the maximum number of times an element appears in implications. The research demonstrates that when this parameter is bounded, the problem becomes tractable, even when relaxed to the concepts of premise-degree and conclusion-degree. The algorithms rely on structural properties of acyclic convex geometries and employ various algorithmic enumeration techniques including resolution graph traversal, saturation techniques, and sequential methods exploiting acyclicity, running in incremental-polynomial time. Finally, the paper proves that the running time cannot be improved to polynomial delay using standard flashlight search frameworks.

Research Background and Motivation

1. Core Problem

Closure systems are fundamental structures in mathematics and computer science, appearing in different forms across database theory, Horn logic, lattice theory, and other fields. Closure systems admit multiple representations, with two of the most fundamental being:

• Irreducible closed sets (ICS): Special sets within the closure system
• Implicational bases: Sets of implications of the form A→B

These two representations are typically incomparable in size and practicality—in some cases, the cardinality of the minimal implicational base can be exponentially larger than the number of irreducible closed sets, and vice versa.

2. Problem Importance

Different representation methods have significant impacts on the computational complexity of certain algorithmic tasks (such as inference, abduction, and identification of lattice properties). Therefore, the ability to convert between these two representations is crucial:

• ICS·Enum: Enumerating irreducible closed sets from an implicational base
• MIB·Gen: Generating a compact implicational base from irreducible closed sets

3. Limitations of Existing Approaches

• The problem generalizes hypergraph dualization, whose complexity has been studied for decades but remains unsolved
• In general closure systems, the problem has been proven harder than distributive lattice dualization
• Even in the restricted class of acyclic convex geometries, the problem remains as hard as hypergraph dualization
• No known subexponential-time algorithms exist

4. Research Motivation

The paper focuses on acyclic convex geometries, a special yet important class of closure systems, seeking tractable cases by restricting the degree parameter. Degree reflects the structural complexity of the implicational base and is a natural and practical parameter.

Core Contributions

1. Theoretical Contribution: Proves that ICS·Enum and MIB·Gen problems are tractable in acyclic convex geometries with bounded degree, even when relaxed to bounded premise-degree or conclusion-degree.
2. Algorithmic Contribution:
   • Proposes an incremental-polynomial time algorithm for ICS·Enum with bounded conclusion-degree (based on hypergraph minimum hitting set enumeration)
   • Proposes an incremental-polynomial time algorithm for ICS·Enum with bounded premise-degree (based on resolution graph traversal techniques)
   • Proposes a polynomial-time algorithm for CB·Gen with bounded degree (critical base generation, using saturation techniques)
3. Technical Innovation: Introduces a top-down sequential method that exploits acyclicity by processing elements in topological order.
4. Complexity Lower Bounds: Proves that polynomial-delay algorithms cannot be obtained using flashlight search frameworks, and that the extended problem ICS·Ext remains NP-complete even with bounded degree.
5. Structural Results: Provides deep analysis of critical generators in acyclic convex geometries, proving that critical bases are minimal under various degree metrics.

Detailed Methodology

Task Definitions

Problem 1: ICS·Enum (Irreducible Closed Set Enumeration)

• Input: Implicational base (X, Σ)
• Output: All irreducible closed sets of the associated closure system

Problem 2: MIB·Gen (Minimal Implicational Base Generation)

• Input: Base set X and irreducible closed sets irr(C) of closure system (X, C)
• Output: A minimal implicational base of (X, C)

Key Parameter Definitions:

• Degree deg(Σ) = max_x |{A→B ∈ Σ : x ∈ A∪B}|
• Premise-degree pdeg(Σ) = max_x |{A→B ∈ Σ : x ∈ A}|
• Conclusion-degree cdeg(Σ) = max_x |{A→B ∈ Σ : x ∈ B}|

Core Methodology: Top-Down Sequential Method

1. Basic Idea

Exploiting the topological structure of acyclic implicational bases, processing each element x₁,...,xₙ in topological order, utilizing information about ancestor elements when processing xᵢ.

Key Observation: In convex geometries, each irreducible closed set is attached to exactly one element (Proposition 2.1). Therefore, the problem can be decomposed into enumerating irr(x) for each element x.

2. Intermediate Problem: ACS+A·Enum

Defines attached closed set enumeration with ancestor solutions:

• Input: Acyclic implicational base (X, Σ), element x, and irr(y) for all ancestors y of x
• Output: irr(x)

Theorem 4.1: If ACS+A·Enum can output the i-th solution in time f(N,i), then ICS·Enum can output the j-th solution in time O(poly(N') + N'·f(N'+j,j)).

Bounded Conclusion-Degree Algorithm (Section 5)

Core Lemma (Lemma 5.1)

For M ∈ irr(x), there exists a minimum hitting set T of the premise hypergraph Hₓ = (⋃Eₓ, Eₓ) and an irredundant choice S ∈ S(T) such that: $M = \left(\bigcap S\right) \setminus \{x\}$

where Eₓ = {A : A→B ∈ Σ, x ∈ B}

Algorithm Strategy

1. Construct the premise hypergraph Hₓ (number of edges ≤ cdeg(x))
2. Enumerate all minimum hitting sets T of Hₓ (brute force, complexity |X|^O(k))
3. For each T, enumerate all irredundant choices S (complexity N^O(k))
4. Verify whether (⋂S){x} is an irreducible closed set

Theorem 5.3: There exists an incremental-polynomial time algorithm for ICS·Enum on acyclic implicational bases with bounded conclusion-degree.

Bounded Premise-Degree Algorithm (Section 6)

Resolution Graph Traversal Framework

Uses three conditions from the folklore theorem (Theorem 6.1):

1. Initial Solution: Use greedy completion GCₓ(∅) to find the first solution in polynomial time
2. Neighbor Function: Define N(M,y) based on hypergraph HM,y = (VM,y, EM,y), where EM,y = {A : A→B ∈ Σ, A\M={y}, B⊈M}
3. Strong Connectivity: Prove that the solution graph is strongly connected

Key Lemma (Lemma 6.4)

For M,M* ∈ irr(x), there exists y ∈ M*\M, T ∈ MHS(HM,y), and S ∈ S(T) such that M* ⊆ ⋂S.

Neighbor Function Definition

$N(M,y) = \left\{GC_x\left((M \cap \bigcap S) \cup \{y\}\right) : S \in S(T), T \in MHS(H_{M,y}), x \notin \phi\left((M \cap \bigcap S) \cup \{y\}\right)\right\}$

Theorem 6.9: There exists an incremental-polynomial time algorithm for ICS·Enum on acyclic implicational bases with bounded premise-degree.

Critical Base Generation Algorithm (Section 7)

Critical Generators

A set A is a critical generator for x if and only if:

• A = ex(φ(A)) (A is the set of extreme points of its closure)
• φ(A) ∈ min⊆{C : C ∈ C, x ∈ C, x ∉ ex(C)}

Key Property (Theorem 3.4): The critical base of an acyclic convex geometry is minimal in unit cardinality and aggregate cardinality.

Saturation Algorithm

Solves CGE+A·Dec (decision version with counterexamples):

1. Construct partial implicational base Σ' = {A→x : A ∈ F} ∪ {A→y : A ∈ critgen(y), y ∈ critanc(x)}
2. Use ACS+A·Enum to enumerate irr_C'(x)
3. If M ∈ irr_C'(x) \ irr_C(x) is found, extract missing critical generators from M (Lemma 7.1)
4. Otherwise, prove F = critgen(x) (Lemma 7.2)

Theorem 7.4: If ACS+A·Enum has an incremental-polynomial time algorithm, then CGE+A·Dec has a polynomial-time algorithm.

Theorem 1.2: There exists a polynomial-time algorithm to construct the critical base from irreducible closed sets of an acyclic convex geometry with bounded premise or conclusion-degree.

Technical Innovations

1. Top-Down Decomposition Strategy

• Innovation: First systematic exploitation of acyclicity for sequential decomposition, transforming global enumeration into local enumeration
• Advantage: Allows utilization of ancestor information when processing each element, significantly reducing search space

2. Dual Algorithm Strategy

• Conclusion-degree: Exploits combinatorial structure of hypergraph hitting sets
• Premise-degree: Exploits reconfiguration ideas of resolution graph traversal
• Uniformity: Both methods work within the same framework, demonstrating parameter symmetry

3. Clever Application of Saturation Techniques

• Reverse Verification: Identifies missing elements by constructing partial closure systems and detecting differences
• Polynomial Efficiency: Exploits minimality of critical bases to ensure algorithm efficiency

4. Structural Insights

• Universality of Critical Generators (Lemma 3.6): Premises of any implicational base contain critical generators
• Minimality of Degree (Lemma 3.7): Critical bases are minimal under all degree metrics
• Computability of Ancestor Relations (Corollary 3.5): Ancestor relations of critical bases can be recovered from irreducible closed sets alone

Experimental Setup

Note: This is a pure theoretical algorithms paper and does not include an experimental evaluation section. The paper's contributions lie in the design and complexity analysis of theoretical algorithms rather than empirical experiments.

Theoretical Verification Methods

1. Correctness Proofs: Verify algorithm correctness through rigorous mathematical proofs
2. Complexity Analysis: Provide detailed time complexity analysis
3. Constructive Examples: Illustrate algorithm operation and complexity lower bounds through concrete examples

Example Analysis

The paper provides multiple illustrative examples:

• Example 2.6: Demonstrates exponential gap between input and output sizes
• Figure 4: Illustrates reduction from MIS·Enum to ICS·Enum
• Figure 6: Shows that the number of minimum hitting sets can be exponentially large

Experimental Results

Main Theoretical Results

Theorem 1.1 (ICS·Enum Tractability): There exists an incremental-polynomial time algorithm to enumerate irreducible closed sets of an acyclic convex geometry given by an acyclic implicational base with bounded premise or conclusion-degree.

Theorem 1.2 (MIB·Gen Tractability): There exists a polynomial-time algorithm to construct the critical base of an acyclic convex geometry with bounded premise or conclusion-degree given by irreducible closed sets.

Complexity Lower Bounds

Theorem 3.9: In acyclic convex geometries, ICS·Enum, ACS·Enum, and MIB·Gen are all harder than MIS·Enum, even for implicational bases of height 2.

Theorem 3.10: The ACS·Enum problem is MIS·Enum-hard for acyclic implicational bases with conclusion-degree at most 2.

Theorem 8.2 (Limitations of Flashlight Search): The ICS·Ext problem is NP-complete even for acyclic implicational bases with simultaneously bounded degree, premise-degree, conclusion-degree, and dimension (4, 4, 2, 2 respectively).

This indicates that standard flashlight search frameworks cannot directly obtain polynomial-delay algorithms.

Generalization Results

Theorem 5.4: If for any element x, the premise hypergraph containing x in the conclusion has bounded dual dimension, then there exists an incremental-polynomial time algorithm for ICS·Enum.

Theorem 6.10: If for any irreducible closed set M and y∉M, the hypergraph HM,y has bounded dual dimension, then there exists an incremental-polynomial time algorithm for ICS·Enum.

Related Work

1. Closure System Representations

• Implicational Base Types: Canonical bases, canonical direct bases, D-bases, etc.
• Minimization Problems: Finding minimal implicational bases is typically difficult, but certain special bases (such as critical bases) can be computed efficiently in specific classes

2. Hypergraph Dualization

• MIS·Enum/MHS·Enum: Fredman-Khachiyan algorithm (quasi-polynomial output time)
• Special Cases: Polynomial-time algorithms for bounded dimension, bounded dual dimension, and other parameterized cases

3. Acyclic Convex Geometries

• History: Pioneering work by Hammer and Kogan (1995)
• Subsequent Research: Wild (1994), Santocanale and Wehrung (2014), Defrain et al. (2021)
• Ordered Convex Geometries: When the implication graph admits an ordering function, the problem reduces to hypergraph dualization

4. Other Tractable Classes

• Modular Lattices and k-intersecting Semi-distributive Lattices: Wilde (2000), Beaudou et al. (2017)
• Closure Spaces with Bounded Carathéodory Number: Wild (2017)

5. Enumeration Complexity

• Incremental-Polynomial Time: Time to output the i-th solution is poly(input_size + i)
• Polynomial Delay: Time between any two consecutive outputs is poly(input_size)
• Output-Polynomial Time: Total time is poly(input_size + output_size)

Positioning of This Work

This paper is the first to systematically investigate the impact of the degree parameter on the conversion problem in acyclic convex geometries, bridging the gap between ordered convex geometries (requiring stronger structure) and general acyclic convex geometries (whose difficulty was unknown).

Conclusions and Discussion

Main Conclusions

1. Tractability: In acyclic convex geometries, ICS·Enum and MIB·Gen problems are tractable when premise-degree or conclusion-degree is bounded
2. Algorithm Efficiency:
   • ICS·Enum: Incremental-polynomial time
   • MIB·Gen (via CB·Gen): Polynomial time (because critical base size is bounded)
3. Methodological Contribution: The top-down sequential method combined with resolution graph traversal and saturation techniques provides a general framework for handling acyclic structures
4. Complexity Boundaries: Proves the difficulty of polynomial delay, clarifying the limitations of algorithm improvements

Limitations

1. Complexity Dependence: Algorithm dependence on degree k is XP rather than FPT (running time N^O(k) rather than f(k)·poly(N))
2. Delay Limitations: Due to the nature of the top-down approach, polynomial delay cannot be achieved, only incremental-polynomial time
3. Class Restrictions: Results apply only to acyclic convex geometries, not to general closure systems
4. Parameter Restrictions: Requires bounded degree, while degree itself may grow with problem size

Future Directions

1. Generalization to Broader Classes

Question 8.1: Can ICS·Enum and CB·Gen be solved with polynomial delay in acyclic convex geometries with bounded degree?

Suggested Directions:

• Lower-bounded Closure Systems: Possess acyclic D-relations, may support topological sorting
• Graph Convexities: Exploit properties of underlying graph structures

2. Other Parameters

• Degeneracy: Analogous concept in hypergraph theory
• Dimension/Arity: Maximum premise size
• Carathéodory Number, Radon Number, Helly Number: Other parameters from convexity theory

3. FPT Algorithms

Key Bottleneck: Enumeration of irredundant choices (Lemma 5.1 and 6.4) leads to N^O(k) complexity

Research Question: Can algorithms with f(k)·poly(N) time be designed?

4. Generalization of Critical Generators

• E-generators: Corresponding concept in lattice theory
• E-bases in Lower-bounded Closure Systems: May be effective implicational bases

5. Practical Applications

• Database Theory: Representation and inference of functional dependencies
• Machine Learning: Concept lattices and formal concept analysis
• Knowledge Representation: Compression and inference of Horn clauses

In-Depth Evaluation

Strengths

1. Theoretical Depth

• Rigor: All results have complete mathematical proofs
• Comprehensiveness: Addresses both enumeration and generation directions
• Precision: Clearly delineates tractability boundaries and limitations

2. Technical Innovation

• Method Diversity: Combines hypergraph theory, resolution graph traversal, saturation techniques, and other methods
• Unified Framework: Top-down method provides unified perspective for different parameter cases
• Structural Insights: Deep analysis of critical generators and degree has independent value

3. Problem Importance

• Fundamentality: Closure systems are core concepts across multiple fields
• Difficulty: Problem generalizes long-standing unsolved hypergraph dualization problem
• Practicality: Has real applications in databases, logic, and lattice theory

4. Presentation Quality

• Self-containedness: Paper includes thorough background and preliminaries
• Clarity: Well-structured, progressing from simple to complex
• Rich Examples: Abundant figures and examples aid understanding

Weaknesses

1. Absence of Experiments

• No Empirical Evaluation: As a pure theory paper, lacks practical performance testing
• Unknown Constants: Asymptotic complexity may hide large constants
• Practical Efficiency: Unclear how algorithms perform on realistic problem sizes

2. Parameter Limitations

• XP Rather Than FPT: Exponential dependence on degree limits practicality
• Potentially Large Degree: Many practical problems may have non-small degree
• Parameter Verification: Unclear which practical problems satisfy bounded degree conditions

3. Generalization Scope

• Acyclicity Required: Results heavily depend on acyclicity
• Convexity: Even within convex geometries, some results don't hold
• Theorem 8.3: Bounded degree provides no help for general closure systems

4. Complexity Gaps

• Delay Problem: Cannot achieve polynomial delay
• FPT Open: Existence of FPT algorithms remains unknown
• Exact Complexity: Precise complexity class of problems remains unclear

Impact

1. Theoretical Contributions

• Gap Filling: Bridges between ordered convex geometries and general acyclic convex geometries
• Methodology: Top-down method may apply to other acyclic structures
• Complexity Understanding: Clarifies obstacles to polynomial delay

2. Practical Value

• Algorithm Tools: Provides implementable algorithms for bounded degree cases
• Parameter Guidance: Validates degree as complexity parameter
• Design Principles: Critical base minimality provides practical guidance

3. Reproducibility

• Algorithm Clarity: All algorithms have clear pseudo-code level descriptions
• Complete Proofs: All claims have detailed proofs
• Open Problems: Clearly identifies future research directions

4. Field Advancement

• ISAAC 2025 Acceptance: Recognition by top-tier algorithms conference
• Ongoing Research: Author team has series of works in this area
• Citation Value: Provides solid foundation for subsequent research

Applicable Scenarios

1. Theoretical Research

• Algorithmic research in closure systems and lattice theory
• Variants of hypergraph dualization problem
• Parameterized complexity theory

2. Database Applications

• Functional Dependencies: When dependency graphs are acyclic with small degree
• Data Mining: Compact representation of association rules
• Query Optimization: Reasoning about dependency relationships

3. Knowledge Representation

• Horn Knowledge Bases: Compression of acyclic Horn formulas
• Ontology Engineering: Representation of concept hierarchies
• Expert Systems: Rule base maintenance

4. Combinatorial Optimization

• Antimatroids: Combinatorial optimization on convex geometries
• Greedy Algorithms: Greedy strategies exploiting acyclic structure
• Polyhedral Theory: Enumeration of convex hulls and extreme points

5. Inapplicable Scenarios

• General closure systems (without acyclicity)
• Unbounded degree problems
• Applications requiring polynomial delay guarantees
• Large-scale real-time systems (XP complexity may be prohibitive)

Key References

1. HK95 Hammer & Kogan (1995): Pioneering work on acyclic Horn knowledge bases
2. DNV21 Defrain, Nourine & Vilmin (2021): Conversion in ordered convex geometries
3. FK96 Fredman & Khachiyan (1996): Quasi-polynomial algorithm for hypergraph dualization
4. KSS00 Kavvadias et al. (2000): Hardness of ACS·Enum
5. Wil94 Wild (1994): Implication-based closure space theory
6. EJ85 Edelman & Jamison (1985): Convex geometry theory
7. MR92 Mannila & Räihä (1992): Relational database design
8. BDVG18 Bertet et al. (2018): Survey on closure systems and implicational bases

Summary

This is a high-quality theoretical algorithms paper that achieves tractability results in acyclic convex geometries, an important class of closure systems, by restricting the degree parameter. The paper's main strengths lie in its theoretical depth, technical innovation, and presentation quality, while clearly delineating complexity boundaries and limitations. Main limitations include XP rather than FPT complexity, absence of experimental evaluation, and strong dependence on acyclicity. The paper establishes a solid foundation for subsequent research in this field, particularly providing valuable insights into parameterized algorithms and exploitation of structural properties. For researchers in theoretical computer science, especially those working on algorithmic enumeration and closure systems, this is an important reference work.