-
Chapter and Conference Paper
Correction to: Parameterized Algorithms for Covering by Arithmetic Progressions
-
Chapter and Conference Paper
Exact and Parameterized Algorithms for Choosability
In the Choosability problem (or list chromatic number problem), for a given graph G, we need to find the smallest k such that G admits a list coloring for any list assignment where all lists contain at least k co...
-
Chapter and Conference Paper
Parameterized Algorithms for Covering by Arithmetic Progressions
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic prog...
-
Chapter and Conference Paper
Tight Double Exponential Lower Bounds
The majority of established algorithms have polynomial, exponential, or factorial runtime complexities. Examples of problems that admit tight double or even triple exponential bounds on computational complexit...
-
Chapter and Conference Paper
Parameterized Complexity of Paired Domination
The Paired Domination problem is one of the well-studied variants of the classical Dominating Set problem. In a graph G on n vertices, a dominating set D (set of vertices such that
-
Article
Solving Target Set Selection with Bounded Thresholds Faster than \(2^n\)
In this paper we consider the Target Set Selection problem. The problem naturally arises in many fields like economy, sociology, medicine. In the Target Set Selection problem one is given a graph G with a functio...
-
Chapter and Conference Paper
Enumeration of Minimal Tropical Connected Sets
A subset of vertices in a vertex-colored graph is called tropical if vertices of each color present in the subset. This paper is dedicated to the enumeration of all minimal tropical connected sets in various c...
-
Chapter and Conference Paper
Fair Division with Minimal Withheld Information in Social Networks
We present a study of a few graph based problems motivated by fair allocation of resources in a social network. The central role in the paper is played by the following problem: What is the largest number of i...
-
Chapter and Conference Paper
Two Generalizations of Proper Coloring: Hardness and Approximability
We study two natural generalizations of q -Coloring. These problems can be seen as optimization problems and are mostly applied to graphs that are not properly colorable with q colors. One of them is known as Max...
-
Chapter and Conference Paper
Maximizing Happiness in Graphs of Bounded Clique-Width
Clique-width is one of the most important parameters that describes structural complexity of a graph. Probably, only treewidth is more studied graph width parameter. In this paper we study how clique-width inf...
-
Chapter and Conference Paper
Lower Bounds for the Happy Coloring Problems
In this paper, we study the Maximum Happy Vertices and the Maximum ...
-
Chapter and Conference Paper
On Happy Colorings, Cuts, and Structural Parameterizations
We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters
-
Chapter and Conference Paper
Upper and Lower Bounds for Different Parameterizations of (n,3)-MAXSAT
In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in input formula each variable appears at most three...
-
Article
Parameterized Complexity of Superstring Problems
In the Shortest Superstring problem we are given a set of strings \(S=\{s_1, \ldots , s_n\}\) ...
-
Article
Open AccessLargest Chordal and Interval Subgraphs Faster than \(2^n\)
We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time ...
-
Chapter and Conference Paper
Parameterized Complexity of Superstring Problems
In the Shortest Superstring problem we are given a set of strings \(S=\{s_1, \ldots , s_n\}\) ...
-
Chapter and Conference Paper
A Subexponential Parameterized Algorithm for Proper Interval Completion
In the Proper Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection mo...
-
Chapter and Conference Paper
Largest Chordal and Interval Subgraphs Faster Than 2 n
We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $\mathcal{O}(2^{\l...
-
Chapter and Conference Paper
A New Algorithm for Parameterized MAX-SAT
We show how to check whether at least k clauses of an input formula in CNF can be satisfied in time O *(1.358 k ). This improves the bound O *(1.370 ...
