Cutting Cycles of Conditional Preference Networks with Feedback Set Approach

Area of Science:

• Artificial Intelligence
• Computer Science

Background:

• Conditional preference networks (CP-nets) are increasingly used for qualitative representation in AI.
• Cycles in CP-nets can negatively impact their properties, such as consistency and satisfaction.
• Existing methods for handling cycles in CP-nets may face challenges with computational complexity.

Purpose of the Study:

• To investigate the application of feedback set problem theory (FVS and FAS) for cycle detection and removal in CP-nets.
• To develop efficient algorithms for cutting cycles in CP-nets, specifically addressing the complexity issue.
• To compare the performance and expressive capabilities of FVS-based and FAS-based approaches for CP-net cycle resolution.

Main Methods:

• Utilizing feedback vertex set (FVS) and feedback arc set (FAS) theories to identify and break cycles within CP-nets.
• Defining a specific class of parent vertices in ring CP-nets to facilitate targeted cycle reduction.
• Developing and implementing novel algorithms based on FVS and FAS tailored for CP-net cycle management.

Main Results:

• Experimental evaluation comparing the running time of the proposed FVS and FAS algorithms.
• Assessment of the expressive ability of CP-nets after cycle removal using the developed methods.
• Demonstration of the effectiveness of the proposed algorithms in managing cycles within CP-nets.

Conclusions:

• The proposed FVS and FAS-based algorithms offer efficient solutions for handling cycles in CP-nets.
• The methods contribute to improving the consistency and satisfaction properties of CP-nets.
• The study provides a comparative analysis of the performance and expressiveness of different cycle-cutting strategies.