Dániel Marx

SODA Conference 2025 Conference Paper

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs

• Simon Döring
• Dániel Marx
• Philip Wellnitz

STOC Conference 2024 Conference Paper

Counting Small Induced Subgraphs with Edge-Monotone Properties

• Simon Döring
• Dániel Marx
• Philip Wellnitz

SODA Conference 2024 Conference Paper

Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations

• Baris Can Esmer
• Ariel Kulik
• Dániel Marx
• Daniel Neuen
• Roohani Sharma

SODA Conference 2023 Conference Paper

Computing Square Colorings on Bounded-Treewidth and Planar Graphs

• Akanksha Agrawal 0001
• Dániel Marx
• Daniel Neuen
• Jasper Slusallek

A square coloring of a graph G is a coloring of the square G 2 of G, that is, a coloring of the vertices of G such that any two vertices that are at distance at most 2 in G receive different colors. We investigate the complexity of finding a square coloring with a given number of q colors. We show that the problem is polynomial-time solvable on graphs of bounded treewidth by presenting an algorithm with running time for graphs of treewidth at most tw. The somewhat unusual exponent 2 tw in the running time is essentially optimal: we show that for any ε > 0, there is no algorithm with running time f (tw)n (2-ε) tw unless the Exponential-Time Hypothesis (ETH) fails. We also show that the square coloring problem is NP-hard on planar graphs for any fixed number q ≥ 4 of colors. Our main algorithmic result is showing that the problem (when the number of colors q is part of the input) can be solved in subexponential time on planar graphs. The result follows from the combination of two algorithms. If the number q of colors is small (≤ n 1/3 ), then we can exploit a treewidth bound on the square of the graph to solve the problem in time. If the number of colors is large (≥ n 1/3 ), then an algorithm based on protrusion decompositions and building on our result for the bounded- treewidth case solves the problem in time. * The full version of the paper can be accessed at https: //arxiv. org/abs/2211. 04458. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

FOCS Conference 2023 Conference Paper

Parameterized Approximation Schemes for Clustering with General Norm Objectives

• Fateme Abbasi
• Sandip Banerjee
• Jaroslaw Byrka
• Parinya Chalermsook
• Ameet Gadekar
• Kamyar Khodamoradi
• Dániel Marx
• Roohani Sharma

This paper considers the well-studied algorithmic regime of designing a $(1+\epsilon)$-approximation algorithm for a k-clustering problem that runs in time $f(k, \epsilon)poly(n)$ (sometimes called an efficient parameterized approximation scheme or EPAS for short 1 ). Notable results of this kind include EPASes in the high-dimensional Euclidean setting for k-center [Badŏiu, Har-Peled, Indyk; STOC’02] as well as k-median, and k-means [Kumar, Sabharwal, Sen; J. ACM 2010]. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. More specifically, our algorithm gives EPASes in the following settings: •Clustering objectives: k-means, k-center, k-median, priority k-center, $\ell$-centrum, ordered k-median, socially fair k-median (aka robust k-median), or any other objective that can be formulated as minimizing a monotone (not necessarily symmetric!) norm of the distances of the points from the solution (generalizing the symmetric formulation introduced by Chakrabarty and Swamy [STOC’19]). •Metric spaces: Continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics. Prior to our results, EPASes were only known for vanilla clustering objectives (k-means, k-median, and k-center) and each such algorithm is tailored to work for the specific input metric and clustering objective (e. g. , EPASes for k means and k-center in $\mathbb{R}^{d}$ are conceptually very different). In contrast, our algorithmic framework is applicable to a wide range of well-studied objective functions in a uniform way, and is (almost) entirely oblivious to any specific metric structures and yet is able to effectively exploit those unknown structures. In particular, our algorithm is not based on the (metric- and objective-specific) technique of coresets. Key to our analysis is a new concept that we call bounded $\epsilon$-scatter dimension—an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension(often used as a source of algorithmic tractability for geometric problems). Our main technical result shows that two conditions are essentially sufficient for our algorithm to yield an EPAS on the input metric M for any clustering objective: (i)The objective is described by a monotone norm, and(ii)the $\epsilon$-scatter dimension of M is upper bounded by a function of $\epsilon$. 1 Quick remarks: (i) An EPAS is not comparable to polynomial time approximation schemes (PTAS), (ii) before the term EPAS was invented some researchers call this type of approximation schemes a PTAS or simply an approximation scheme (in clustering, it is often assumed that k is small) [1], [2], and (iii) both EPAS and PTAS are implied by the existence of efficient polynomial time approximation schemes (EPTAS).

TCS Journal 2023 Journal Article

Parameterized complexity of multicut in weighted trees

• Esther Galby
• Dániel Marx
• Philipp Schepper
• Roohani Sharma
• Prafullkumar Tale

In the Multicut problem, given an undirected graph G, a set of pairs of vertices P, and a budget k, the goal is to determine if there is a set S of at most k edges such that for each ( s, t ) ∈ P, the graph G − S has no path from s to t. In this article we first study the parameterized complexity of a variant of this problem, where the input graph is edge-weighted with arbitrary weights and the goal is to find a solution of minimum weight. Since weights are arbitrarily large, the weight of the solution is not a good choice for a parameter. The weighted problem is non-trivial even on trees and we study this problem on trees parameterized by structural parameters like the number of leaves and the request degree of every vertex. The studied parameters naturally interpolate the known polynomial time and NP -hardness results for this problem. We also give an FPT algorithm for another variant called Weighted Multicut, where given an edge-weighted tree, the goal is to find a solution of size at most k edges that minimizes the weight.

SODA Conference 2023 Conference Paper

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

• Jacob Focke
• Dániel Marx
• Fionn Mc Inerney
• Daniel Neuen
• Govind S. Sankar
• Philipp Schepper
• Philip Wellnitz

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that | N ( u ) ∩ S | ∈ σ for every u ∈ S, and | N ( v ) ∩ S | ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as INDEPENDENT SET, DOMINATING SET, INDEPENDENT DOMINATING SET, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value c σ, ρ such that there is an algorithm that counts (σ, ρ)-sets in time c tw σ, ρ · n O(1) (if a tree decomposition of width tw is given in the input). Let s top denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite; r top is defined analogously for ρ. Surprisingly, c σ, ρ is often significantly smaller than the natural bound s top + r top + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining c σ, ρ, we say that (σ, ρ) is m -structured if there is a pair (α, β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • c σ, ρ = s top + r top +2 if (σ, ρ) is not m-structured for any m ≥ 2 • c σ, ρ = max{ s top, r top } + 2 if (σ, ρ) is 2-structured, but not m-structured for any m ≥ 3, and s top = r top is even, and • c σ, ρ = max{ s top, r top } + 1, otherwise we provide algorithms counting (σ, ρ)-sets in time c tw σ, ρ · n O(1). For example, for the EXACT INDEPENDENT DOMINATING SET problem (also known as PERFECT CODE) corresponding to σ = {0} and ρ = {1}, this improves the 3 tw · n O(1) algorithm of van Rooij to 2 tw · n O(1). Despite the unusually delicate definition of c σ, ρ, we show that our algorithms are most likely optimal, i. e. , for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a ( c σ, ρ — ε) tw · n O(1) - algorithm counting the number of (σ, ρ)-sets would violate the COUNTING STRONG EXPONENTIAL-TIME HYPOTHESIS (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets. * The full version of this work can be accessed at https: //arxiv. org/abs/2211. 04278. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

SODA Conference 2022 Conference Paper

A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs

• Dániel Marx
• Pranabendu Misra
• Daniel Neuen
• Prafullkumar Tale

Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this paper is to introduce a framework for obtaining time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node U nique L abel C over problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, O dd C ycle T ransversal, S ubset F eedback V ertex S et, G roup F eedback V ertex S et, S ubset G roup F eedback V ertex S et, V ertex M ultiway C ut, and C omponent O rder C onnectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain time (randomized) algorithms for V ertex M ultiway C ut, G roup F eedback V ertex S et, and S ubset F eedback V ertex S et. Our algorithms are designed with possible generalization to H -minor free graphs in mind. To obtain the same time algorithms on H -minor free graphs, the only missing piece is the vertex version of a contraction decomposition theorem that we currently have only for planar graphs.

SODA Conference 2022 Conference Paper

Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds

• Jacob Focke
• Dániel Marx
• Pawel Rzazewski

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G, H, and lists L ( v ) ⊆ V ( H ) for every v ∊ V ( G ), a list homomorphism is a function f: V(G ) → V(H ) that preserves the edges (i. e. , uv ∊ E(G ) implies f(u)f(v ) ∊ E(H )) and respects the lists (i. e. , f(v ) ∊ L(v )). Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time. Our main result is determining, for every fixed graph H, how much the base |V ( H ) | in the running time can be improved. For a connected graph H we define irr( H ) in the following way: if H has a loop or is nonbipartite, then irr( H ) is the maximum size of a set S ⊆ V ( H ) where any two vertices have different neighborhoods; if H is bipartite, then irr( H ) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr( H ) as the maximum of irr( C ) over every connected component C of H. It follows from earlier results that if irr( H ) = 1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H, the number of list homomorphisms from ( G, L ) to H can be counted in time if a tree decomposition of G having width at most t is given in the input, and given that irr( H ) ≥ 2, cannot be counted in time for any ∊ > 0, even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails. Thereby we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops.

STOC Conference 2018 Conference Paper

A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs

• Mark de Berg
• Hans L. Bodlaender
• Sándor Kisfaludi-Bak
• Dániel Marx
• Tom C. van der Zanden

We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2 O ( n 1−1/ d ) for any fixed dimension d ≥ 2 for many well known graph problems, including Independent Set, r -Dominating Set for constant r , and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms work on the graph itself, i.e., do not require any geometric information. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques.

SODA Conference 2018 Conference Paper

Covering a tree with rooted subtrees - parameterized and approximation algorithms

• Lin Chen 0009
• Dániel Marx

We consider the multiple traveling salesman problem on a weighted tree. In this problem there are m salesmen located at the root initially. Each of them will visit a subset of vertices and return to the root. The goal is to assign a tour to every salesman such that every vertex is visited and the longest tour among all salesmen is minimized. The problem is equivalent to the subtree cover problem, in which we cover a tree with rooted subtrees such that the weight of the maximum weighted subtree is minimized. The classical machine scheduling problem can be viewed as a special case of our problem when the given tree is a star. We provide approximation and parameterized algorithms for this problem. We first present a PTAS (Polynomial Time Approximation Scheme). We then observe that, the problem remains NP-hard even if tree height and edge weight are constant, and present an FPT algorithm for this problem parameterized by the largest tour length. To achieve the FPT algorithm, we first formulate the problem as an integer linear program having a certain “tree-fold” structure. Then we show that an ILP with such a structure is FPT, which is a generalization of an earlier FPT result for n-fold integer programming by Hemmecke, Onn and Romanchuk [5]. This extension of n-fold ILP may be of independent interest.

FOCS Conference 2018 Conference Paper

On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs

• Dániel Marx
• Marcin Pilipczuk
• Michal Pilipczuk

There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(sqrt(k)) instead of O(k) (modulo standard complexity assumptions). We consider two classic optimization problems parameterized by the number of terminals. The Steiner Tree problem asks for a minimum-weight tree connecting a given set of terminals T in an edge-weighted graph. In the Subset Traveling Salesman problem we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of these problems in planar graphs, where the number k = |T| of terminals is regarded as the parameter. Our results are the following: • Subset TSP can be solved in time 2^O(sqrt(k) log k). n^O(1) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. • Assuming the Exponential-Time Hypothesis, Steiner Tree on undirected planar graphs cannot be solved in time 2^o(k). n^O(1), even in the unit-weight setting. This lower bound makes Steiner Tree the first "genuinely planar" problem (i. e. , where the input is only planar graph with a set of distinguished terminals) for which we can show that the square root phenomenon does not appear. • Steiner Tree can be solved in time n^O(sqrt(k)) * W on undirected planar graphs with maximum edge weight W. Note that this result is incomparable to the fact that the problem is known to be solvable in time 2^k. n^O(1) even in general graphs. A direct corollary of the combination of our results for Steiner Tree is that this problem does not admit a parameter-preserving polynomial kernel on planar graphs unless ETH fails.

I&C Journal 2017 Journal Article

Hitting forbidden subgraphs in graphs of bounded treewidth

• Marek Cygan
• Dániel Marx
• Marcin Pilipczuk
• Michał Pilipczuk

We study the complexity of a generic hitting problem H-Subgraph Hitting, where given a fixed pattern graph H and an input graph G, the task is to find a set X ⊆ V ( G ) of minimum size that hits all subgraphs of G isomorphic to H. In the colorful variant of the problem, each vertex of G is precolored with some color from V ( H ) and we require to hit only H-subgraphs with matching colors. Standard techniques shows that for every fixed H, the problem is fixed-parameter tractable parameterized by the treewidth of G; however, it is not clear how exactly the running time should depend on treewidth. For the colorful variant, we demonstrate matching upper and lower bounds showing that the dependence of the running time on treewidth of G is tightly governed by μ ( H ), the maximum size of a minimal vertex separator in H. That is, we show for every fixed H that, on a graph of treewidth t, the colorful problem can be solved in time 2 O ( t μ ( H ) ) ⋅ | V ( G ) |, but cannot be solved in time 2 o ( t μ ( H ) ) ⋅ | V ( G ) | O ( 1 ), assuming the Exponential Time Hypothesis (ETH). Furthermore, we give some preliminary results showing that, in the absence of colors, the parameterized complexity landscape of H-Subgraph Hitting is much richer.

STOC Conference 2017 Conference Paper

Homomorphisms are a good basis for counting small subgraphs

• Radu Curticapean
• Holger Dell
• Dániel Marx

We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. We use the framework of graph motif parameters to obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G. More precisely, for graphs H on k edges, we show how to count subgraph copies of H in time k O ( k ) · n 0.174 k + o ( k ) by a surprisingly simple algorithm. This improves upon previously known running times, such as O ( n 0.91 k + c ) time for k -edge matchings or O ( n 0.46 k + c ) time for k -cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating f ε C on input graphs G , parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C , we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G , where H is from a fixed class of graphs, we want to count color-preserving H -copies in G . We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions.

STOC Conference 2016 Conference Paper

A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting

• MohammadHossein Bateni
• Erik D. Demaine
• MohammadTaghi Hajiaghayi
• Dániel Marx

We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O (log n (loglog n ) O (1) ). We achieve this result via a novel and powerful technique called spanner bootstrapping , which allows one to bootstrap from a superconstant approximation factor (even superpolynomial in the input size) all the way down to a PTAS. This is in contrast with the popular existing approach for planar PTASs of constructing light-weight spanners in one iteration, which notably requires a constant-factor approximate solution to start from. Spanner bootstrapping removes one of the main barriers for designing PTASs for problems which have no known constant-factor approximation (even on planar graphs), and thus can be used to obtain PTASs for several difficult-to-approximate problems.

MFCS Conference 2016 Conference Paper

Routing with Congestion in Acyclic Digraphs

• Saeed Akhoondian Amiri
• Stephan Kreutzer
• Dániel Marx
• Roman Rabinovich 0001

We study the version of the k-disjoint paths problem where k demand pairs (s_1, t_1), .. ., (s_k, t_k) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n^{O(d)} if we allow congestion k-d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f(k)n^{o(d*log(d))} for any computable function f.

FOCS Conference 2016 Conference Paper

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

• Fedor V. Fomin
• Daniel Lokshtanov
• Dániel Marx
• Marcin Pilipczuk
• Michal Pilipczuk
• Saket Saurabh 0001

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: 1) A induces a subgraph of G of treewidth O(√(k log k)), and 2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2 O(√k log2 k) · n O(1))-1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2 O (√(k log 2 k))n O(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include DIRECTED k-Path, WEIGHTED k-Path, VERTEX COVER LOCAL SEARCH, and SUBGRAPH ISOMORPHISM, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

SODA Conference 2016 Conference Paper

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus

• Radu Curticapean
• Dániel Marx

By now, we have a good understanding of how NP-hard problems become easier on graphs of bounded treewidth and bounded cliquewidth: for various problems, matching upper bounds and conditional lower bounds describe exactly how the running time has to depend on treewidth or cliquewidth. In particular, Fomin et al. (2009, 2010) have shown a significant difference between these two parameters: assuming the Exponential-Time Hypothesis (ETH), the optimal algorithms for problems such as M ax C ut and E dge D ominating S et have running time 2 O ( t ) n O (1) when parameterized by treewidth, but n O ( t ) when parameterized by cliquewidth. In this paper, we show that a similar phenomenon occurs also for counting problems. Specifically, we prove that, assuming the counting version of the Strong Exponential-Time Hypothesis (#SETH), the problem of counting perfect matchings has no (2 – ∊ ) k n O (1) time algorithm for any ∊ > 0 on graphs of treewidth k (but it is known to be solvable in time 2 k n O (1) if a tree decomposition of width k is given), and has no O ( n (1– ∊ ) k ) time algorithm for any ∊ > 0 on graphs of cliquewidth k (but it can be solved in time O ( n k +1 ) if a k -expression is given). A celebrated result of Fisher, Kasteleyn, and Temperley from the 1960s shows that counting perfect matchings in planar graphs is polynomial-time solvable. This was later extended by Gallucio and Loebl (1999), Tesler (2000) and Regge and Zechina (2000) who gave 4 k · n O (1) time algorithms for graphs of genus k. We show that the dependence on the genus k has to be exponential: assuming #ETH, the counting version of ETH, there is no 2 o ( k ) · n O (1) time algorithm for the problem on graphs of genus k.

SODA Conference 2015 Conference Paper

An exact characterization of tractable demand patterns for maximum disjoint path problems

• Dániel Marx
• Paul Wollan

We study the following general disjoint paths problem: given a supply graph G, a set T ⊆ V(G) of terminals, a demand graph H on the vertices T, and an integer k, the task is to find a set of k pairwise vertex-disjoint valid paths, where we say that a path of the supply graph G is valid if its endpoints are in T and adjacent in the demand graph H. For a class H of graphs, we denote by M aximum D isjoint ℋ-P aths the restriction of this problem when the demand graph H is assumed to be a member of ℋ. We study the fixed-parameter tractability of this family of problems, parameterized by k. Our main result is a complete characterization of the fixed-parameter tractable cases of M aximum D isjoint ℋ-P aths for every hereditary class ℋ of graphs: it turns out that complexity depends on the existence of large induced matchings and large induced skew bicliques in the demand graph H (a skew biclique is a bipartite graph on vertices a 1, …, a n, b 1, …, b n with a i and b j being adjacent if and only if i ≤ j ). Specifically, we prove the following classification for every hereditary class ℋ. If ℋ does not contain every matching and does not contain every skew biclique, then MAXIMUM D isjoint ℋ-P aths is FPT. If ℋ does not contain every matching, but contains every skew biclique, then MAXIMUM DISJOINT ℋ-P aths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the Erdös-Pósa property. If ℋ contains every matching, then MAXIMUM DISJOINT ℋ-P aths is W[1]-hard and the valid paths do not satisfy the analog of the Erdös-Pósa property.

SODA Conference 2015 Conference Paper

Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels

• Bart M. P. Jansen
• Dániel Marx

We study two fundamental problems related to finding subgraphs: (1) given graphs G and H, S ubgraph T est asks if H is isomorphic to a subgraph of G, (2) given graphs G, H, and an integer t, PACKING asks if G contains t vertex-disjoint subgraphs isomorphic to H. For every graph class ℱ, let ℱ-S ubgraph T est and ℱ-P acking be the special cases of the two problems where H is restricted to be in F. Our goal is to study which classes ℱ make the two problems tractable in one of the following senses: (randomized) polynomial-time solvable, admits a polynomial (many-one) kernel (that is, has a polynomial-time preprocessing procedure that creates an equivalent instance whose size is polynomially bounded by the size of the solution), or admits a polynomial Turing kernel (that is, has an adaptive polynomial-time procedure that reduces the problem to a polynomial number of instances, each of which has size bounded polynomially by the size of the solution). To obtain a more robust setting, we restrict our attention to hereditary classes F. It is known that if every component of every graph in ℱ has at most two vertices, then ℱ-P acking is polynomial-time solvable, and NP-hard otherwise. We identify a simple combinatorial property (every component of every graph in ℱ either has bounded size or is a bipartite graph with one of the sides having bounded size) such that if a hereditary class ℱ has this property, then ℱ-P acking admits a polynomial kernel, and has no polynomial (many-one) kernel otherwise, unless the polynomial hierarchy collapses. Furthermore, if ℱ does not have this property, then ℱ-P acking is either WK[1]-hard, W[1]-hard, or L ong P ath -hard, giving evidence that it does not admit polynomial Turing kernels either. For ℱ-S ubgraph T est, we show that if every graph of a hereditary class ℱ satisfies the property that it is possible to delete a bounded number of vertices such that every remaining component has size at most two, then F- S ubgraph T est is solvable in randomized polynomial time and it is NP-hard otherwise. We introduce a combinatorial property called ( a, b, c, d )-splittability and show that if every graph in a hereditary class ℱ has this property, then F- S ubgraph T est admits a polynomial Turing kernel and it is WK[1]-hard, W[1]-hard, or L ong P ath -hard otherwise. We do not give a complete characterization of the cases when F- S ubgraph T est admits polynomial many-one kernels, but show examples that this question is much more fragile than the characterization for Turing kernels.

SODA Conference 2014 Conference Paper

A subexponential parameterized algorithm for Subset TSP on planar graphs

• Philip N. Klein
• Dániel Marx

Given a graph G and a subset S of vertices, the Subset TSP problem asks for a shortest closed walk in G visiting all vertices of S. The problem can be solved in time 2 k · n O (1) using the classical dynamic programming algorithms of Bellman and of Held and Karp, where k = | S | and n = | V ( G )|. Our main result is showing that the problem can be solved in time if G is a planar graph with weights that are integers no greater than W. While similar speedups have been observed for various paramterized problems on planar graphs, our result cannot be simply obtained as a consequence of bounding the treewidth of G or invoking bidimensionality theory. Our algorithm consists of two steps: (1) find a locally optimal solution, and (2) use it to guide a dynamic program. The proof of correctness of the algorithm depends on a treewidth bound on a graph obtained by combining an optimal solution with a locally optimal solution.

FOCS Conference 2014 Conference Paper

Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts

• Radu Curticapean
• Dániel Marx

For a class C of graphs, #Sub(C) is the counting problem that, given a graph H from C and an arbitrary graph G, asks for the number of subgraphs of G isomorphic to H. It is known that if C has bounded vertex-cover number (equivalently, the size of the maximum matching in C is bounded), then #Sub(C) is polynomial-time solvable. We complement this result with a corresponding lower bound: if C is any recursively enumerable class of graphs with unbounded vertexcover number, then #Sub(C) is #W[1]-hard parameterized by the size of H and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT is equal to #W[1]. As a first step of the proof, we show that counting kmatchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting k-matchings in general graphs; our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no f(k)*n^o(k/log(k)) time algorithm for counting k-matchings in bipartite graphs for any computable function f. As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length k is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.

SODA Conference 2014 Conference Paper

Finding small patterns in permutations in linear time

• Sylvain Guillemot
• Dániel Marx

Given two permutations σ and π, the P ermutation P attern problem asks if σ is a subpattern of π. We show that the problem can be solved in time 2 O ( ℓ 2 log ℓ ). n, where ℓ = | σ | and n = | π |. In other words, the problem is fixed-parameter tractable parameterized by the size of the subpattern to be found. We introduce a novel type of decompositions for permutations and a corresponding width measure. We present a linear-time algorithm that either finds σ as a subpattern of π, or finds a decomposition of π whose width is bounded by a function of | σ |. Then we show how to solve the P ermutation P attern problem in linear time if a bounded-width decomposition is given in the input.

SODA Conference 2014 Conference Paper

Interval Deletion is Fixed-Parameter Tractable

• Yixin Cao 0001
• Dániel Marx

We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph on n vertices into an interval graph. We present a parameterized algorithm of runtime 10 k · n O (1) for this problem, thereby showing its fixed-parameter tractability.

SODA Conference 2014 Conference Paper

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

• Rajesh Chitnis
• MohammadTaghi Hajiaghayi
• Dániel Marx

Given a vertex-weighted directed graph G = ( V, E ) and a set T = { t 1, t 2, … t k } of k terminals, the objective of the S trongly C onnected S teiner S ubgraph (SCSS) problem is to find a vertex set H ⊆ V of minimum weight such that G [ H ] contains a t i → t j path for each i = j. The problem is NP-hard, but Feldman and Ruhl (FOCS '99; SICOMP '06) gave a novel n O ( k ) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a algorithm for planar SCSS, which is an improvement of a factor of in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an algorithm for any computable function f, unless the Exponential Time Hypothesis (ETH) fails. The algorithm eventually relies on the excluded grid theorem for planar graphs, but we stress that it is not simply a straightforward application of treewidth-based techniques: we need several layers of abstraction to arrive to a problem formulation where the speedup due to planarity can be exploited. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: Our algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. In general graphs, we cannot hope for such a dramatic improvement over the n O ( k ) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f ( k ) · n o ( k /log k ) algorithm for any computable function f. Feldman and Ruhl generalized their n O ( k ) algorithm to the more general D irected S teiner F orest (DSF) problem; here the task is to find a subgraph of minimum weight such that for every source s i there is a path to the corresponding terminal t i. We show that that, assuming ETH, there is no f ( k ) · n o ( k ) time algorithm for DSF on acyclic planar graphs.

I&C Journal 2013 Journal Article

Clustering with local restrictions

• Daniel Lokshtanov
• Dániel Marx

We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement. Formally, let μ be a function on the subsets of vertices of a graph G. In the ( μ, p, q ) -Partition problem, the task is to find a partition of the vertices into clusters where each cluster C satisfies the requirements that (1) at most q edges leave C and (2) μ ( C ) ⩽ p. Our first result shows that if μ is an arbitrary polynomial-time computable monotone function, then ( μ, p, q ) -Partition can be solved in time n O ( q ), i. e. , it is polynomial-time solvable for every fixed q. We study in detail three concrete functions μ (the number of vertices in the cluster, number of nonedges in the cluster, maximum number of non-neighbors a vertex has in the cluster), which correspond to natural clustering problems. For these functions, we show that ( μ, p, q ) -Partition can be solved in time 2 O ( p ) ⋅ n O ( 1 ) and in time 2 O ( q ) ⋅ n O ( 1 ) on n-vertex graphs, i. e. , the problem is fixed-parameter tractable parameterized by p or by q.

FOCS Conference 2013 Conference Paper

The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable

• Marek Cygan
• Dániel Marx
• Marcin Pilipczuk
• Michal Pilipczuk

Given a graph G and k pairs of vertices (s 1, t 1 ), .. ., (s k, t k ), the k-Vertex-Disjoint Paths problem asks for pair wise vertex-disjoint paths P 1, .. ., Pk such that Pi goes from si to ti. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time nO(k). We give an algorithm with running time 2 2O(k2) * n O(1) for the problem, that is, we show the fixed-parameter tractability of the problem.

SODA Conference 2012 Conference Paper

Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset

• Rajesh Chitnis
• MohammadTaghi Hajiaghayi
• Dániel Marx

SODA Conference 2012 Conference Paper

Kernelization of packing problems

• Holger Dell
• Dániel Marx

Kernelization algorithms are polynomial-time reductions from a problem to itself that guarantee their output to have a size not exceeding some bound. For example, d -S et M atching for integers d ≥ 3 is the problem of finding a matching of size at least k in a given d -uniform hypergraph and has kernels with O ( k d ) edges. Recently, Bodlaender et al. [ICALP 2008], Fortnow and Santhanam [STOC 2008], Dell and Van Melkebeek [STOC 2010] developed a framework for proving lower bounds on the kernel size for certain problems, under the complexity-theoretic hypothesis that coNP is not contained in NP/poly. Under the same hypothesis, we show lower bounds for the kernelization of d -S et M atching and other packing problems. Our bounds are tight for d -S et M atching: It does not have kernels with O ( k d−∊ ) edges for any ∊ > 0 unless the hypothesis fails. By reduction, this transfers to a bound of O ( k d − 1 − ∊ ) for the problem of finding k vertex-disjoint cliques of size d in standard graphs. It is natural to ask for tight bounds on the kernel sizes of such graph packing problems. We make first progress in that direction by showing non-trivial kernels with O ( k 2. 5 ) edges for the problem of finding k vertex-disjoint paths of three edges each. This does not quite match the best lower bound of O ( k 2−∊ ) that we can prove. Most of our lower bound proofs follow a general scheme that we discover: To exclude kernels of size O ( k d −∊ ) for a problem in d -uniform hypergraphs, one should reduce from a carefully chosen d -partite problem that is still NP-hard. As an illustration, we apply this scheme to the vertex cover problem, which allows us to replace the number-theoretical construction by Dell and Van Melkebeek [STOC 2010] with shorter elementary arguments.

STOC Conference 2012 Conference Paper

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

• Martin Grohe
• Dániel Marx

We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter |H|.

TCS Journal 2011 Journal Article

Complexity of clique coloring and related problems

• Dániel Marx

A k -clique-coloring of a graph G is an assignment of k colors to the vertices of G such that every maximal (i. e. , not extendable) clique of G contains two vertices with different colors. We show that deciding whether a graph has a k -clique-coloring is Σ 2 p -complete for every k ≥ 2. The complexity of two related problems are also considered. A graph is k -clique-choosable, if for every k -list-assignment on the vertices, there is a clique coloring where each vertex receives a color from its list. This problem turns out to be Π 3 p -complete for every k ≥ 2. A graph G is hereditary k -clique-colorable if every induced subgraph of G is k -clique-colorable. We prove that deciding hereditary k -clique-colorability is also Π 3 p -complete for every k ≥ 3. Therefore, for all the problems considered in the paper, the obvious upper bound on the complexity turns out to be the exact class where the problem belongs.

STOC Conference 2011 Conference Paper

Finding topological subgraphs is fixed-parameter tractable

• Martin Grohe
• Ken-ichi Kawarabayashi
• Dániel Marx
• Paul Wollan

We prove that for every fixed undirected graph H , there is an O(|V(G)| 3 ) time algorithm that, given a graph G , tests if G contains H as a topological subgraph (that is, a subdivision of H is subgraph of G ). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every H we obtain an O(|V(G)| 3 ) time algorithm that tests if there is an immersion of H into a given graph G . This answers another open question raised by Downey and Fellows in 1992.

STOC Conference 2011 Conference Paper

Fixed-parameter tractability of multicut parameterized by the size of the cutset

• Dániel Marx
• Igor Razgon

Given an undirected graph $G$, a collection {(s 1 ,t 1 ), ..., (s l ,t l )} of pairs of vertices, and an integer p, the Edge Multicut problem ask if there is a set S of at most p edges such that the removal of S disconnects every s i from the corresponding t i . Vertex Multicut is the analogous problem where S is a set of at most p vertices. Our main result is that both problems can be solved in time 2 O(p 3 ) ⋅ n O(1) , i.e., fixed-parameter tractable parameterized by the size p of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form f(p) ⋅ n O(1) exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

SODA Conference 2011 Conference Paper

Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal

• Daniel Lokshtanov
• Dániel Marx
• Saket Saurabh 0001

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that SAT cannot be solved in (2 − ε) n m O (1) time, we show that for any ε > 0; I ndependent S et cannot be solved in time (2 − ε) tw( G ) | V ( G )| O (1), D ominating S et cannot be solved in time (3 − ε) tw( G ) | V ( G )| O (1), M ax C ut cannot be solved in time (2 − ε) tw( G ) | V ( G )| O (1), O dd C ycle T ranversal cannot be solved in time (3 − ε) tw( G ) | V ( G )| O (1), For any q ≥ 3, q -C oloring cannot be solved in time ( q − ε) tw( G ) | V ( G )| O (1), P artition I nto T riangles cannot be solved in time (2 − ε) tw( G ) | V ( G )| O (1). Our lower bounds match the running times for the best known algorithms for the problems, up to the ε in the base.

SODA Conference 2011 Conference Paper

Prize-collecting Steiner Problems on Planar Graphs

• MohammadHossein Bateni
• Chandra Chekuri
• Alina Ene
• MohammadTaghi Hajiaghayi
• Nitish Korula
• Dániel Marx

SODA Conference 2011 Conference Paper

Slightly Superexponential Parameterized Problems

• Daniel Lokshtanov
• Dániel Marx
• Saket Saurabh 0001

A central problem in parameterized algorithms is to obtain algorithms with running time f ( k ) · n O (1) such that f is as slow growing function of the parameter k as possible. In particular, the first natural goal is to make f ( k ) single-exponential, that is, c k for some constant c. This has led to the development of parameterized algorithms for various problems where f ( k ) appearing in their running time is of form 2 O ( k ). However there are still plenty of problems where the “slightly superexponential” f ( k ) appearing in the best known running time has remained non single-exponential even after a lot of attempts to bring it down. A natural question to ask is whether the f ( k ) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f ( k ) is k O ( k ) = 2 O ( k log k ) in the best known running time and for a number of such problems, we show that the dependence on k in the running time cannot be improved to single exponential. More precisely we prove following tight lower bounds, for three natural problems, arising from three different domains: The pattern matching problem C losest S tring is known to be solvable in time 2 O ( d log d ) · n O (1) and 2 O ( d log |σ|) · n O (1). We show that there is no 2 o ( d log d ). · n O (1) and 2 o ( d log |σ|) · n O (1) time algorithm, unless Exponential Time Hypothesis (ETH) fails. The graph embedding problem D istortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be done in time 2 O ( d log d ) · n O (1). We show that there is no 2 o ( d log d ) · n O (1) time algorithm, unless ETH fails. The D isjoint P aths problem can be solved in time in time 2 O ( w log w ) · n O (1) on graphs of treewidth at most w. We show that there is no 2 o ( w log w ) · n O (1) time algorithm, unless ETH fails. To obtain our result we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. We believe that many further results of this form can be obtained by using the framework of the current paper.

STOC Conference 2010 Conference Paper

Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth

• MohammadHossein Bateni
• MohammadTaghi Hajiaghayi
• Dániel Marx

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded treewidth graphs needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded treewidth graphs, planar graphs, and bounded genus graphs.

MFCS Conference 2010 Conference Paper

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

• Stefan Kratsch
• Dániel Marx
• Magnus Wahlström

Abstract For a finite set \(\it\Gamma\) of Boolean relations, Max Ones SAT( \(\it\Gamma\) ) and Exact Ones SAT( \(\it\Gamma\) ) are generalized satisfiability problems where every constraint relation is from \(\it\Gamma\), and the task is to find a satisfying assignment with at least/exactly k variables set to 1, respectively. We study the parameterized complexity of these problems, including the question whether they admit polynomial kernels. For Max Ones SAT( \(\it\Gamma\) ), we give a classification into 5 different complexity levels: polynomial-time solvable, admits a polynomial kernel, fixed-parameter tractable, solvable in polynomial time for fixed k, and NP-hard already for k = 1. For Exact Ones SAT( \(\it\Gamma\) ), we refine the classification obtained earlier by having a closer look at the fixed-parameter tractable cases and classifying the sets \(\it\Gamma\) for which Exact Ones SAT( \(\it\Gamma\) ) admits a polynomial kernel.

STOC Conference 2010 Conference Paper

Tractable hypergraph properties for constraint satisfaction and conjunctive queries

• Dániel Marx

An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure of the constraints influences the complexity of the problem. For binary CSP instances (i.e., where each constraint involves only two variables), the situation is well understood: the complexity of the problem essentially depends on the treewidth of the graph of the constraints. However, this is not the correct answer if constraints with unbounded number of variables are allowed, and in particular, for CSP instances arising from query evaluation problems in database theory. Formally, if H is a class of hypergraphs, then let CSP(H) be CSP restricted to instances whose hypergraph is in H. Our goal is to characterize those classes of hypergraphs for which CSP(H) is polynomial-time solvable or fixed-parameter tractable, parameterized by the number of variables. In the applications related to database query evaluation, we usually assume that the number of variables is much smaller than the size of the instance, thus parameterization by the number of variables is a meaningful question. The most general known property of H that makes CSP(H) polynomial-time solvable is bounded fractional hypertree width. Here we introduce a new hypergraph measure called submodular width, and show that bounded submodular width of H (which is a strictly more general property than bounded fractional hypertree width) implies that CSP(H) is fixed-parameter tractable. In a matching hardness result, we show that if H has unbounded submodular width, then CSP(H) is not fixed-parameter tractable (and hence not polynomial-time solvable), unless the Exponential Time Hypothesis (ETH) fails. The algorithmic result uses tree decompositions in a novel way: instead of using a single decomposition depending on the hypergraph, the instance is split into a set of instances (all on the same set of variables as the original instance), and then the new instances are solved by choosing a different tree decomposition for each of them. The reason why this strategy works is that the splitting can be done in such a way that the new instances are "uniform" with respect to the number extensions of partial solutions, and therefore the number of partial solutions can be described by a submodular function. For the hardness result, we prove via a series of combinatorial results that if a hypergraph H has large submodular width, then a 3SAT instance can be efficiently simulated by a CSP instance whose hypergraph is H. To prove these combinatorial results, we need to develop a theory of (multicommodity) flows on hypergraphs and vertex separators in the case when the function b(S) defining the cost of separator S is submodular.

TCS Journal 2009 Journal Article

A parameterized view on matroid optimization problems

• Dániel Marx

Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial n O ( k ) time brute force algorithm for finding a k -element solution, we try to give algorithms with uniformly polynomial (i. e. , f ( k ) ⋅ n O ( 1 ) ) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ℓ, then we can determine in randomized time f ( k, ℓ ) ⋅ n O ( 1 ) whether there is an independent set that is the union of k blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k -element set in the intersection of ℓ matroids, or finding k terminals in a network such that each of them can be connected simultaneously to the source by ℓ disjoint paths.

SODA Conference 2009 Conference Paper

Approximating fractional hypertree width

• Dániel Marx

TCS Journal 2008 Journal Article

Complexity of unique list colorability

• Dániel Marx

Given a list L ( v ) for each vertex v, we say that the graph G is L -colorable if there is a proper vertex coloring of G where each vertex v takes its color from L ( v ). The graph is uniquely k -list colorable if there is a list assignment L such that ∣ L ( v ) ∣ = k for every vertex v and the graph has exactly one L -coloring with these lists. Mahdian and Mahmoodian [M. Mahdian, E. S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. 51 (1999) 295–305] gave a polynomial-time characterization of uniquely 2-list colorable graphs. Answering an open question from [M. Ghebleh, E. S. Mahmoodian, On uniquely list colorable graphs, Ars Combin. 59 (2001) 307–318; M. Mahdian, E. S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. 51 (1999) 295–305], we show that uniquely 3-list colorable graphs are unlikely to have such a nice characterization, since recognizing these graphs is Σ 2 p -complete.

FOCS Conference 2008 Conference Paper

Size Bounds and Query Plans for Relational Joins

• Albert Atserias
• Martin Grohe
• Dániel Marx

Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimisers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model, and in an average-case model where the database is chosen according to a known probability distribution. In the former case, our first key observation is that the worst-case size of a query is characterised by the fractional edge cover number of its underlying hypergraph, a combinatorial parameter previously known to provide an upper bound. We complete the picture by proving a matching lower bound, and by showing that there exist queries for which the join-project plan suggested by the fractional edge cover approach may be substantially better than any join plan that does not use intermediate projections.

FOCS Conference 2007 Conference Paper

Can you beat treewidth?

• Dániel Marx

It is well-known that constraint satisfaction problems (CSP) can be solved in time n O(k) if the treewidth of the primal graph of the instance is at most k and n is the size of the input. We show that no algorithm can be significantly better than this treewidth-based algorithm, even if we restrict the problem to some special class of primal graphs. Formally, let g be an arbitrary class of graphs and assume that there is an algorithm A solving binary CSP for instances whose primal graph is in g. We prove that if the running lime of A is f(G)n O(k/logk), where k is the treewidth of the primal graph G and f is an arbitrary function, then the Exponential Time Hypothesis fails. We prove the result also in the more general framework of the homomorphism problem for bounded-arity relational structures. For this problem, the treewidth of the core of the left-hand side structure plays the same role as the. treewidth of the primal graph above.

FOCS Conference 2007 Conference Paper

On the Optimality of Planar and Geometric Approximation Schemes

• Dániel Marx

We show for several planar and geometric problems that the best known approximation schemes are essentially optimal with respect to the dependence on epsi. For example, we show that the 2 O(1/epsi) ldrn time approximation schemes for planar maximum independent set and for TSP on a metric defined bv a planar graph are essentially optimal: if there is a delta>0 such that any of these problems admits a 2 O((1/epsi) 1-delta ) n O(1) time PTAS, then the exponential tune hypothesis (ETH) fails. It is known that maximum independent set on unit disk graphs and the planar logic problems MPSAT. TMIN, TMAX admit n O(1/epsi) time approximation schemes. We show that they are optimal in the sense that if there is a delta>0 such that any of these problems admits a 2 (1/epsi) O(1) n O((1/epsi) 1-delta ) time PTAS, then ETH fails.

SODA Conference 2006 Conference Paper

Constraint solving via fractional edge covers

• Martin Grohe
• Dániel Marx

TCS Journal 2006 Journal Article

Minimum sum multicoloring on the edges of trees

• Dániel Marx

The edge multicoloring problem is that given a graph G and integer demands x ( e ) for every edge e, assign a set of x ( e ) colors to edge e, such that adjacent edges have disjoint sets of colors. In the minimum sum edge multicoloring problem the finish time of an edge is defined to be the highest color assigned to it. The goal is to minimize the sum of the finish times. The main result of the paper is a polynomial-time approximation scheme for minimum sum multicoloring the edges of trees. We also show that the problem is strongly NP-hard for trees, even if every demand is at most 2.

TCS Journal 2006 Journal Article

Parameterized coloring problems on chordal graphs

• Dániel Marx

In the precoloring extension problem (PREXT) a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper coloring of the graph with the given number of colors. Two parameterized versions of the problem are studied in the paper: either the number of precolored vertices or the number of colors used in the precoloring is restricted to be at most k. We show that for chordal graphs these problems are polynomial-time solvable for every fixed k, but W[1]-hard if k is the parameter. For a graph class F, let F + ke (resp. , F + kv ) denote those graphs that can be made to be a member of F by deleting at most k edges (resp. , vertices). We investigate the connection between PREXT in F (with the two parameters defined above) and the coloring of F + ke, F + kv graphs (with k being the parameter). Answering an open question of Leizhen Cai [Parameterized complexity of vertex colouring, Discrete Appl. Math. 127 (2003) 415–429], we show that coloring chordal + ke graphs is fixed-parameter tractable.

TCS Journal 2006 Journal Article

Parameterized graph separation problems

• Dániel Marx

We consider parameterized problems where some separation property has to be achieved by deleting as few vertices as possible. The following five problems are studied: delete k vertices such that (a) each of the given ℓ terminals is separated from the others, (b) each of the given ℓ pairs of terminals is separated, (c) exactly ℓ vertices are cut away from the graph, (d) exactly ℓ connected vertices are cut away from the graph, (e) the graph is separated into at least ℓ components. We show that if both k and ℓ are parameters, then (a), (b) and (d) are fixed-parameter tractable, while (c) and (e) are W[1]-hard.

FOCS Conference 2005 Conference Paper

The Closest Substring problem with small distances

• Dániel Marx

In the closest substring problem k strings s/sub 1/, .. ., s/sub k/ are given, and the task is to find a string s of length L such that each string s/sub i/, has a consecutive substring of length L whose distance is at most d from s. The problem is motivated by applications in computational biology. We present two algorithms that can be efficient for small fixed values of d and k: for some functions f and g, the algorithms have running time f(d) /spl middot/ n(O(log d)) and g(d, k) /spl middot/ n(O(log log k)), respectively. The second algorithm is based on connections with the extremal combinatorics of hypergraphs. The closest substring problem is also investigated from the parameterized complexity point of view. Answering an open question from (Evans et al. , 2003; Fellows et al. ; Gramm et al. , 2003), we show that the problem is W[1] hard even if both d and k are parameters. It follows as a consequence of this hardness result that our algorithms are optimal in the sense that the exponent of n in the running time cannot be improved to o(log d) or to o(log log k) (modulo some complexity-theoretic assumptions). Another consequence is that the running time n/sup O(1//spl epsiv/4)/ of the approximation scheme for closest substring presented in (Li et al. , 2002) cannot be improved to f(/spl epsiv/) /spl middot/ n/sup c/, i. e. the /spl epsiv/ has to appear in the exponent of n.

MFCS Conference 2002 Conference Paper

The Complexity of Tree Multicolorings

• Dániel Marx

Abstract The multicoloring problem is that given a graph G and integer demands x ( v ) for every vertex v, assign a set of x ( v ) colors to vertex v, such that neighboring vertices have disjoint sets of colors. In the preemptive sum multicoloring problem the finish time of a vertex is defined to be the highest color assigned to it. The goal is to minimize the sum of the finish times. The study of this problem is motivated by applications in scheduling. Answering a question of Halldórsson et al. [ 4 ], we show that the problem is strongly NP -hard in binary trees. As a first step toward this result we prove that list multicoloring of binary trees is NP -complete.