1,721,046 research outputs found
Solving the directed feedback vertex set problem in theory and practice
No full textA directed feedback vertex set (dfvs) is a subset of vertices of a graph, that, when removed, makes the graph acyclic. The Directed Feedback Vertex Set problem (DFVS) is to find such a subset. It is NP-complete, hence, we do not know how to solve it efficiently.
In this work we explore practical approaches to find a minimum dfvs on real word instances. This was also the goal of the Parameterized Algorithms and Computational Experiments (PACE) challenge 2022. Our submission obtained the second place in the exact track and was the best student team.
Our first step of finding a minimum dfvs is to apply a set of data reduction rules. These are applied in polynomial time and reduce the size of the instance. We give a detailed overview of existing and new data reduction rules.
A kernel can be seen as a collection of reduction rules with theoretical guarantees. It is a polynomial time algorithm that takes a problem instance and returns a smaller equivalent instance with a bound on its size. We show that a very simple reduction rule removes the input restriction for the kernel of Bergougnoux et al. (2021). After its application, we obtain an instance with at most O(f^4) vertices, with f being the size of a minimum feedback vertex set on its cycle preserving undirected graph.
We implemented several techniques to solve a reduced instance. We achieved best results when performing an iterative reduction to Hitting Set, which we then either reduce to Integer Linear Program, Max SAT or Vertex Cover. Solvers for these three problems already exist, which can solve large instances in practice.
Depending on the instance, we select the best suitable solving approach. For the first time, we explain the solver that we submitted in detail and present an improved version. We compare our results with approaches of other challenge participants, in particular DAGer, the winner of the exact track. Our improved solver is now able to solve the same number of instances within the time limit of the PACE challenge
Descriptive complexity of learning
No full textSupervised learning is a field in machine learning that strives to classify data based on labelled training examples. In the Boolean setting, each input is to be assigned to one of two classes, and there are several fruitful machine-learning methods to obtain a classifier. However, different algorithms usually come with different types of classifiers, e.g. decision trees, support-vector machines, or neural networks, and this is cumbersome for a unified study of the intrinsic complexity of learning tasks. This thesis aims at strengthening the theoretical foundations of machine learning in a consistent framework. In the setting due to Grohe and Turán (2004), the inputs for the classification are tuples from a relational structure and the search space for the classifiers consists of logical formulas. The framework separates the definition of the class of potential classifiers (the hypothesis class) from the precise machine-learning algorithm that returns a classifier. This facilitates an information-theoretic analysis of hypothesis classes as well as a study of the computational complexity of learning hypotheses from a specific hypothesis class. As a first step, Grohe and Ritzert (2017) proved that hypotheses definable in first-order logic (FO) can be learned in sublinear time over structures of small degree. We generalise this result to two extensions of FO that provide data-aggregation methods similar to those in commonly used relational database systems. First, we study the extension FOCN of FO with counting quantifiers. Then, we analyse logics that operate on weighted structures, which can model relational databases with numerical values. For that, we introduce the new logic FOWA, which extends FO by weight aggregation. We provide locality results and prove that hypotheses definable in a fragment of the logic can be learned in sublinear time over structures of small degree. To better understand the complexity of machine-learning tasks on richer classes of structures, we then study the parameterised complexity of these problems. On arbitrary relational structures and under common complexity-theoretic assumptions, learning hypotheses definable in pure first-order logic turns out to be intractable. In contrast to this, we show that the problem is fixed-parameter tractable if the structures come from a nowhere dense class. This subsumes numerous classes of sparse graphs. In particular, we obtain fixed-parameter tractability for planar graphs, graphs of bounded treewidth, and classes of graphs excluding a minor
Counting and sliding verifying and restoring healthy systems
No full textReactive systems play a significant role in the daily life of every person. Such systems
include personal computers, automatic teller machines, devices we use every day in our
households, and also systems that play a less active but still important role, for example
monitoring devices scanning for environmental threats in a country. In particular for
safety-critical reactive systems it is of enormous importance that correctness properties of
such systems have been verified. A very prominent technique to tackle such verification
tasks is called model checking. From a theoretical point of view, model checking commonly
boils down to solving classical decision problems for finite automata; usually automata
operating on infinite words. We study Parikh automata on finite and infinite words with applications to model checking. These automata extend classical finite automata with a Counting mechanism.
Still, due the dynamics of the realworld it might be the case that a change in the environmentleads to a faulty or even dangerous state of such a system. Referring to the above example of devices scanning for environmental threats, assume that due to a mistake at a local construction site the connection to the other devices has been cut, leaving a part of the country unmonitored. Hence, a new solution has to be computed. However, the new solution can differ arbitrarily from the current state. Given that it is costly to move such devices around, it is desirable to compute a new solution that is close to the current state. To capture and formalize such scenarios, we introduce the new framework of solution discovery via reconfiguration for constructing a feasible solution for a given problem by executing a sequence of small modifications starting from a given state
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Two new perspectives on algorithmic meta-theorems : evaluating approximate first-order counting queries on bounded expansion and first-order queries on random graphs
No full textWe present two algorithmic meta-theorems. Our first meta-theorem is an approximation scheme of the parameterized model-checking problem for the first-order counting logic FO({>0}). This logic extends first-order logic with the ability to count the number of satisfying assignments of a variable and compare it to fixed but arbitrarily large numbers. The model-checking scheme runs in linear fpt time (parameterized by formula length) on structures with bounded expansion and either gives the correct answer or says ``I do not know.'' The latter answer may only be given if small perturbations in the number-symbols of the formula could make it both satisfied and unsatisfied. As a consequence, every property expressible in FO({>0}) can be approximated in linear time on bounded expansion graph classes. A restricted set of counting properties can also be solved exactly in linear time, leading for example to an fpt algorithm for partial dominating set on bounded expansion graph classes. These results are complemented by showing that exactly solving the model-checking problem for FO({>0}) is already hard on trees of bounded depth and just slightly increasing the expressiveness of FO({>0}) makes even approximation hard on trees.Our second meta-theorem is a first-order model-checking algorithm for random graphs and complex networks. Roughly speaking, we say a random graph model is alpha-power-law-bounded if it is unclustered and the fraction of vertices with degree k is O(k^-alpha). We solve the parameterized first-order model-checking problem in almost linear fpt time on random graph models satisfying this property with alpha >= 3. This means in particular that one can solve every first-order property in almost linear expected time on these random graph models. This includes many popular models of complex networks such as preferential attachment graphs, Chung–Lu graphs, configuration graphs, and sparse Erdős–Rényi graphs. We present hardness results that show intractability for alpha < 3, assuming we allow an adversary to color the vertices of the input graph. We base our algorithms on a new structural decomposition of alpha-power-law-bounded random graphs and on new concentration bounds for the degree evolution in preferential attachment graphs
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
