Author name cluster

Dusan Knop

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

MFCS Conference 2024 Conference Paper

Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra

Václav Blazej
Dusan Knop
Jan Pokorný 0001
Simon Schierreich

In the Equitable Connected Partition (ECP for short) problem, we are given a graph G = (V, E) together with an integer p ∈ ℕ, and our goal is to find a partition of V into p parts such that each part induces a connected sub-graph of G and the size of each two parts differs by at most 1. On the one hand, the problem is known to be NP-hard in general and W[1]-hard with respect to the path-width, the feedback-vertex set, and the number of parts p combined. On the other hand, fixed-parameter algorithms are known for parameters the vertex-integrity and the max leaf number. In this work, we systematically study ECP with respect to various structural restrictions of the underlying graph and provide a clear dichotomy of its parameterised complexity. Specifically, we show that the problem is in FPT when parameterized by the modular-width and the distance to clique. Next, we prove W[1]-hardness with respect to the distance to cluster, the 4-path vertex cover number, the distance to disjoint paths, and the feedback-edge set, and NP-hardness for constant shrub-depth graphs. Our hardness results are complemented by matching algorithmic upper-bounds: we give an XP algorithm for parameterisation by the tree-width and the distance to cluster. We also give an improved FPT algorithm for parameterisation by the vertex integrity and the first explicit FPT algorithm for the 3-path vertex cover number. The main ingredient of these algorithms is a formulation of ECP as N-fold IP, which clearly indicates that such formulations may, in certain scenarios, significantly outperform existing algorithms based on the famous algorithm of Lenstra.

Details

ECAI Conference 2023 Conference Paper

High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

Robert Bredereck
Andrzej Kaczmarczyk 0001
Dusan Knop
Rolf Niedermeier

Using insights from parametric integer linear programming, we improve the work of Bredereck et al. [Proc. ACM EC 2019] on high-multiplicity fair allocation. Answering an open question from their work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter “number of agents” plus “number of item types. ” Our central improvement, compared to their result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary, which is required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary. Thus, we substantially expand the range of feasible utility and multiplicity values.

Details

TARK Conference 2023 Conference Paper

Maximizing Social Welfare in Score-Based Social Distance Games

Robert Ganian
Thekla Hamm
Dusan Knop
Sanjukta Roy 0001
Simon Schierreich
Ondrej Suchý 0001

Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function u that took into account distances in a given social network. In this paper, we consider a non-normalized score-based definition of social distance games where the utility function u_v depends on a generic scoring vector v, which may be customized to match the specifics of each individual application scenario. As our main technical contribution, we establish the tractability of computing a welfare-maximizing partitioning of the agents into coalitions on tree-like networks, for every score-based function u_v. We provide more efficient algorithms when dealing with specific choices of u_v or simpler networks, and also extend all of these results to computing coalitions that are Nash stable or individually rational. We view these results as a further strong indication of the usefulness of the proposed score-based utility function: even on very simple networks, the problem of computing a welfare-maximizing partitioning into coalitions remains open for the originally considered canonical function u.

Details DOI

MFCS Conference 2019 Conference Paper

Parameterized Complexity of Fair Vertex Evaluation Problems

Dusan Knop
Tomás Masarík
Tomás Toufar

A prototypical graph problem is centered around a graph-theoretic property for a set of vertices and a solution to it is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of a certain quality, where we use size as a quality measure. In this work, we are changing the measure to the fair measure (cf. Lin and Sahni [Li-Shin Lin and Sartaj Sahni, 1989]). The fair measure of a set of vertices S is (at most) k if the number of neighbors in the set S of any vertex (in the input graph) does not exceed k. One possible way to study graph problems is by defining the property in a certain logic. For a given objective, an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. More formally, we study the {MSO} Fair Vertex Evaluation, where the graph-theoretic property is described by an {MSO} formula. In the presented paper we show that there is an FPT algorithm for the {MSO} Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph and the size of the formula. One may define an extended variant of {MSO} Fair Vertex Evaluation for formulas with l free variables; here we measure a maximum number of neighbors in each of the l sets. However, such variant is {W[1]}-hard for parameter l even on graphs with twin cover one. Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i. e. , the rest forms an edgeless graph). On the negative side, Fair VC is {W[1]}-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.

Details

AAAI Conference 2019 Conference Paper

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Eduard Eiben
Robert Ganian
Dusan Knop
Sebastian Ordyniak

We study the parameterized complexity of Integer Quadratic Programming under two kinds of restrictions: explicit restrictions on the domain or coefficients, and structural restrictions on variable interactions. We argue that both kinds of restrictions are necessary to achieve tractability for Integer Quadratic Programming, and obtain four new algorithms for the problem that are tuned to possible explicit restrictions of instances that we may wish to solve. The presented algorithms are exact, deterministic, and complemented by appropriate lower bounds.

PDF Details