Bayesian network structure learning is the notoriously difficult problem of discovering a that optimally represents given set training data. In this paper we study computational worst-case complexity exact under graph theoretic restrictions on (directed) super-structure. The super-structure an undirected contains as subgraphs skeletons solution networks. We introduce directed natural generalization its counterpart. Our results apply to several variants score-based where score decomposes into...

Abstract We study the parameterized complexity of Bounded-Degree Vertex Deletion problem (BDD), where aim is to find a maximum induced subgraph whose degree below given bound. Our focus lies on parameters that measure structural properties input instance. first show W[1]-hard by wide range fairly restrictive such as feedback vertex set number, pathwidth, treedepth, and even size minimum deletion into graphs pathwidth treedepth at most three. thereby resolve an open question stated in...

Checking whether a system of linear equations is consistent basic computational problem with ubiquitous applications. When dealing inconsistent systems, one may seek an assignment that minimises the number unsatisfied equations. This NP -hard and UGC-hard to approximate within any constant even for two-variable over two-element field. We study this from point view parameterized complexity, parameter being consider defined family commutative domains (i.e. rings without zero divisors)...

Over the past two decades main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in FPT-algorithm by Grohe, Kreutzer and Siebertz for FO nowhere dense classes graphs [STOC'14], with structures starting to attract attention only recently. Bova, Ganian Szeider [CSL-LICS'14] initiated study complexity on partially ordered sets (posets). showed that existential logic is fixed-parameter tractable (FPT) posets bounded width, where...

Integer Linear Programming (ILP) and its mixed variant (MILP) are archetypical examples of NP-complete optimization problems which have a wide range applications in various areas artificial intelligence. However, we still lack thorough understanding structural restrictions make these tractable. Here focus on structure captured via so-called decompositional parameters, been highly successful fields such as boolean satisfiability constraint satisfaction but not yet reached their full potential...

The early classifications of the computational complexity planning under various restrictions in STRIPS (Bylander) and SAS+ (Bäckström Nebel) have influenced following research many ways. We go back reanalyse their subclasses, but this time using more modern tool parameterized analysis. This provides new results that together with old give a detailed picture landscape. demonstrate separation not possible standard theory, which contributes to explaining why certain cases seemed simpler...

Integer Linear Programming (ILP) has a broad range of applications in various areas artificial intelligence. Yet spite recent advances, we still lack thorough understanding which structural restrictions make ILP tractable. Here study instances consisting small number ``global'' variables and/or constraints such that the remaining part instance consists and otherwise independent components; this is captured terms measure call fracture backdoors generalizes, for instance, well-studied class...

In this paper we extend the classical notion of strong and weak backdoor sets for SAT CSP by allowing that different instantiations variables result in instances belong to base classes; union classes forms a heterogeneous class. Backdoor can be much smaller than homogeneous ones, hence they are more desirable but possibly harder find. We draw detailed complexity landscape problem detecting into CSP.

We consider monotonicity problems for graph searching games. Variants of these games - defined by the type moves allowed players have been found to be closely connected decompositions and associated width measures such as path- or tree-width. Of particular interest is question whether are monotone, i.e. cops can catch a robber without ever allowing reach positions that cleared before. The problem has intensely studied in literature, but two types was left unresolved. These on digraphs where...

We study the Connected Fair Division problem (CFD), which generalizes fundamental of fairly allocating resources to agents by requiring that items allocated each agent form a connected subgraph in provided item graph G. expand on previous results providing comprehensive complexity-theoretic understanding CFD based several new algorithms and lower bounds while taking into account well-established notions fairness: proportionality, envy-freeness, EF1 EFX. In particular, we show achieve...

Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating backdoor variables one reduces given instance to several easy instances that belong a tractable class.The overall time needed solve is exponential in size of set, hence it challenging problem find small set if exists; over last years this has been subject intensive research. In paper we extend classical notion strong by allowing different instantiations result base classes; union...

We prove that the model checking problem for existential fragment of first-order (FO) logic on partially ordered sets is fixed-parameter tractable (FPT) with respect to formula and width a poset (the maximum size an antichain). While there long line research into FO graphs, study this posets has been initiated just recently by Bova, Ganian Szeider (CSL-LICS 2014), who proved FPT algorithm fixed width. improve upon their result in two ways: (1) runtime our O(f(|{\phi}|,w).n^2) n-element w,...