Skip to content

Only supply subgraph of the input graph to the ASP encoding? #4

@bbliem

Description

@bbliem

Currently, D-FLAT supplies the whole instance to the ASP encoding at each tree decomposition node. Maybe it makes sense to only give those facts as input that are relevant for the bags of the current node or its children. Theoretically, with the current practice we have (at least) linear runtime in each call since the input has linear size. For bounded width, we could bring this down to constant time by restricting the input. However, appropriate data structures would be required, because just running through the entire input (hyper)graph before each ASP call, in order to filter the input, would yield linear runtime yet again -- albeit not inside the ASP call, but still...

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions