
On the computational tractability of a geographic clustering problem arising in redistricting
Redistricting is the problem of dividing a state into a number k of regi...
read it

Four short stories on surprising algorithmic uses of treewidth
This article briefly describes four algorithmic problems where the notio...
read it

Finding Small Satisfying Assignments Faster Than Brute Force: A Finegrained Perspective into Boolean Constraint Satisfaction
To study the question under which circumstances small solutions can be f...
read it

Incompressibility of Hfree edge modification problems: Towards a dichotomy
Given a graph G and an integer k, the Hfree Edge Editing problem is to ...
read it

Hitting Long Directed Cycles is FixedParameter Tractable
In the Directed Long Cycle Hitting Set problem we are given a directed g...
read it

Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
The Directed Feedback Vertex Set (DFVS) problem takes as input a directe...
read it

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
(see paper for full abstract) Given a vertexweighted directed graph G...
read it

How does object fatness impact the complexity of packing in d dimensions?
Packing is a classical problem where one is given a set of subsets of Eu...
read it

Parameterized Intractability of Even Set and Shortest Vector Problem
The kEven Set problem is a parameterized variant of the Minimum Distanc...
read it

Finding and counting permutations via CSPs
Permutation patterns and pattern avoidance have been intensively studied...
read it

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
We prove essentially tight lower bounds, conditionally to the Exponentia...
read it

Slightly Superexponential Parameterized Problems
A central problem in parameterized algorithms is to obtain algorithms ...
read it

Covering a tree with rooted subtrees
We consider the multiple traveling salesman problem on a weighted tree. ...
read it

Kernelization of Packing Problems
Kernelization algorithms are polynomialtime reductions from a problem t...
read it

Multibudgeted directed cuts
We study multibudgeted variants of the classic minimum cut problem and ...
read it

Subexponentialtime Algorithms for Maximum Independent Set in P_tfree and Broomfree Graphs
In algorithmic graph theory, a classic open question is to determine the...
read it

A Framework for ETHTight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lowerbound framework that facilitates the co...
read it

Framework for ETHtight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lowerbound framework that facilitates the co...
read it

The Parameterized Hardness of the kCenter Problem in Transportation Networks
In this paper we study the hardness of the kCenter problem on inputs th...
read it

Constraint Solving via Fractional Edge Covers
Many important combinatorial problems can be modeled as constraint satis...
read it

On the hardness of losing weight
We study the complexity of local search for the Boolean constraint satis...
read it

Completely inapproximable monotone and antimonotone parameterized problems
We prove that weighted circuit satisfiability for monotone or antimonoto...
read it

Clustering with Local Restrictions
We study a family of graph clustering problems where each cluster has to...
read it

Size bounds and query plans for relational joins
Relational joins are at the core of relational algebra, which in turn is...
read it

Soft Constraints of Difference and Equality
In many combinatorial problems one may need to model the diversity or si...
read it
Dániel Marx
is this you? claim profile