Publications of Dániel Marx

Note: The copyright of the published papers is with the respective publishers. The papers are made available here to ensure the timely dissemination of scholarly information. The published versions of the papers may have gone through additional rounds of copyediting and proofreading. Most of the papers here list the authors in strict alphabetic ordering, which is the standard convention in mathematics and theoretical computer science.

Detailed list (with abstracts)List of research talksDBLP

Journal papers:
2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004

Conference papers without journal versions:
2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000

Papers appearing in edited volumes:
2020 2012

Volume editing:
2012

Manuscripts

Books

  1. by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov,
    Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh

    Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555.
Journal papers
202120202019201820172016201520142013201220112010200920082007200620052004
    2021

  1. Journal of the ACM. 68(3): 16:1-16:40, 2021.
    (with: Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi)

  2. Journal of the ACM, 68(4): 30:1-30:26, 2021
    (with: Vincent Cohen-Addad, Éric Colin de Verdière, and Arnaud de Mesmay)

    Conference version:
    In Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), 27:1-27:16, 2019.
    (with: Vincent Cohen-Addad, Éric Colin de Verdière, and Arnaud de Mesmay)

  3. Algorithmica, 83(8): 2552-2577 (2021)
    (with: Benjamin Aram Berendsohn and László Kozma)

    Conference version:
    In Proceedings of 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), 1:1-1:16
    (with: Benjamin Aram Berendsohn and László Kozma)

    2020

  4. SIAM J. Comput. 49(2): 318-364, 2020.
    (with: Rajesh Chitnis, Andreas Feldmann and MohammadTaghi Hajiaghayi)

    Conference version:
    In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 1782-1801, 2014.
    (with: Rajesh Chitnis and MohammadTaghi Hajiaghayi)

  5. SIAM J. Comput. 49(6): 1291-1331, 2020.
    (with:Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Tom C. van der Zanden)

    Conference version:
    In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), 574-586, 2018.
    (with: Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Tom C. van der Zanden)

  6. Algorithmica 82(8): 2135-2155, 2020.
    (with: Stefan Kratsch, Shaohua Li, Marcin Pilipczuk, and Magnus Wahlström)

    Conference version:
    In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), 18:1-18:14, 2018.
    (with: Stefan Kratsch, Shaohua Li, Marcin Pilipczuk, and Magnus Wahlström)

  7. Algorithmica 82(7): 1989-2005, 2020.
    (with: Andreas Feldmann)

    Conference version:
    In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), 19:1-19:13, 2018.
    (with: Andreas Feldmann)

    2019

  8. Algorithmica 81(10): 3890-3935, 2019.
    (with: Édouard Bonnet, Nick Brettell, and O-joung Kwon)

    Conference version:
    42nd In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), 7:1-7:13, 2017.
    (with: Édouard Bonnet, Nick Brettell, and O-joung Kwon)

  9. Inf. Process. Lett. 151, 7:1-7:11, 2019.
    (with: Saeed Akhoondian Amiri, Stephan Kreutzer, and Roman Rabinovich)

    Conference version:
    41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 7:1-7:11, 2016.
    (with: Saeed Akhoondian Amiri, Stephan Kreutzer, and Roman Rabinovich)

  10. Algorithmica,81(2):421-438, 2019.
    (with: Gábor Bacsó, Daniel Lokshtanov, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan van Leeuwen)

    Conference version:
    11th International Symposium on Parameterized and Exact Computation (IPEC 2016),3:1-3:12, 2016.
    (with: Gábor Bacsó and Zsolt Tuza)

    2018

  11. ACM Transactions on Algorithms, 14(2):13:1-13:30, 2018.
    (with: Daniel Lokshtanov and Saket Saurabh)

    Conference version:
    In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 777-789, 2011.
    (with: Daniel Lokshtanov and Saket Saurabh)

    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-ε)nmO(1) time, we show that for any ε> 0;
    • INDEPENDENT SET cannot be solved in (2-ε)tw(G)|V(G)|O(1) time,
    • DOMINATING SET cannot be solved in (3-ε)tw(G)|V(G)|O(1) time,
    • MAX CUT cannot be solved in (2-ε)tw(G)|V(G)|O(1) time,
    • ODD CYCLE TRANSVERSAL cannot be solved in (2-ε)tw(G)|V(G)|O(1) time,
    • For any q≥3, q-COLORING cannot be solved in (q-ε)tw(G)|V(G)|O(1) time,
    • PARTITION INTO TRIANGLES cannot be solved in (2-ε)tw(G)|V(G)|O(1) time.
    Our lower bounds match the running times for the best known algorithms for the problems, up to the ε in the base.

  12. SIAM Journal on Computing, 47(3):675-702, 2018..
    (with: Daniel Lokshtanov and Saket Saurabh)

    Conference version:
    In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 760-776, 2011.
    (with: Daniel Lokshtanov and Saket Saurabh)

    A central problem in parameterized algorithms is to obtain algorithms with running time f(k)nO(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 2O(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 kO(k)=2O(klog 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 CLOSEST STRING is known to be solvable in time 2O(dlog d)nO(1) and 2O(dlog |Σ|)nO(1). We show that there is no 2o(dlog d)nO(1) and 2o(dlog |Σ|)nO(1) time algorithm, unless Exponential Time Hypothesis (ETH) fails.
    • The graph embedding problem DISTORTION, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be done in time 2O(dlog d)nO(1). We show that there is no 2o(dlog d)nO(1) time algorithm, unless ETH fails.
    • The DISJOINT PATHS problem can be solved in time in time 2O(wlog w)nO(1) on graphs of treewidth at most w. We show that there is no 2o(wlog w)nO(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.

  13. Journal of Computational Geometry, 9(2):47-80, 2018.
    (with: Csaba Bíró, Édouard Bonnet, Till Miltzow, and Pawel Rzazewski)

    Conference version:
    In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), 18:1-18:16, 2017.
    (with: Csaba Bíró, Édouard Bonnet, Till Miltzow, and Pawel Rzazewski)

    2017

  14. J. Combinatorial Theory Ser. B, 122:428-437, 2017.
    (with: Paul Seymour and Paul Wollan)

  15. Algorithmica, 78(1):110-146, 2017.
    (with: Rajesh Chitnis, László Egri)

    Conference version:
    In Proceedings of the 21st European Symposium on Algorithms (ESA 2013), Lecture Notes in Computer Science Volume 8125, Springer, 313-324, 2013.
    (with: Rajesh Chitnis, László Egri)

    In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v)⊆V(H) for each vertex v\∈V(G), and an integer k. The task is to decide whether there exists a set WV(G) of size at most k such that there is a homomorphism from G\W to H respecting the lists. We show that DL-HOM(H), parameterized by k and |H|, is fixed-parameter tractable for any (P6,C6)-free bipartite graph H; already for this restricted class of graphs, the problem generalizes Vertex Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the size of the cutset and the number of terminals. We conjecture that DL-HOM(H) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable; by a result of Feder et al., a graph H belongs to this class precisely if it is a bipartite graph whose complement is a circular arc graph. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT.

  16. Information and Computation, 256:62-82, 2017.
    (with:Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk)

    Conference version:
    Mathematical foundations of computer science (MFCS 2014), (2)489-500, Lecture Notes in Comput. Sci., 8635, Springer, 2014.
    (with:Marek Cygan, Marcin Pilipczuk, Michal 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 we seek for the minimum size of a set X of vertices 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 (e.g., Courcelle's theorem) show that, for every fixed H and 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 2O(tμ(H))|V(G)|, but cannot be solved in time 2o(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.

  17. Journal of Graph Theory, 85(4):814-838, 2017.
    (with:Pierre Aboulker, Nick Brettel, Fréderic Havét, Nicolas Trotignon)

    A graph G has maximal local edge-connectivity k if the maximum number of edge-disjoint paths between every pair of distinct vertices x and y is at most k. We prove Brooks-type theorems for k-connected graphs with maximal local edge-connectivity k, and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph G with maximal local connectivity 3, outputs an optimal colouring for G. On the other hand, we prove, for k ≥ 3, that k-COLOURABILITY is NP-complete when restricted to minimally k-connected graphs, and 3-COLOURABILITY is NP-complete when restricted to (k-1)-connected graphs with maximal local connectivity k. Finally, we consider a parameterization of k-COLOURABILITY based on the number of vertices of degree at least k+1, and prove that, even when k is part of the input, the corresponding parameterized problem is FPT.

    2016

  18. ACM Transactions on Computation Theory, 8(1):1:1-1:28, 2016.
    (with: Stefan Kratsch, Magnus Wahlström)

    Conference version:
    Mathematical foundations of computer science (MFCS 2010), 489-500, Lecture Notes in Comput. Sci., 6281, Springer, 2010.
    (with: Stefan Kratsch, Magnus Wahlström)

    For a finite set Γ of Boolean relations, Max Ones SAT(Γ) and Exact Ones SAT(Γ) are generalized satisfiability problems where every constraint relation is from Γ, 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(Γ), 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(Γ), we refine the classification obtained earlier by having a closer look at the fixed-parameter tractable cases and classifying the sets Γ for which Exact Ones SAT(Γ) admits a polynomial kernel.

  19. ACM Transactions on Algorithms, 12(3):41:1-41:24, 2016.
    (with:Marek Cygan, Holger Dell, Daniel Lokshtanov, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström)

    Conference version:
    Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC 2012), 74-84, 2012.
    (with:Marek Cygan, Holger Dell, Daniel Lokshtanov, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström)

    The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET, 3-CNF-SAT. In some instances, improving these algorithms further seems to be out of reach. The CNF-SAT problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-SAT that run in time o(2n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ε<1, there is a (large) integer k such that that k-CNF-SAT cannot be computed in time 2εn. In this paper, we show that, for every ε<1, the problems HITTING SET, SET SPLITTING, and NAE-SAT cannot be computed in time O(2εn) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for SET COVER, and prove that, under this assumption, the fastest known algorithms for STEINER TREE, CONNECTED VERTEX COVER, SET PARTITIONING, and the pseudo-polynomial time algorithm for SUBSET SUM cannot be significantly improved. Finally, we justify our assumption about the hardness of SET COVER by showing that the parity of the number of set covers cannot be computed in time O(2εn) for any ε<1 unless SETH fails.

  20. Algorithmica, 75(1):118-137, 2016.
    (with: Yixin Cao)

    Conference version:
    In Proceedings of 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 214-225, 2014.
    (with: Yixin Cao)

    Graph modification problems are typically asked as follows: is there a set of k operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the same property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem which allows all three types of operations: given a graph G and integers k1, k2, and k3, the CHORDAL EDITING problem asks if G can be transformed into a chordal graph by at most k1 vertex deletions, k2 edge deletions, and k3 edge additions. Clearly, this problem generalizes both CHORDAL VERTEX/EDGE DELETION and CHORDAL COMPLETION (also known as MINIMUM FILL-IN). Our main result is an algorithm for CHORDAL EDITING in time 2O(k log(k)) nO(1), where k:= k1+ k2+ k3; therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case CHORDAL DELETION.

    2015

  21. SIAM Journal on Computing, 44(1):114-159, 2015.
    (with: Martin Grohe)

    Conference version:
    In Proceedings of the 44th annual ACM symposium on Theory of computing (STOC 2012), 173-192, 2012.
    (with: Martin Grohe)

    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|. We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a ``typical'' application of the structure theorem, we show that on graphs excluding H as a topological subgraph, PARTIAL DOMINATING SET (find k vertices whose closed neighborhood has maximum size) can be solved in time f(H,k)nO(1) time. More significantly, we show that on graphs excluding H as a topological subgraph, GRAPH ISOMORPHISM can be solved in time nf(H). This result unifies and generalizes two previously known important polynomial-time solvable cases of GRAPH ISOMORPHISM: bounded-degree graphs and H-minor free graph. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition.

  22. ACM Transaction on Algorithms, 11(3):21, 2015.
    (with: Yixin Cao)

    Conference version:
    In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 122-141, 2014.
    (with: Yixin Cao)

    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 10knO(1) for this problem, thereby showing its fixed-parameter tractability.

  23. ACM Transaction on Algorithms, 11(4):27m 2015.
    (with: László A. Végh)

    Conference version:
    40th International Colloquium on Automata, Languages and Programming (ICALP 2013), 721-732, Lecture Notes in Comput. Sci., 7965, Springer, 2013.
    (with: László A. Végh)

    We consider connectivity-augmentation problems in a setting where each potential new edge has a nonnegative cost associated with it, and the task is to achieve a certain connectivity target with at most p new edges of minimum total cost. The main result is that the minimum cost augmentation of edge-connectivity from k-1 to k with at most p new edges is fixed-parameter tractable parameterized by p and admits a polynomial kernel. We also prove the fixed-parameter tractability of increasing edge-connectivity from 0 to 2, and increasing node-connectivity from 1 to 2.

  24. ACM Transaction on Algorithms, 11(4):28, 2015.
    (with: Rajesh Chitnis, Marek Cygan, and MohammadTaghi Hajiaghayi)

    Conference version:
    39th International Colloquium on Automata, Languages and Programming (ICALP 2012), 230-241, Lecture Notes in Comput. Sci., 7391, Springer, 2012..
    (with: Rajesh Chitnis, Marek Cygan, and MohammadTaghi Hajiaghayi)

    Given a graph G and an integer k, the FEEDBACK VERTEX SET (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. Bodlaender (WG '91) gave the first fixed-parameter algorithm for FVS in undirected graphs. The fixed-parameter tractability status of FVS in directed graphs was along-standing open problem until Chen et al. (STOC '08) showed that it is fixed-parameter tractable by giving an 4kk!nO(1) algorithm. In the subset versions of this problems, we are given an additional subset S of vertices (resp. edges) and we want to hit all cycles passing through a vertex of S (resp. an edge of S). Indeed both the edge and vertex versions are known to be equivalent in the parameterized sense. Recently the SUBSET FEEDBACK VERTEX SET in undirected graphs was shown to be FPT by Cygan et al. (ICALP '11) and Kakimura et al. (SODA '12). We generalize the result of Chen et al. (STOC '08) by showing that SUBSET FEEDBACK VERTEX SET in directed graphs can be solved in time 22O(k)nO(1), i.e., FPT parameterized by size k of the solution. By our result, we complete the picture for feedback vertex set problems and their subset versions in undirected and directed graphs. The technique of random sampling of important separators was used by Marx and Razgon (STOC '11) to show that UNDIRECTED MULTICUT is FPT and was generalized by Chitnis et al. (SODA '12) to directed graphs to show that DIRECTED MULTIWAY CUT is FPT. In this paper we give a general family of problems (which includes DIRECTED MULTIWAY CUT and DIRECTED SUBSET FEEDBACK VERTEX SET among others) for which we can do random sampling of important separators and obtain a set which is disjoint from a minimum solution and covers its "shadow". We believe this general approach will be useful for showing the fixed-parameter tractability of other problems in directed graphs.

  25. Algorithmica, 72(3):687-713, 2015.
    (with: Pinar Heggernes, Pim van 't Hof, Neeldhara Misra, and Yngve Villanger)

    Conference version:
    38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012), 332-343, Lecture Notes in Comput. Sci., 7551, Springer, 2012.
    (with: Pinar Heggernes, Pim van 't Hof, Neeldhara Misra, and Yngve Villanger)

    We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t} separator is polynomial-time solvable (Tarjan 1985), while for example the problems of finding a minimum s-t separator that is a connected graph or an independent set are fixed-parameter tractable (Marx, O'Sullivan and Razgon, manuscript). We extend these results the following way:
    1. Finding a minimum c-connected s-t separator is FPT for c=2 and W[1]-hard for any c≥3
    2. Finding a minimum s-t separator with diameter at most d is W[1]-hard for any d≥2.
    3. Finding a minimum r-regular s-t separator is W[1]-hard for any r≥1
    4. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree.
    We also show that finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless NP is a subset of coNP/poly.

    2014

  26. SIAM Journal on Computing, 43(2):355-388, 2014.
    (with: Andrei Bulatov)

    Conference version:
    38th International Colloquium on Automata, Languages and Programming (ICALP 2011), 424-436, Lecture Notes in Comput. Sci., 6755, Springer, 2011.
    (with: Andrei Bulatov)

    In the constraint satisfaction problem (CSP) corresponding to a constraint language (i.e., a set of relations) Γ, the goal is to find an assignment of values to variables so that a given set of constraints specified by relations from Γ is satisfied. In this paper we study the fixed-parameter tractability of constraint satisfaction problems parameterized by the size of the solution in the following sense: one of the possible values, say 0, is ``free,'' and the number of variables allowed to take other, ``expensive,'' values is restricted. A size constraint requires that exactly k variables take nonzero values. We also study a more refined version of this restriction: a global cardinality constraint prescribes how many variables have to be assigned each particular value. We study the parameterized complexity of these types of CSPs where the parameter is the required number k of nonzero variables. As special cases, we can obtain natural and well-studied parameterized problems such as INDEPENDENT SET, VERTEX COVER, -HITTING SET, BICLIQUE, etc. In the case of constraint languages closed under substitution of constants, we give a complete characterization of the fixed-parameter tractable cases of CSPs with size constraints, and we show that all the remaining problems are W[1]-hard. For CSPs with cardinality constraints, we obtain a similar classification, but for some of the problems we are only able to show that they are BICLIQUE-hard. The exact parameterized complexity of the BICLIQUE problem is a notorious open problem, although it is believed to be W[1]-hard.

  27. SIAM Journal on Computing, 43(2):355-388, 2014.
    (with: Igor Razgon)

    Conference version:
    In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC 2011), 469-478, 2011.
    (with: Igor Razgon)

    Given an undirected graph G, a collection {(s1,t1),...,(sk,tk)} 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 si from the corresponding ti. 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 2O(p3)nO(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 2O(p3)nO(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.

  28. ACM Transactions on Algorithms, 10(4):21, 2014
    (with: Holger Dell, Thore Husfeldt, Nina Taslaman, Martin Wahlén)

    We show conditional lower bounds for well-studied #P-hard problems:
    • The number of satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph.
    • The permanent of an n*n matrix with entries 0 and 1 cannot be computed in time exp(o(n)).
    • The Tutte polynomial of an n-vertex multigraph cannot be computed in time exp(o(n)) at most evaluation points (x; y) in the case of multigraphs, and it cannot be computed in time exp(o(n/ poly log n)) in the case of simple graphs.
    Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of n-variable 3-CNF formulas cannot be decided in time exp(o(n)). We relax this hypothesis by introducing its counting version #ETH, namely that the satisfying assignments cannot be counted in time exp(o(n)). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for d-CNF formulas to the counting setting.

  29. ACM Transactions on Algorithms, 11(1):4, 2014.
    (with: Martin Grohe)

    Conference version:
    In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), 289-298, 2006.
    (with: Martin Grohe)

    Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence identifying polynomial-time solvable classes of constraint satisfaction problems has received a lot of attention. In this paper, we are interested in structural properties that can make the problem tractable. So far, the largest structural class that is known to be polynomial-time solvable is the class of bounded hypertree width instances introduced by Gottlob et al. Here we identify a new class of polynomial-time solvable instances: those having bounded fractional edge cover number.

    Combining hypertree width and fractional edge cover number, we then introduce the notion of fractional hypertree width. We prove that constraint satisfaction problems with bounded fractional hypertree width can be solved in polynomial time (provided that a the tree decomposition is given in the input). Together with a recent approximation algorithm for finding such decompositions, it follows that bounded fractional hypertree width is now the most general known structural property that guarantees polynomial-time solvability.


  30. ACM Transactions on Algorithms, 11(2):14, 2014.
    (with: Erik Demaine, MohammadTaghi Hajiaghayi)

    Conference version:
    In Proceedings of the 17th European Symposium on Algorithms (ESA 2009), Lecture Notes in Comput. Sci., 5757, Springer, Berlin, 718-729, 2009.
    (with: Erik Demaine, MohammadTaghi Hajiaghayi)

    We study an extensive class of movement minimization problems which arise from many practical scenarios but so far have little theoretical study. In general, these problems involve planning the coordinated motion of a collection of agents (representing robots, people, map labels, network messages, etc.) to achieve a global property in the network while minimizing the maximum or average movement (expended energy). The only previous theoretical results about this class of problems are about approximation, and mainly negative: many movement problems of interest have polynomial inapproximability. Given that the number of mobile agents is typically much smaller than the complexity of the environment, we turn to fixed-parameter tractability. We characterize the boundary between tractable and intractable movement problems in a very general set up: it turns out the complexity of the problem fundamentally depends on the treewidth of the minimal configurations. Thus the complexity of a particular problem can be determined by answering a purely combinatorial question. Using our general tools, we determine the complexity of several concrete problems and fortunately show that many movement problems of interest can be solved efficiently.

  31. SIAM Journal on Discrete Mathematics, 28(1):503-520, 2014
    (with: Paul Wollan)

    We consider the problem of how much edge connectivity is necessary to force a graph G to contain a fixed graph H as an immersion. We show that if the maximum degree in H is Δ, then all the examples of Δ-edge connected graphs which do not contain H as a weak immersion must have a treelike decomposition called a tree-cut decomposition of bounded width. If we consider strong immersions, then it is easy to see that there are arbitrarily highly edge connected graphs which do not contain a fixed clique Kt as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain Kt as a strong immersion.

  32. Algorithmica, 68(1):41-61, 2014
    (with: Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter)

    Conference version:
    37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), 131-142, Lecture Notes in Comput. Sci., 6986, Springer, Berlin, 2011.
    (with: Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter)

    We study a family of problems where the goal is to make a graph Eulerian by a minimum number of deletions. We completely classify the parameterized complexity of various versions: undirected or directed graphs, vertex or edge deletions, with or without the requirement of connectivity, etc. Of particular interest is a randomized FPT algorithm for making an undirected graph Eulerian by deleting the minimum number of edges.

    2013

  33. Journal of the ACM, 60(6):42, 2013.

    Conference version:
    In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), 735-744.

    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. Note that 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 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, unless the Exponential Time Hypothesis fails.

  34. SIAM Journal on Computing, 42(4):1737-1767, 2013.
    (with: Albert Atserias, Martin Grohe)

    Conference version:
    In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), 739-748, 2008.
    (with: Albert Atserias, Martin Grohe)

    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. On the other hand, we show that in the average-case model, every join-project plan can be turned into a plan containing no projections in such a way that the expected time to evaluate the plan increases only by a constant factor independent of the size of the database. Not surprisingly, the key combinatorial parameter in this context is the maximum density of the underlying hypergraph. We show how to make effective use of this parameter to eliminate the projections.

  35. SIAM Journal on Computing, 42(4):1674-1696, 2013.
    (with: Rajesh Chitnis and MohammadTaghi Hajiaghayi)

    Conference version:
    In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 1713-1725, 2012.
    (with: Rajesh Chitnis and MohammadTaghi Hajiaghayi)

    Given a directed graph G, a set of k terminals and an integer p, the DIRECTED VERTEX MULTIWAY CUT problem asks if there is a set S of at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. DIRECTED EDGE MULTIWAY CUT is the analogous problem where S is a set of at most p edges. These two problems indeed are known to be equivalent. A natural generalization of the multiway cut is the multicut problem, in which we want to disconnect only a set of k given pairs instead of all pairs. Marx (Theor. Comp. Sci. 2006) showed that in undirected graphs multiway cut is fixed-parameter tractable (FPT) parameterized by p. Marx and Razgon (STOC 2011) showed that undirected multicut is FPT and directed multicut is W[1]-hard parameterized by $. We complete the picture here by our main result which is that both DIRECTED VERTEX MULTIWAY CUT and DIRECTED EDGE MULTIWAY CUT can be solved in time 22O(p)nO(1), i.e., FPT parameterized by size p of the cutset of the solution. This answers an open question raised by Marx (Theor. Comp. Sci. 2006) and Marx and Razgon (STOC 2011). It follows from our result that DIRECTED MULTICUT is FPT for the case of k=2 terminal pairs, which answers another open problem raised in Marx and Razgon (STOC 2011).

  36. ACM Transactions on Algorithms, 9(4):30, 2013.
    (with: Barry O'Sullivan, Igor Razgon)

    Conference version:
    27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), 561-572, 2010.
    (with: Barry O'Sullivan, Igor Razgon)

    We present a method for reducing the treewidth of a graph while preserving all of its minimal s-t separators up to a certain fixed size k. This technique allows us to solve s-t CUT and MULTICUT problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set or induce a connected graph) in linear time for every fixed number k of removed vertices.

    Our results have applications for problems that are not directly defined by separators, but the known solution methods depend on some variant of separation. For example, we can solve similarly restricted generalizations of BIPARTIZATION (delete at most k vertices from G to make it bipartite) in almost linear time for every fixed number k of removed vertices.These results answer a number of open questions in the area of parameterized complexity. Furthermore, our technique turns out to be relevant for (H,C,k)- and (H,C,≤k)-coloring problems as well, which are cardinality constrained variants of the classical H-coloring problem. We make progress in the classification of the parameterized complexity of these problems by identifying new cases that can be solved in almost linear time for every fixed cardinality bound.


  37. Algorithmica, 65(2):275-316, 2013.
    (with: Ildikó Schlotter)

    We investigate a special case of the INDUCED SUBGRAPH ISOMORPHISM problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-parameter tractability of the problem with non-standard parameterization, where the parameter is the difference |V(G)|-|V(H)|, with G and H being the larger and the smaller input graph, respectively. Intuitively, we can interpret this problem as ``cleaning'' the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We also prove W[1]-hardness for the standard parameterization where the parameter is |V(H)|.

  38. Information and Computation, 222:278-292, 2013.
    (with: Daniel Lokshtanov)

    Conference version:
    38th International Colloquium on Automata, Languages and Programming (ICALP 2011), 785-797, Lecture Notes in Comput. Sci., 6755, Springer, 2011.
    (with: Daniel Lokshtanov)

    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 nO(q), i.e., it is polynomial-time solvable for every fixed q. We study in detail three concrete functions μ (number of nonedges in the cluster, maximum number of non-neighbours a vertex has in the cluster, the number of vertices in the cluster), which correspond to natural clustering problems. For these functions, we show that (μ,p,q)-PARTITION can be solved in time 2O(p) nO(1) and in randomized time 2O(q) nO(1), i.e., the problem is fixed-parameter tractable parameterized by p or by q.

  39. Journal of Computer and System Sciences, 79(1):144-151, 2013.

    Conference version:
    In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, Cambridge, Massachusetts, 181-187, 2010.

    We prove that weighted monotone/antimonotone circuit satisfiability has no fixed-parameter tractable approximation algorithm with any approximation ratio function ρ, unless FPT≠W[1]. In particular, not having such an fpt-approximation algorithm implies that these problems have no polynomial-time approximation algorithms with ratio ρ(OPT) for any nontrivial function ρ.

  40. Journal of Computer and System Sciences, 79(1):39-49, 2013.
    (with: Klaus Jansen, Stefan Kratsch, Ildikó Schlotter)

    Conference version:
    12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), 260-271, Lecture Notes in Comput. Sci., 6139, Springer, Berlin, 2010.
    (with: Klaus Jansen, Stefan Kratsch, Ildikó Schlotter)

    As Bin Packing is NP-hard already for k=2 bins, it is unlikely to be solvable in polynomial time even if the number of bins is a fixed constant. However, if the sizes of the items are polynomially bounded integers, then the problem can be solved in time nO(k) for an input of length n by dynamic programming. We show, by proving the W[1]-hardness of Unary Bin Packing (where the sizes are given in unary encoding), that this running time cannot be improved to f(k) nO(1) for any function f(k) (under standard complexity assumptions). On the other hand, we provide an algorithm for Bin Packing that obtains in time 2O(k log2 k)+O(n) a solution with additive error at most 1, i.e., either finds a packing into~k+1 bins or decides that k bins do not suffice.

  41. Information Processing Letters, 113(22-24):906-912, 2013.
    (with: Sylvain Guillemot)

    Conference version:
    8th International Symposium on Parameterized and Exact Computation (IPEC 2013), 177-188, Lecture Notes in Comput. Sci., vol. 8246, Springer, 2013.
    (with: Sylvain Guillemot)

    The BIPARTITE CONTRACTION problem is to decide, given a graph G and a parameter k, whether we can can obtain a bipartite graph from G by at most k edge contractions. The fixed-parameter tractability of the problem was shown by Heggernes et al., with an algorithm whose running time has double-exponential dependence on k. We present a new randomized FPT algorithm for the problem, which is both conceptually simpler and achieves an improved 2O(k2) running time, i.e., avoiding the double-exponential dependence on k. The algorithm can be derandomized using standard techniques.

    2012

  42. Journal of Artificial Intelligence Research, 45:47-78, 2012.
    (with: David Cohen, Martin Cooper, Páidí Creed, András Z. Salamon)

    The constraint satisfaction problem (CSP) is a general problem central to computer science and artificial intelligence. Although the CSP is NP-hard in general, considerable effort has been spent on identifying tractable subclasses. The main two approaches consider structural properties (restrictions on the hypergraph of constraint scopes) and relational properties (restrictions on the language of constraint relations). Recently, some authors have considered hybrid properties that restrict the constraint hypergraph and the relations simultaneously.

    Our key contribution is the novel concept of a CSP pattern and classes of problems defined by forbidden patterns (which can be viewed as forbidding generic sub-problems). We describe the theoretical framework which can be used to reason about classes of problems defined by forbidden patterns. We show that this framework generalises certain known hybrid tractable classes.

    Although we are not close to obtaining a complete characterisation concerning the tractability of general forbidden patterns, we prove a dichotomy in a special case: classes of problems that arise when we can only forbid binary negative patterns (generic sub-problems in which only disallowed tuples are specified). In this case we show that all (finite sets of) forbidden patterns define either polynomial-time solvable or NP-complete classes of instances.


  43. ACM Transactions on Algorithms, 8(2):19, 2012.
    (with: Andrei Krokhin)

    Conference version:
    35rd International Colloquium on Automata, Languages and Programming (ICALP 2008), 662-673, Lecture Notes in Comput. Sci., 5125, Springer, Berlin, 2008.
    (with: Andrei Krokhin)

    We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, and a solution to it, the question is whether there is a better (lighter, i.e., having strictly less Hamming weight) solution within a given distance from the initial solution. We classify the complexity, both classical and parameterized, of such problems by a Schaefer-style dichotomy result, that is, with a restricted set of allowed types of constraints. Our results show that there is a considerable amount of such problems that are NP-hard, but fixed-parameter tractable when parameterized by the distance.

  44. Journal of Computer and System Sciences, 78(2):638-650, 2012.
    (with: Andrei Bulatov, Víctor Dalmau, Martin Grohe)

    Conference version:
    26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), 231-242, 2009.
    (with: Andrei Bulatov, Víctor Dalmau, Martin Grohe)

    The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.

  45. Algorithmica, 62(3-4):807-822, 2012.
    (with: Ildikó Schlotter)

    Conference version:
    33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), 292-303, Lecture Notes in Comput. Sci., 4769, Springer, Berlin, 2007.
    (with: Ildikó Schlotter)

    In the Planar + k vertex problem the task is to find at most k vertices whose deletion makes the given graph planar. The graphs for which there exists a solution form a minor closed class of graphs, hence by the deep results of Robertson and Seymour, there is an O(n3) time algorithm for every fixed value of k. However, the proof is extremely complicated and the constants hidden by the big-O notation are huge. Here we give a much simpler algorithm for this problem with quadratic running time, by iteratively reducing the input graph and then applying techniques for graphs of bounded treewidth.

    2011

  46. Journal of the ACM, 58(5):21, 2011.
    (with: MohammadHossein Bateni, MohammadTaghi Hajiaghayi)

    Conference version:
    In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), 211-220.
    (with: MohammadHossein Bateni, MohammadTaghi Hajiaghayi)

    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 graph 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.

  47. Bulletin of the EATCS, 84, 41-71, 2011.
    (with: Daniel Lokshtanov and Saket Saurabh)

    In this article we survey algorithmic lower bound results that have been obtained in the field of exact exponential time algorithms and parameterized complexity under certain assumptions on the running time of algorithms solving CNF-SAT, namely Exponential time hypothesis (ETH) and Strong Exponential time hypothesis (SETH).

  48. ACM Transactions on Algorithms, 7(4):43 (2011)
    (with: Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote)

    We study the parameterized complexity of the k-center problem on a given n-pointset P in Rd, with the dimension d as the parameter. We show that the rectilinear 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in O(nlog n) time for any fixed dimension d. On the other hand, we show that this is unlikely to be the case with both the Euclidean and rectilinear k-center problems for any k≥2 and k≥4 respectively. In particular, we prove that deciding whether P can be covered by the union of 2 balls of given radius or by the union of 4 cubes of given side length is W[1]-hard with respect to d, and thus not fixed-parameter tractable unless FPT=W[1]. For the Euclidean case we also show that even an no(d)-time algorithm does not exist, unless there is a 2o(n)-time algorithm for n-variable 3SAT, i.e., the Exponential Time Hypothesis fails.

  49. SIAM J. Discrete Math., 25(2): 631-644, 2011
    (with: Noga Alon)

    We consider the problem of partitioning the vertices of an n-vertex graph with maximum degree d into k classes V1, ..., Vk of size at most n/k in a way that minimizes the number of pairs (i,j) for which there is an edge between Vi and Vj. We show that there is always such a partition with O(k2-2/d) adjacent pairs and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems.

  50. Theor. Comput. Sci., 412(29): 3487-3500, 2011.

    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 Σ2p?-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, one can select a clique coloring from these lists. This problem turns out to be Π3p-complete for every k≥ 2. A graph G is hereditarty k-clique-colorable if every induced subgraph of G is k-clique-colorable. We prove that deciding hereditary k-clique-colorability is also Π3p-complete for every k≥ 3.

  51. J. Artif. Intell. Res. (JAIR),, 41:97-130, 2011
    (with: Emmanuel Hebrard, Barry O'Sullivan, Igor Razgon)

    Conference version:
    15th International Conference on Principles and Practice of Constraint Programming (CP 2009), 424-438, Lecture Notes in Comput. Sci., 5732, Springer, Berlin, 2009.
    (with: Emmanuel Hebrard, Barry O'Sullivan, Igor Razgon)

    Many combinatorial problems encountered in practice involve constraints that require that a set of variables take distinct or equal values.The ALLDIFFERENT constraint, in particular, ensures that all variables take distinct values. Two soft variants of this constraint were proposed in [4], defined either with respect to a so-called variable or graph-based cost function. When requiring similarity, as opposed to diversity, one can consider the dual definition either for the cost or for the basic constraint itself, that is, ALLEQUAL in our case. Six cost functions can be defined by exploring every combinations of these definitions. It is therefore natural to study the complexity of achieving Arc Consistency and Bound Consistency on them. From our earlier work on this topic an open problem remained, namely achieving bounds consistency on the maximisation of the SOFTALLDIFF constraint when considering the graph-based cost.In this paper we resolve this problem. Therefore, we give a complete taxonomy of constraints of equality and difference, based on the alternative objective functions used for the soft variants.

  52. J. Comb. Theory, Ser. B 101(5): 378-381, 2011
    (with: Naonori Kakimura and Ken-ichi Kawarabayashi)

    The well-known theorem of Erdös and Pósa says that a graph G has either k vertex-disjoint cycles or a vertex set X of order at most f(k) such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we generalize Erdös-Pósa's result to cycles that are required to go through a set S of vertices. Given an integer k and a vertex subset S (possibly unbounded number of vertices) in a given graph G, we prove that either G has k vertex-disjoint cycles, each of which contains at least one vertex of S, or G has a vertex set X of order at most f(k) = 40k2 log2k such that G\X has no cycle that intersects S.

  53. Discrete Optimization, 8(1):25-40, 2011.
    (with: Ildikó Schlotter)

    Conference version:
    4nd International Workshop on Parameterized and Exact Computation (IWPEC 2009), 300-311, Lecture Notes in Comput. Sci., 5917, Springer, Berlin, 2009.
    (with: Ildikó Schlotter)

    We study the Hospitals/Residents with Couples problem, a variant of the classical Stable Marriage problem. This is the extension of the Hospitals/Residents problem where residents are allowed to form pairs and submit joint rankings over hospitals. We use the framework of parameterized complexity, considering the number of couples as a param- eter. We also apply a local search approach, and examine the possibili- ties for giving FPT algorithms applicable in this context. Furthermore, we also investigate the matching problem containing couples that is the simplied version of the Hospitals/Residents problem modeling the case when no preferences are given.

  54. Theory of Computing Systems, 48:444-464, 2011.

    Conference version:
    26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), 649-660, 2009.

    The way the graph structure of the constraints influences the complexity of constraint satisfaction problems (CSP) is well understood for bounded-arity constraints. The situation is less clear if there is no bound on the arities. In this case the answer depends also on how the constraints are represented in the input. We study this question for the truth table representation of constraints. We introduce a new hypergraph measure adaptive width and show that CSP with truth tables is polynomial-time solvable if restricted to a class of hypergraphs with bounded adaptive width. Conversely, assuming a conjecture on the complexity of binary CSP, there is no other polynomial-time solvable case.

    2010

  55. Theory of Computing, 6(1):85-112, 2010.

    Conference version:
    In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 169-179, 2007.

    It is well-known that constraint satisfaction problems (CSP) can be solved in time nO(k) if the treewidth of the primal graph of the instance is at most k. 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 time of A is f(G)no(k/log k), 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.

  56. Communications of the ACM, 53(9):99-106, 2010.
    (with: Andrei Bulatov)

    In a constraint satisfaction problem (CSP) the goal is to find an assignment of a given set of variables subject to specified constraints. A global cardinality constraint is an additional requirement that prescribes how many variables must be assigned a certain value. We study the complexity of the problem CCSP(Γ), the CSP with global cardinality constraints that allows only relations from the set Γ. The main result of this paper characterizes sets Γ that give rise to problems solvable in polynomial time, and states that the remaining such problems are NP-complete.

  57. Logical Methods in Computer Science, Vol. 6 (4:4):1-27, 2010.
    (with: Andrei Bulatov)

    Conference version:
    In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science (LICS 2009), 419-428, 2009.
    (with: Andrei Bulatov)

    In a constraint satisfaction problem (CSP) the goal is to find an assignment of a given set of variables subject to specified constraints. A global cardinality constraint is an additional requirement that prescribes how many variables must be assigned a certain value. We study the complexity of the problem CCSP(Γ), the constraint satisfaction problem with global cardinality constraints that allows only relations from the set Γ. The main result of this paper characterizes sets Γ that give rise to problems solvable in polynomial time, and states that the remaining such problems are NP-complete.

  58. ACM Transactions on Algorithms, 6(2), Article 29, 2010.

    Conference version:
    In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 902-911, 2009.

    Fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. Its algorithmic importance comes from the fact that, as shown in previous work, constraint satisfaction problems (CSP) and various problems in database theory are polynomial-time solvable if the input contains a bounded-width fractional hypertree decomposition of the hypergraph of the constraints. In this paper, we show that for every w≥1, there is a polynomial-time algorithm that, given a hypergraph H with fractional hypertree width at most w, computes a fractional hypertree decomposition of width O(w3) for H. This means that polynomial-time algorithms relying on bounded-width fractional hypertree decompositions no longer need to be given a decomposition explicitly in the input, since an appropriate decomposition can be computed in polynomial time. Therefore, if H is a class of hypergraphs with bounded fractional hypertree width, then CSP restricted to instances whose structure is in H is polynomial-time solvable. This makes bounded fractional hypertree width the most general known hypergraph property that makes CSP, Boolean Conjuctive Queries, and Conjunctive Query Containment polynomial-time solvable.

  59. Algorithmica, 58(1), 170-187, 2010.
    (with: Ildikó Schlotter)

    We consider the variant of the classical Stable Marriage problem where preference lists can be incomplete and may contain ties. In such a setting, finding a stable matching of maximum size is NP-hard. We study the parameterized complexity of this problem, where the parameter can be the number of ties, the maximum or the overall length of ties. We also investigate the applicability of a local search algorithm for the problem. Finally, we examine the possibilities for giving an FPT algorithm or an FPT approximation algorithm for finding an egalitarian or a minimum regret matching.

  60. International Journal of Computational Geometry and Applications, 20(2), 147-173, 2010.
    (with: Panos Giannopoulos, Rolf Klein, Christian Knauer, Martin Kutz)

    We prove that computing a geometric minimum-dilation graph on a given set of points in the plane, using not more than a given number of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. We also show that the problem remains NP-hard even when a minimum-dilation tour or path is sought; not even an FPTAS exists in this case.

  61. Algorithmica, 57(4), 747-768, 2010.

    Conference version:
    32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), 37-48, Lecture Notes in Comput. Sci., 4271, Springer, Berlin, 2006.

    It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices. Here we present a uniformly polynomial-time algorithm for the problem: the running time is f(k) nc for some constant c not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O(nk) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices to be deleted is fixed-parameter tractable. This answers an open question of Cai.

    2009

  62. Discrete Applied Mathematics, 157(15):3258-3267, 2009.
    (with: Ildikó Schlotter)

    Conference version:
    34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008), 287-289, Lecture Notes in Comput. Sci., 5344, Springer, Berlin, 2008.
    (with: Ildikó Schlotter)

    We investigate the Induced Subgraph Isomorphism problem with non-standard parametrization, where the parameter is the difference |V(G)| - |V (H)| with H and G being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as "cleaning" the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We show fixed-parameter tractability of the cases where both H and G are planar and H is 3-connected, or H is a tree and G is arbitrary.

  63. Information Processing Letters, 109(20):1161-1166, 2009.
    (with: Igor Razgon)

    Conference version:
    In Proceedings of the 17th European Symposium on Algorithms (ESA 2009), Lecture Notes in Comput. Sci., 5757, Springer, Berlin, 647-658, 2009.
    (with: Igor Razgon)

    The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s1,t1}, ..., {sm,tm}; the task is to remove a minimum set of edges such that si and ti are disconnected for every 1 ≤ im. The parameterized complexity of the problem, parameterized by the maximum number k of edges that are allowed to be removed, is currently open. The main result of the paper is a parameterized 2-approximation algorithm: in time f(k)nO(1), we can either find a solution of size 2k or correctly conclude that there is no solution of size k. The proposed algorithm is based on a transformation of the Edge Multicut problem into a variant of parameterized Max-2-SAT problem, where the parameter is related to the number of clauses that are not satisfied. It follows from previous results that the latter problem can be 2-approximated in a fixed-parameter time; on the other hand, we show here that it is W[1]-hard. Thus the additional contribution of the present paper is introducing the first natural W[1]-hard problem that is constant-ratio fixed-parameter approximable.

  64. Theoretical Computer Science, 410(44):4471-4479, 2009.

    Conference version:
    33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), 656-667, Lecture Notes in Comput. Sci., 4051, Springer, Berlin, 2006.

    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 O(nk) time brute force algorithm for finding a k-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k) nO(1)) running time. The main result is that if the ground set of a represented matroid is partitioned into blocks of size l, then we can determine in f(k,l) nO(1) randomized time whether there is an independent set that is the union of k blocks. As consequence, algorithms with similar running time are obtained for other problems such as finding a k-set in the intersection of l matroids, or finding k terminals in a network such that each of them can be connected simultaneously to the source by l disjoint paths.

  65. Discrete Applied Mathematics, 157(5):1034-1045, 2009.

    In the minimum sum edge coloring problem we have to assign positive integers to the edges of a graph such that adjacent edges receive different integers and the sum of the assigned numbers is minimal. We show that the problem is (a) NP-hard for planar bipartite graphs with maximum degree 3, (b) NP-hard for 3-regular planar graphs, (c) NP-hard for partial 2-trees, and (d) APX-hard for bipartite graphs.

  66. Journal of Combinatorial Theory Ser. B, 99(1):218-228, 2009
    (with: Martin Grohe)

    A bramble in a graph G is a family of connected subgraphs of G such that any two of these subgraphs have a nonempty intersection or are joined by an edge. The order of a bramble is the least number of vertices required to cover every subgraph in the bramble. Seymour and Thomas proved that the maximum order of a bramble in a graph is precisely the tree width of the graph plus one. We prove that every graph of tree width at least k has a bramble of order Ω(k1/2/log2k) and size polynomial in n and k, and that for every k there is a graph G of tree width Ω(k) such that every bramble of G of order k1/2+ε has size exponential in n. To prove the lower bound, we establish a close connection between linear tree width and vertex expansion. For the upper bound, we use the connections between tree width, separators, and concurrent flows.

  67. Discrete Applied Mathematics, 157(1):13-18, 2009
    (with: Marcus Schaefer)

    A coloring of a graph is nonrepetitive if the graph contains no path that has a color pattern of the form xx (where x is a sequence of colors). We show that determining whether a particular coloring of a graph is nonrepetitive is coNP-hard, even if the number of colors is limited to four. The problem becomes fixed-parameter tractable, if we only exclude colorings xx up to a fixed length k of x.

    2008

  68. SIAM Journal on Computing, 38(4):1382-1410, 2008.

    Conference version:
    In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 63-72, 2005.

    We study two pattern matching problems that are motivated by applications in computational biology. In the CLOSEST SUBSTRING problem k strings s1, ..., sk are given, and the task is to find a string s of length L such that each string si has a consecutive substring of length L whose distance is at most d from s. 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) nO(log d) and g(d,k) n^O(loglog 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, 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(loglog k) (modulo some complexity-theoretic assumptions). CONSENSUS PATTERNS is the variant of the problem where, instead of the requirement that each si has a substring that is of distance at most d from s, we have to select the substrings in such a way that the average of these k distances is at most δ. By giving an f(δ)n9 time algorithm, we show that the problem is fixed-parameter tractable.

  69. Theoretical Computer Science, 401:62-76, 2008.

    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 gave a polynomial-time characterization of uniquely 2-list colorable graphs. Answering an open question, we show that uniquely 3-list colorable graphs are unlikely to have such a nice characterization, since recognizing these graphs is Σ2p-complete.

  70. Operations Research Letters, 36(1):31-36, 2008.

    We show that searching the k-change neighborhood is W[1]-hard for metric TSP, which means that finding the best tour in the k-change neighborhood essentially requires complete search (modulo some complexity-theoretic assumptions).

  71. The Computer Journal, 51(1):60-78, 2008.

    Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type, and propose directions for future research.

    2006

  72. Theoretical Computer Science, 361(2-3):133-149, 2006

    Conference version:
    1st Workshop on Approximation and Online Algorithms (WAOA 2003), 214-226, Lecture Notes in Comput. Sci., 2909, Springer, Berlin, 2004.
    [Slides]

    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 vertex 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.

  73. Discrete Applied Mathematics, 154(6):995-1002, 2006

    In the precoloring extension problem we are given a graph with some of the vertices having a preassigned color and it has to be decided whether this coloring can be extended to a proper k-coloring of the graph. Answering an open question of Hujter and Tuza [Combin. Probab. Comput. 5 (1996) 35-56], we show that the precoloring extension problem is NP-complete on unit interval graphs.

  74. Computational Complexity, 14(4):308-340, 2006

    The sum of a coloring is the sum of the colors assigned to the vertices (assuming that the colors are the positive integers). The sum Σ(G) of graph G is the smallest sum that can be achieved by a proper coloring of G. The chromatic strength s(G) of G is the minimum number of colors that is required by a coloring with sum Σ(G). We determine the complexity of the question 'Is s(G)≤k?' for every k: it is coNP-complete for k=2, and Θ2P-complete for k≥3. We also study the complexity of the edge coloring version of the problem, with analogous definitions for the edge sum Σ'(G) and the chromatic edge strength s'(G). We show that for every k≥3, it is Θ2P-complete to decide whether s'(G)≤ k holds. As a first step of the proof, for every r≥ 3, we present graphs with chromatic index r and edge strength r+1. Such graphs were not known before for every r.

  75. Theoretical Computer Science, 351(3):407-424, 2006

    Conference version:
    1st International Workshop on Parameterized and Exact Computation (IWPEC 2004), 83-95, Lecture Notes in Comput. Sci., 3162, Springer, Berlin, 2004.
    [Slides]

    In the precoloring extension problem (PrExt) a graph is given with some of the vertices having a preassigned color 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 these problems are polynomial time solvable but W[1]-hard in chordal graphs. 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 and the coloring of F+ke, F+ve graphs. Answering an open question of Leizhen Cai, we show that coloring chordal+ke graphs is fixed-parameter tractable.

  76. Theoretical Computer Science, 351(3):394-406, 2006

    Conference version:
    1st International Workshop on Parameterized and Exact Computation (IWPEC 2004), 71-82, Lecture Notes in Comput. Sci., 3162, Springer, Berlin, 2004.
    [Slides]

    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 l terminals is separated from the others, (b) each of the given l pairs of terminals are separated, (c) exactly l vertices are cut away from the graph, (d) exactly l connected vertices are cut away from the graph, (e) the graph is separated into l components, We show that if both k and l are parameters, then (a), (b) and (d) are fixed-parameter tractable, while (c) and (e) are W[1]-hard.

    2005

  77. Operations Research Letters, 33(4):382-384, 2005

    In the minimum sum coloring problem we have to assign positive integers to the vertices of a graph in such a way that neighbors receive different numbers and the sum of the numbers is minimized. Szkalicki [SIAM J. Comput., 29(1):274--287, 1999] has shown that minimum sum coloring is NP-hard for interval graphs. Here we present a simpler proof of this result.

  78. Journal of Graph Theory. 49(4):313-324, 2005

    In the edge precoloring extension problem we are given a graph with some of the edges having a preassigned color and it has to be decided whether this coloring can be extended to a proper k-edge-coloring of the graph. In list edge coloring every edge has a list of available colors, and question is whether there is a proper edge coloring where every edge receives a color from its list. We show that both problems are NP-complete on (a) planar, 3-regular bipartite graphs, (b) bipartite outerplanar graphs, and (c) bipartite series-parallel graphs. This improves previous results of Easton and Parker [Discrete Appl. Math.,113(2-3):167-181, 2001], and Fiala [J. Graph Theory, 43(2):156-160, 2003].

  79. Computational Complexity, 14(2):153-183, 2005

    Conference version:
    In Proceedings of 19th Annual IEEE Conference on Computational Complexity, Amherst, Massachusetts, 139-149, 2004.
    [Slides] [Slides of a longer talk]

    We prove a parameterized analog of Schaefer's Dichotomy Theorem: we show that for every finite boolean constraint family F, deciding whether a formula containing constraints from F has a satisfying assignment of weight exactly k is either fixed-parameter tractable (FPT) or W[1]-complete. We give a simple characterization of those constraints that make the problem fixed-parameter tractable. The special cases when the formula is restricted to be bounded occurrence, bounded treewidth or planar are also considered, it turns out that in these cases the problem is in FPT for every constraint family F.

    2004

  80. Periodica Polytechnica Ser. El. Eng. 48(1-2):5-10, 2004.

  81. Discrete Applied Mathematics, 143(1-3):336-341, 2004

    We show that the edge disjoint paths problem is NP-complete in directed or undirected rectangular grids, even if the union of the supply and the demand graph G+H is Eulerian.

  82. Information Processing Letters, 89(2):85-90, 2004.

    Conference version:
    3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Application, Tokyo, 2002, 164-170
    [Slides]

    The list edge multicoloring problem is a version of edge coloring where every edge e has a list of available colors L(e) and an integer demand x(e). For each e, we have to select x(e) colors from L(e) such that adjacent edges receive disjoint sets of colors. Marcotte and Seymour proved a characterization theorem for list edge multicoloring trees, which can be turned into a polynomial time algorithm. We present a slightly more general algorithm that works also on odd cycles. A variant of the method leads to a randomized polynomial time algorithm for handling even cycles as well.

Conference papers without journal versions
2021202020192018201720162015201420132012201120102009200820072006200520042003200220012000
    2021

  1. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2021), 19-29, 2021.

  2. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 95:1-95:20, 2021.
    (with: Govind S. Sankar, Philipp Schepper)

  3. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021), 3:1-3:18, 2021.
    (with: Vincent Cohen-Addad, Philip N. Klein, Archer Wheeler, Christopher Wolfram)

    2020

  4. In Proceedings of Computational Complexity Conference (CCC 2020), 27:1-27:28, 2020.
    (with: Marvin Künneman)

  5. In Proceedings of 28th Annual European Symposium on Algorithms (ESA 2020), 71:1-71:19, 2020.

  6. In Proceedings of 28th Annual European Symposium on Algorithms (ESA 2020), 72:1-72:25, 2020.
    (with: R. B. Sandeep)

  7. In Proceedings of 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 59:1-59:18, 2020. (with: Alexander Gök and Matthias Mnich)

    2019

  8. In Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), 27:1-27:16, 2019.
    (with: Vincent Cohen-Addad, Éric Colin de Verdière , and Arnaud de Mesmay)

  9. In International Conference on Algorithms and Complexity (CIAC 2019), Lecture Notes in Computer Science 11485, 249-261, 2019.
    (with: Alexander Göke and Mathias Mnich)

  10. In Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), 8:1-8:20, 2019.
    (with: Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh)

  11. In Proceedings of 30th International Symposium on Algorithms and Computation (ISAAC 2019), 36:1-36:18, 2019.
    (with: Sándor Kisfaludi-Ba andTom C. van der Zanden)

    2018

  12. In proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018), 474-484, 2018.
    (with: Marcin Pilipczuk and Michal Pilipczuk)

  13. In proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 2801-2820, 2018.
    (with: Lin Chen)

  14. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), 27:1-27:15, 2018.
    (with: László Egri and Pawel Rzazewski)

    2017

  15. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), 210-223, 2017.
    (with:Radu Curticapean, Holger Dell)

  16. In 25th Annual European Symposium on Algorithms (ESA 2017), 59:1-59:15, 2017.
    (with: Marcin Pilipczuk)

  17. 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), 22:1-22:14, 2017.
    (with: Lin Chen, Deshi Ye, and Guochuan Zhang)

    2016

  18. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), 16:1-16:54, 2016.
    (with: Ario Salmasi and Anastasios Sidiropoulos)

  19. 4th Annual European Symposium on Algorithms (ESA 2016), 18:1-18:18, 2016.
    (with: Édouard Bonnet and László Egri)

  20. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), 515-524, 2016.
    (with: Fedor Fomin, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh)

  21. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 27:1-27:14, 2016.
    (with: Andreas Feldmann)

  22. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 28:1-28:15, 2016.
    (with: Valia Mitsou)

  23. 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2016), 233-244, 2016.
    (with: Édouard Bonnet, Nick Brettell, and O-joung Kwon)


  24. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), 570-583, 2016.
    (with: MohammadHossein Bateni, Erik Demaine, and MohammadTaghi Hajiaghayi)

    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(logn (loglogn)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.

    Our second major contribution required for the planar group Steiner tree PTAS is a spanner construction, which reduces the graph to have total weight within a factor of the optimal solution while approximately preserving the optimal solution. This is particularly challenging because group Steiner tree requires deciding which terminal in each group to connect by the tree, making it much harder than recent previous approaches to construct spanners for planar TSP by Klein [SIAM J. Computing 2008], subset TSP by Klein [STOC 2006], Steiner tree by Borradaile, Klein, and Mathieu [ACM Trans. Algorithms 2009], and Steiner forest by Bateni, Hajiaghayi, and Marx [J. ACM 2011] (and its improvement to an efficient PTAS by Eisenstat, Klein, and Mathieu [SODA 2012]. The main conceptual contribution here is realizing that selecting which terminals may be relevant is essentially a complicated prize-collecting process: we have to carefully weigh the cost and benefits of reaching or avoiding certain terminals in the spanner. Via a sequence of involved prize-collecting procedures, we can construct a spanner that reaches a set of terminals that is sufficient for an almost-optimal solution.

    Our PTAS for planar group Steiner tree implies the first PTAS for geometric Euclidean group Steiner tree with obstacles, as well as a (2+)-approximation algorithm for group TSP with obstacles, improving over the best previous constant-factor approximation algorithms. By contrast, we show that planar group Steiner forest, a slight generalization of planar group Steiner tree, is APX-hard on planar graphs of treewidth 3, even if the groups are pairwise disjoint and every group is a vertex or an edge.


  25. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), 1650-1669, 2016.
    (with: Radu Curticapean)

    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 Max Cut and Edge Dominating Set have running time 2O(t)nO(1) when parameterized by treewidth, but nO(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 --- ε)knO(1) time algorithm for any ε > 0 on graphs of treewidth k (but it is known to be solvable in time 2knO(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(nk+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 4k · nO(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 2O(k) · nO(1) time algorithm for the problem on graphs of genus k.


  26. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), 52:1-52:16, 2016.
    (with: Tillmann Miltzow)

    Given a set of n points S in the plane, a triangulation T of S is a maximal set of non-crossing segments with endpoints in S. We present an algorithm that computes the number of triangulations on a given set of n points in time n(11+ o(1)) √n, significantly improving the previous best running time of O(2n n2) by Alvarez and Seidel [SoCG 2013]. Our main tool is identifying separators of size O(√n) of a triangulation in a canonical way. The definition of the separators are based on the decomposition of the triangulation into nested layers ("cactus graphs"). Based on the above algorithm, we develop a simple and formal framework to count other non-crossing straight-line graphs in nO(√n) time. We demonstrate the usefulness of the framework by applying it to counting non-crossing Hamilton cycles, spanning trees, perfect matchings, 3-colorable triangulations, connected graphs, cycle decompositions, quadrangulations, 3-regular graphs, and more.

    2015

  27. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 642-661,2015.
    (with: Paul Wollan)

    We study the following general disjoint paths problem: given a supply graph G, terminals T, a demand graph H on the vertices T, and an integer k, we seek 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. We study the fixed-parameter tractability of this family of problems, parameterized by k, when H is assumed to belong in a fixed hereditary class H. Our main result is a complete characterization of the fixed-parameter tractable cases. We show that if H does not contain every matching and does not contain every skew biclique, then the H-disjoint paths problem is FPT for H in H, and otherwise the problem is W[1]-hard.

  28. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 616-629, 2015.
    (with: Bart M. P. Jansen)

    We study two fundamental problems related to finding subgraphs: given graphs G and H, test whether H is isomorphic to a subgraph of G, or determine the maximum number of vertex-disjoint H-subgraphs that can be packed in G. We investigate these problems when the graph H belongs to a fixed hereditary family F. Our goal is to study which classes F make the two problems tractable in one of the following senses: (a) (randomized) polynomial-time solvable, (b) admits a polynomial (many-one) kernel, or (c) admits a polynomial Turing kernel.

  29. In Proceedings of the 23rd European Symposium on Algorithms (ESA 2015), Lecture Notes in Computer Science Volume 9294, Springer, 865-877, 2015.
    (with: Michal Pilipczuk)

    We study a general family of facility location problems defined on planar graphs and on the 2-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the nO(k) time brute force algorithm of selecting k objects can be improved to nO(√k) time. The algorithm is based on focusing on the Voronoi diagram of a hypothetical solution of k objects; this idea was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. As concrete consequences of our main result, we obtain nO(√k) time algorithms for the following problems: d-SCATTERED SET in planar graphs (find $ vertices at pairwise distance d); d-DOMINATING SET/(k,d)-CENTER in planar graphs (find $ vertices such that every vertex is at distance at most $ from these vertices); select k pairwise disjoint connected vertex sets from a given collection; select k pairwise disjoint disks in the plane (of possibly different radii) from a given collection; cover a set of points in the plane by selecting k disks/axis-parallel squares from a given collection. We complement these positive results with lower bounds suggesting that some similar, but slightly more general problems (such as covering points with axis-parallel rectangles) do not admit nO(√k) time algorithms.

    2014

  30. In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014), 130-139, 2014.
    (with: Radu Curticapean)

    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 vertex-cover 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 k-matchings 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)no(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.

  31. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 82-101, 2014.
    (with: Sylvain Guillemot)

    Given two permutations σ and π, the PERMUTATION PATTERN problem asks if σ is a subpattern of π. We show that the problem can be solved in time 2O(l2 log l) n, where l=|σ| 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 PERMUTATION PATTERN problem in linear time if a bounded-width decomposition is given in the input.

  32. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 1812-1830, 2014.
    (with: Philip N. Klein)

    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 2knO(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 (2O(√k log k+W)nO(1) 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.

  33. Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), 67, 2014.
    (with: Anastasios Sidiropoulos)

    We are studying d-dimensional geometric problems that have algorithms with 1-1/d appearing in the exponent of the running time, for example, in the form of 2n1-1/d or nk1-1/d. This means that these algorithms perform somewhat better in low dimensions, but the running time is almost the same for all large values d of the dimension. Our main result is showing that for some of these problems the dependence on 1-1/d is best possible under a standard complexity assumption. We show that, assuming the Exponential Time Hypothesis,
    • d-dimensional Euclidean TSP on n points cannot be solved in time 2n1-1/d-ε for any ε>0, and
    • the problem of finding a set of k pairwise nonintersecting d-dimensional unit balls/axis parallel unit cubes cannot be solved in time f(k)no(k1-1/d) for any computable function f.
    These lower bounds essentially match the known algorithms for these problems. To obtain these results, we first prove lower bounds on the complexity of Constraint Satisfaction Problems (CSPs) whose constraint graphs are d-dimensional grids. We state the complexity results on CSPs in a way to make them convenient starting points forproblem-specific reductions to particular d-dimensional geometric problems and to be reusable in the future for further results of similar flavor.

  34. In Proceedings of 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 542-553, 2014.
    (with: Michal Pilipczuk)

    Given two graphs H and G, the SIBGRAPH Subgraph Isomorphism problem asks if H is isomorphic to a subgraph of G. While NP-hard in general, algorithms exist for various parameterized versions of the problem. However, the literature contains very little guidance on which combinations of parameters can or cannot be exploited algorithmically. Our goal is to systematically investigate the possible parameterized algorithms that can exist for Subgraph Isomorphism. We develop a framework involving 10 relevant parameters for each of H and G (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time f1(p1,p2,...,pl) nf2(pl+1,...,pk) exists, where each of p1,...,pk is one of the 10 parameters depending only on H or G. We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of G gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when H is a bounded-degree tree of constant pathwidth and G is a planar graph of bounded pathwidth.

    2013

  35. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), 197-206, 2013.
    (with:Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk)

    Full version:
    Technical Report, arXiv:1111.1109

    Given a graph G and k pairs of vertices (s1,t1), ..., (sk,tk), the k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P1, ..., Pk such that Pi goes from si to ti. Schrijver proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time nO(k)

  36. 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Volume 2, 125-136, Lecture Notes in Comput. Sci., 7965, Springer, 2013.
    (with: Hubie Chen)

    We study the complexity of model checking in quantified conjunctive logic, that is, the fragment of first-order logic where both quantifiers maybe used, but conjunction is the only permitted connective. In particular, we study block-sorted queries, which we define to be prenex sentences in multi-sorted relational first-order logic where two variables having the same sort must appear in the same quantifier block. We establish a complexity classification theorem that describes precisely the sets of block-sorted queries of bounded arity on which model checking is fixed-parameter tractable. This theorem strictly generalizes, for the first time, the corresponding classificationfor existential conjunctive logic (which is known and due to Grohe) to a logic in which both quantifiers are present.

    2012

  37. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 68-81, 2012.
    (with: Holger Dell)

    Kernelization algorithms are polynomial-time reductions from a problem to itself that guarantee their output to have a size not exceedingsome bound. For example, d-Set Matching 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(kd) 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 thecomplexity-theoretic hypothesis that coNP is not contained in NP/poly. Under the same hypothesis, we show lower bounds for the kernelizationof d-Set Matching and other packing problems. Our bounds are tight for d-Set Matching: It does not have kernels with O(kd) edges for any ε>0 unless the hypothesis fails. By reduction, this transfers to a bound of O(kd-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 kernelswith O(k2.5) edges for the problem of finding k vertex-disjoint paths of three edges each. This does not quite match the best lowerbound of O(k2-ε) that we can prove. Most of our lower bound proofs follow a general scheme that we discover: To exclude kernels of size O(kd) 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, weapply this scheme to the vertex cover problem, which allows us toreplace the number-theoretical construction by Dell and Van Melkebeek [STOC 2010] with shorter elementary arguments.

  38. 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), 569-580, Lecture Notes in Comput. Sci., 7391, Springer, 2012.
    (with: Philip N. Klein)

    The problem PLANAR k-TERMINAL CUT is as follows: given an undirected planar graph with edge-costs and with k vertices designated as terminals, find a minimum-cost set of edges whose removal pairwise separates the terminals. It was known that the complexity of this problem is O(n2k-4log n). We show that there is a constant c such that the complexity is O(nck). This matches a recent lower bound of Marx showing that the ck term in the exponent is best possible up to the constant c (assuming the Exponential Time Hypothesis).

  39. 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), 677-688, Lecture Notes in Comput. Sci., 7391, Springer, 2012.

    Given a planar graph with k terminal vertices, the PLANAR MULTIWAY CUT problem asks for a minimum set of edges whose removal pairwise separates the terminals from each other. A classical algorithm of Dahlhaus et al. solves the problem in time nO(k), which was very recently improved to 2O(k)nO(√k) time by Klein and Marx. Here we show the optimality of the latter algorithm: assuming the Exponential Time Hypothesis (ETH), there is no f(k)no(√k) time algorithm for PLANAR MULTIWAY CUT. It also follows that the problem is W[1]-hard, answering an open question of Downey and Fellows.

    2011

  40. 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), 5-10, Lecture Notes in Comput. Sci., 6986, Springer, Berlin, 2011.

    The notion of "important separators" and bounding the number of such separators turned out to be a very useful technique in the design of fixed-parameter tractable algorithms for multi(way) cut problems. For example, the recent breakthrough result of Chen et al. on the DIRECTED FEEDBACK VERTEX SET problem can be also explained using this notion. In my talk, I will overview combinatorial and algorithmic results that can be obtained by studying such separators.

  41. 17th International Conference on Principles and Practice of Constraint Programming (CP 2011), 160-171, Lecture Notes in Comput. Sci., 6876, Springer, Berlin, 2011.
    (with: David Cohen, Martin Cooper, Martin Green)

    Much work has been done on describing tractable classes of constraint networks. Most of the known tractable examples are described by either restricting the structure of the networks, or their language. Indeed, for both structural or language restrictions very strong dichotomy results have been proven and in both cases it is likely that all practical examples have already been discovered. As such it is timely to consider tractability which cannot be described by language or structural restrictions. This is the focus of the work here. In this paper we investigate a novel reason for tractability: having at least one variable ordering for which the number of partial solutions to the first n variables is bounded by a polynomial in n. We show that the presence of sufficient functional constraints can guarantee this propertyand we investigate the complexity of finding good variableorderings based on different notions of functionality. What is more we identify a completely novel reason for tractability based on so called Turan sets.

  42. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC 2011), 479-488, 2011.
    (with: Martin Grohe, Ken-ichi Kawarabayashi, and Paul Wollan)

    Full version:
    Technical Report, arXiv:1011.1827

    We show that for every fixed undirected graph H, there is a O(|V(G)|3) time algorithm that tests, given a graph G, 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.

  43. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 1028-1049, 2011.
    (with: MohammadHossein Bateni, Chandra Checkuri, Alina R. Ene, MohammadTaghi Hajiaghayi, Nitish Korula)

    In this paper, we reduce PRIZE-COLLECTING STEINER TSP (PCTSP), PRIZE COLLETING STROLL (PCS), PRIZE-COLLECTING (PCST), PRIZE-COLLETING FOREST (PCSF), and more generally SUBMODULAR PRIZE-COLLECTING STEINER FOREST (SPCSF), on planar graphs (and also on bounded-genus graphs) to the corresponding problem on graphs of bounded treewidth. More precisely, for each of the mentioned problems, an α-approximation algorithm for the problem on graphs of bounded treewidth implies an (α+ε)-approximation algorithm for the problem on planar graphs (and also bounded-genus graphs), for any constant ε>0. PCS, PCTSP, PCST can be solved exactly on graphs of bounded treewidth and hence we obtain a PTAS for these problems on planar graphs and bounded-genus graphs. In contrast, we show that PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. Apart from ruling out a PTAS for PCSF on planar graphs and bounded treewidth graphs, this result is also interesting since it gives the first provable hardness separation between the approximability of a problem and its prize-collecting version. We also show that PCSF is APX-hard on Euclidean instances.

    2010

  44. 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010), 244-255, Lecture Notes in Comput. Sci., 6410, Springer, Berlin, 2010.
    (with: Ildikó Schlotter)

    We study the Arc-Preserving Subsequence (APS) prob- lem with unlimited annotations. Given two arc-annotated sequences P and T, this problem asks if it is possible to delete characters from T to obtain P. Since even the unary version of APS is NP-hard, we used the framework of parameterized complexity, focusing on a parameterization of this problem where the parameter is the number of deletions we can make. We present a linear-time FPT algorithm for a generalization of APS, applying techniques originally designed to give an FPT algorithm for Induced Subgraph Isomorphism on interval graphs.

    2007

  45. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 338-348, 2007.

    We show for several planar and geometric problems that the best knownapproximation schemes are essentially optimal with respect to the dependence on ε. For example, we show that the 2O(1/ε) n time approximation schemes for planar MAXIMUM INDEPENDENT SET and for TSP on a metric defined by a planar graph are essentially optimal: if there is a δ>0 such that any of these problems admits a 2O(1/ε)1-δnO(1) time PTAS, then the Exponential Time Hypothesis (ETH) fails. It is known that MAXIMUM INDEPENDENT SET on unit diskgraphs and the planar logic problems MPSAT, TMIN, TMAX admit nO(1/ε) time approximation schemes. We show that they are optimal in the sense that if there is a δ>0 such that any of these problems admits a 2(1/ε)O(1)nO(1/ε)1-δ time PTAS, then ETH fails.

  46. In A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier, and J. Ramirez Alfonsin, editors, Graph Theory in Paris. Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics, pages 255--270. Birkhäuser, 2007.

    In the precoloring extension problem (PrExt) we are given a graph with some of the vertices having a preassigned color and it has to be decided whether this coloring can be extended to a proper k-coloring of the graph. 1-PrExt is the special case where every color is assigned to at most one vertex in the precoloring. Answering an open question of Hujter and Tuza, we show that the 1-PrExt problem can be solved in polynomial time for chordal graphs.

    2006

  47. 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), 154-165, Lecture Notes in Comput. Sci., 4169, Springer, Berlin, 2006.

    We investigate the parameterized complexity of MAXIMUM INDEPENDENT SET and DOMINATING SET restricted to certain geometric graphs. We show that DOMINATING SET is W[1]-hard for the intersection graphs of unit squares, unit disks, and line segments. For MAXIMUM INDEPENDENT SET, we show that the problem is W[1]-complete for unit segments, but fixed-parameter tractable if the segments are axis-parallel.

    2005

  48. In Proceedings of 13th Annual European Symposium on Algorithms (ESA 2005), Lecture Notes in Comput. Sci., 3669, Springer, Berlin, 448-459, 2005.
    [Slides]

    An EPTAS (efficient PTAS) is an approximation scheme where ε does not appear in the exponent of n, i.e., the running time is f(ε) * nc. We use parameterized complexity to investigate the possibility of improving the known approximation schemes for certain geometric problems to EPTAS. Answering an open question of Alber and Fiala, we show that MAXIMUM INDEPENDENT SET is W[1]-complete for the intersection graphs of unit disks and axis-parallel unit squares in the plane. A standard consequence of this result is that the nO(1/ε) time PTAS of Hunt et al. for MAXIMUM INDEPENDENT SET on unit disk graphs cannot be improved to an EPTAS. Similar results are obtained for the problem of covering points with squares.

    2004

  49. 2nd Workshop on Approximation and Online Algorithms (WAOA 2004), 9-22, Lecture Notes in Comput. Sci., 3351, Springer, Berlin, 2005.
    [Slides]

    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 planar graphs and partial k-trees.

    2002

  50. Mathematical foundations of computer science (MFCS 2002), 532-542, Lecture Notes in Comput. Sci., 2420, Springer, Berlin, 2002.
    [Slides]

    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. [Inform. and Comput., 180(2):113-129, 2003], 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.

    2000

  51. IEEE INFOCOM 2000, 1000-1009.
    (with: Dániel Fogaras)

    An efficient and general graph-theoretic model (the Wavelength-Graph (WG)) has been proposed which enables solving the static Routing and Wavelength Assignment (RWA) problems in Multihop Wavelength Routing (WR) Wavelength Division Multiplexing (WDM) Networks simultaneously, and - as a unique feature - it optimises the optical layer jointly with electrical one. Based on the proposed WG model the problem has been formulated as an Integer Linear Program (ILP), solved by stochastic algorithms improved by simple heuristics.
    The topology of the physical layer, the type of each node (e.g., OADM, OXC or EXC), the number of available wavelengths per link and the capacity of each wavelength-channel are assumed given with the aggregated traffic demand of each node-pair. The output of the optimisation is the system of wavelengthpaths, lightpaths and semi-lightpaths.
    The objective of the optimisation is to reduce resource usage at upper (electrical) layers, subject to constrained amount of capacity of each wavelength and limited number of wavelengths. Although the problem to be solved is NP-hard, all methods proposed give results in very short time.

Papers appearing in edited volumes
    2020

  1. In Fomin, F.V., et al. (eds.) Treewidth, Kernels, and Algorithms. Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Lecture Notes in Comput. Sci., vol 12160, pp. 129-144, Springer, 2020.

    2012

  2. In Bodlaender, H.L., et al. (eds.) Fellows Festschrift. Lecture Notes in Comput. Sci., vol. 7370, pp. 457-468, Springer, 2012.
    (with:Fedor V. Fomin)

    We give an update on the status of open problems from the book "Parameterized Complexity" by Downey and Fellows.

  3. In Bodlaender, H.L., et al. (eds.) Fellows Festschrift. Lecture Notes in Comput. Sci., vol. 7370, pp. 469-496, Springer, 2012.

    The progress in parameterized complexity has been very significant in recent years, with new research questions and directions, such as kernelization lower bounds, appearing and receiving considerable attention. This speculative article tries to identify new directions that might become similar hot topics in the future. First, we point out that the search for optimality in parameterized complexity already has good foundations, but lots of interesting work can be still done in this area. The systematic study of kernelization became a very successful research direction in recent years. We look at what general conclusions one can draw from these results and we argue that the systematic study of other algorithmic techniques should be modeled after the study of kernelization. In particular, we set up a framework for understanding which problems can be solved by branching algorithms. Finally, we discuss that the domain of directed graph problems is a challenging area which can potentially see significant progress in the following years.

Volume editing
    2012

  1. Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx (eds.) Lecture Notes in Comput. Sci., vol. 7370, Springer, 2012.

  2. Dániel Marx and Peter Rossmanith (eds.) Lecture Notes in Comput. Sci., vol. 7112, Springer, 2012.

Manuscripts
  1. Manuscript, 2003.

    Coloring circular arcs was shown to be NP-complete by Garey, Johnson, Miller and Papadimitriou [SIAM J. Algebraic Discrete Methods, 1(2):216--227, 1980]. Here we present a simpler proof of this result.

  2. Parameterized Complexity Newletter, pages 7-8, Vol. 3, 2007.
Thesis
  1. PhD thesis, 2004.

Back to homepage