A logical approach to locality in pictures languages
This paper deals with descriptive complexity of picture languages of any dimension by fragments of existential second-order logic:1) We generalize to any dimension the characterization by Giammarresi et al. (1996) of the class of recognizable picture ...
Equations over sets of integers with addition only
Systems of equations of the form X = Y + Z and X = C are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are ...
Parameterized complexity dichotomy for Steiner Multicut
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...
Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems
We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph G = ( V , E ) with edge-weights w : E ź R ź 0 and vertex-weights ź : V ź R + ...
Hellinger volume and number-on-the-forehead communication complexity
Information-theoretic methods are a powerful tool in communication complexity, providing, in particular, elegant and tight lower bounds on disjointness in the number-in-the-hand (NIH) model. In this paper, we study the applicability of information ...
Kernelizations for the hybridization number problem on multiple nonbinary trees
Given a finite set X, a collection T of rooted phylogenetic trees on X and an integer k, the Hybridization Number problem asks if there exists a phylogenetic network on X that displays all trees from T and has reticulation number at most k. We show two ...
An efficient time-free solution to SAT problem by P systems with proteins on membranes
The notion of time-free solution to decision problem by P systems with proteins on membranes, in the sense that the correctness of the solution is irrelevant to the times associated with the involved rules, is defined.A time-free uniform solution to the ...
Win-win kernelization for degree sequence completion problems
We study provably effective and efficient data reduction for a class of NP-hard graph modification problems based on vertex degree properties. We show fixed-parameter tractability for NP-hard graph completion (that is, edge addition) cases while we show ...
Fast processing of graph queries on a large database of small and medium-sized data graphs
We propose a new way of indexing a large database of small and medium-sized graphs and processing exact subgraph matching (or subgraph isomorphism) and approximate (full) graph matching queries. Rather than decomposing a graph into smaller units (e.g., ...
Approximately counting locally-optimal structures
In general, constructing a locally-optimal structure is a little harder than constructing an arbitrary structure, but significantly easier than constructing a globally-optimal structure. A similar situation arises in listing. In counting, most problems ...