We introduce a general abstract framework for database repairs, where the repair notions are defined using formal logic. We distinguish between integrity constraints and so-called query constraints. The former are used to model consistency and desirable properties of the data (such as functional dependencies and independencies), while the latter relate two database instances according to their answers to the query constraints. The framework allows for a distinction between hard and soft queries, allowing the answers to a core set of queries to be preserved, as well as defining a distance between instances based on query answers. We illustrate how different repair notions from the literature can be modelled in our framework. The framework generalises both set-based and cardinality based repairs to semiring annotated databases. Finally, we initiate a complexity-theoretic analysis of consistent query answering and checking existence of a repair in our setting.

The proper thinness of a graph is an invariant that generalizes the concept of a proper interval graph. Every graph has a numerical value of proper thinness and the graphs with proper thinness 1 are exactly the proper interval graphs. A graph is proper k -thin if its vertices can be ordered in such a way that there is a partition of the vertices into k classes satisfying that for each triple of vertices r < s < t , such that there is an edge between r and t , it is true that if r and s belong to the same class, then there is an edge between s and t , and if s and t belong to the same class, then there is an edge between r and s . The proper thinness is the smallest value of k such that the graph is proper k -thin. In this work we focus on the calculation of proper thinness for trees. We characterize trees of proper thinness 2, both structurally and by their minimal forbidden induced subgraphs. The characterizations obtained lead to a polynomial-time recognition algorithm. We furthermore show why the structural results obtained for trees of proper thinness 2 cannot be straightforwardly generalized to trees of proper thinness 3.

Graph modification problems are computational tasks where the goal is to change an input graph G using operations from a fixed set, in order to make the resulting graph satisfy a target property, which usually entails membership to a desired graph class C. Some well-known examples of operations include vertex-deletion, edge-deletion, edge-addition and edge-contraction. In this paper we address an operation known as subgraph complement. Given a graph G and a subset S of its vertices, the subgraph complement G ⊕ S is the graph resulting from complementing the edge set of the subgraph induced by S in G. We say that a graph H is a subgraph complement of G if there is an S such that H is isomorphic to G⊕S. For a graph class C, the Subgraph complementation to C is the problem of deciding, for a given graph G, whether G has a subgraph complement in C. This problem has been studied and its complexity has been settled for many classes C such as H -free graphs, for various families H , and for classes of bounded degeneracy. In this work, we focus on classes of graphs of minimum/maximum degree upper/lower bounded by some value k. In particular, we answer an open question of Antony et al. [Information Processing Letters 188, 106530 (2025)], by showing that Subgraph complementation to C is NP-complete when C is the class of graphs of minimum degree at least k , if k is part of the input. We also show that Subgraph complementation to k -regular parameterized by k is fixed-parameter tractable.

We embark on a study of the consistent answers of queries over databases annotated with values from a naturally ordered positive semiring. In this setting, the consistent answers of a query are defined as the minimum of the semiring values that the query takes over all repairs of an inconsistent database. The main focus is on self-join free conjunctive queries and key constraints, which is the most extensively studied case of consistent query answering over standard databases. We introduce a variant of first-order logic with a limited form of negation, define suitable semiring semantics, and then establish the main result of the paper: the consistent query answers of a self-join free conjunctive query under key constraints are rewritable in this logic if and only if the attack graph of the query contains no cycles. This result generalizes an analogous result of Koutris and Wijsen for ordinary databases, but also yields new results for a multitude of semirings, including the bag semiring, the tropical semiring, and the fuzzy semiring. Further, for the bag semiring, we show that computing the consistent answers of any self-join free conjunctive query whose attack graph has a strong cycle is not only NP-hard but also it is NP-hard to even approximate the consistent answers with a constant relative approximation guarantee.

Attribution scores reflect how important the feature values in an input entity are for the output of a machine learning model. One of the most popular attribution scores is the SHAP score, which is an instantiation of the general Shapley value used in coalition game theory. The definition of this score relies on a probability distribution on the entity population. Since the exact distribution is generally unknown, it needs to be assigned subjectively or be estimated from data, which may lead to misleading feature scores. In this paper, we propose a principled framework for reasoning on SHAP scores under unknown entity population distributions. In our framework, we consider an uncertainty region that contains the potential distributions, and the SHAP score of a feature becomes a function defined over this region. We study the basic problems of finding maxima and minima of this function, which allows us to determine tight ranges for the SHAP scores of all features. In particular, we pinpoint the complexity of these problems, and other related ones, showing them to be intractable. Finally, we present experiments on a real-world dataset, showing that our framework may contribute to a more robust feature scoring.

For a fixed property (graph class) Π, given a graph G and an integer k, the Π-deletion problem consists in deciding if we can turn G into a graph with the property Π by deleting at most k edges. The Π-deletion problem is known to be NP-hard for most of the well-studied graph classes, such as chordal, interval, bipartite, planar, comparability and permutation graphs, among others; even deletion to cacti is known to be NP-hard for general graphs. However, there is a notable exception: the deletion problem to trees is polynomial. Motivated by this fact, we study the deletion problem for some classes similar to trees, addressing in this way a knowledge gap in the literature. We prove that deletion to cacti is hard even when the input is a bipartite graph. On the positive side, we show that the problem becomes tractable when the input is chordal, and for the special case of quasi-threshold graphs we give a simpler and faster algorithm. In addition, we present sufficient structural conditions on the graph class Π that imply the NP-hardness of the Π-deletion problem, and show that deletion from general graphs to some well-known subclasses of forests is NP-hard.

Semiring semantics for first-order logic provides a way to trace how facts represented by a model are used to deduce satisfaction of a formula. Team semantics is a framework for studying logics of dependence and independence in diverse contexts such as databases, quantum mechanics, and statistics by extending first-order logic with atoms that describe dependencies between variables. Combining these two, we propose a unifying approach for analysing the concepts of dependence and independence via a novel semiring team semantics, which subsumes all the previously considered variants for first-order team semantics. In particular, we study the preservation of satisfaction of dependencies and formulae between different semirings. In addition we create links to reasoning tasks such as provenance, counting, and repairs.

In the deeply interconnected world we live in, pieces of information link domains all around us. As graph databases embrace effectively relationships among data and allow processing and querying these connections efficiently, they are rapidly becoming a popular platform for storage that supports a wide range of domains and applications. As in the relational case, it is expected that data preserves a set of integrity constraints that define the semantic structure of the world it represents. When a database does not satisfy its integrity constraints, a possible approach is to search for a ‘similar’ database that does satisfy the constraints, also known as a repair. In this work, we study the problem of computing subset and superset repairs for graph databases with data values using a notion of consistency based on having a set of Reg-GXPath expressions as integrity constraints. We show that for positive fragments of Reg-GXPath these problems admit a polynomial-time algorithm, while the full expressive power of the language renders them intractable.