Lukasz Kowalik


Main menu: Home | Papers | Teaching | Projects |

Research papers

See elsewhere

[dblp] | [Google scholar] | [University portal]

Jump to area

Exponential-time and parameterized algorithms | Approximation algorithms | Planar graphs | Other areas

Exponential-time and parameterized algorithms

  1. The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth, Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge and Piotr Wygocki
    Proc. 15th International Symposium on Parameterized and Exact Computation, IPEC 2020,
    [DOI] [benchmark instances repository]
  2. The Asymmetric Travelling Salesman Problem in Sparse Digraphs, Lukasz Kowalik, Konrad Majewski
    Proc. 15th International Symposium on Parameterized and Exact Computation, IPEC 2020,
    [DOI] [arXiv]
  3. Many visits TSP revisited, Lukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström.
    Proc. 28th Annual European Symposium on Algorithms (ESA 2020),
    [DOI] [arXiv]
  4. Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP, Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen and Lukasz Kowalik.
    Proc. 27th Annual European Symposium on Algorithms (ESA 2019)
    [DOI] [arXiv]
  5. Tight Lower Bounds for List Edge Coloring, Lukasz Kowalik, Arkadiusz Socala.
    Proc. 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'18)
    [arXiv] [DOI] [slides]
  6. On Directed Feedback Vertex Set parameterized by treewidth, Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna.
    Proc. 44th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), LNCS 11159, Springer, pp. 65-78.
    [arXiv] [DOI]
  7. Improving TSP tours using dynamic programming over tree decomposition, with Marek Cygan and Arkadiusz Socala.
    ACM Transactions on Algorithms, vol. 15(4), pp. 54:1--54:19, 2019.
    [arXiv] [DOI]
    Conference version: Proc. 25th Annual European Symposium on Algorithms (ESA 2017). Best paper award.
    [DOI] [slides]
  8. Tight lower bounds for the complexity of multicoloring, with Marthe Bonamy, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna
    ACM Transactions on Computation Theory, 11 (2019), pp. 13:1-13:19
    [DOI] [arXiv]
    Conference version: Proc. 25th Annual European Symposium on Algorithms (ESA 2017).
  9. Approximation and Parameterized Complexity of Minimax Approval Voting, with Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
    Journal of Artificial Intelligence Research, 63 (2018) 495-513
    [DOI] [arXiv]
    Conference version: Proc. 31st AAAI Conference on Artificial Intelligence (AAAI'17), pp. 459--465, AAAI Press, 2017.
  10. On the fine-grained complexity of rainbow coloring, with Juho Lauri and Arkadiusz Socala
    SIAM J. Discrete Math, 32(3), 1672-1705 (2018)
    [arXiv] [DOI]
    Conference version: Proc. 24th Annual European Symposium on Algorithms (ESA 2016)
  11. On finding rainbow and colorful paths, with Juho Lauri
    Theor. Comput. Sci. 628: 110-114 (2016)
    [Publisher's version]
  12. Linear kernels for outbranching problems in sparse digraphs, with Marthe Bonamy, Michal Pilipczuk and Arkadiusz Socala
    Algorithmica 79(1): 159-188 (2017).
    [arXiv] [BibTeX entry] [DOI]
    Conference version: Proc IPEC'15, LNCS vol 9134, pp. 199-211, 2015.
    [BibTeX entry] [DOI]
  13. Spotting Trees with Few Leaves, with Andreas Björklund, Vikram Kamat and Meirav Zehavi
    SIAM Journal on Discrete Mathematics, 2017, Vol. 31, No. 2 : pp. 687-713.
    [DOI] [arXiv] [talk]
    Conference version: Proc. ICALP 2015, pp. 243-255.
    [BibTeX entry] [DOI] [slides]
  14. Constrained Multilinear Detection and Generalized Graph Motifs, with Andreas Björklund, Petteri Kaski
    Algorithmica 74(2): 947-967 (2016)
    (Extended, generalized version of our STACS 2013 paper)
    [PDF] [Publisher's version]
  15. Engineering Motif Search for Large Graphs, with Andreas Björklund, Petteri Kaski, Juho Lauri
    Proc. 17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015, SIAM, 2015, pp. 104-118.
    [PDF] [Publisher's version]
  16. A 13k-kernel for Planar Feedback Vertex Set via Region Decomposition, with Marthe Bonamy
    Theor. Comput. Sci. 645: 25-40 (2016)
    [arXiv] [DOI]
    Conference version: A 14k-kernel for Planar Feedback Vertex Set via Region Decomposition Proc. 9th International Symposium on Parameterized and Exact Computation, IPEC'14, LNCS vol 8894, Springer, 97-109, 2014.
  17. Fast Witness Extraction Using a Decision Oracle, with Andreas Björklund and Petteri Kaski
    Proc. 22th Annual European Symposium on Algorithms (ESA 2014), LNCS 8737, 2014, pp. 149-160.
    [Publisher's version] [BibTeX entry] [slides]
  18. Assigning channels via the meet-in-the-middle approach, with Arkadiusz Socala,
    Algorithmica 74(4): 1435-1452 (2016) (open access).
    [arXiv] [PDF] [DOI]
    Conference version: Proc. 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), LNCS 8503, 2014, pp. 282-293.
    [Publisher's version]

    Abstract: We study the complexity of the CHANNEL ASSIGNMENT problem. By applying the meet-in-the-middle approach we get an algorithm for the $\ell$-bounded CHANNEL ASSIGNMENT (when the edge weights are bounded by $\ell$) running in time $O^*((2\sqrt{\ell+1})^n)$. This is the first algorithm which breaks the $(O(\ell))^n$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. A major open problem asks whether CHANNEL ASSIGNMENT admits a $O(c^n)$-time algorithm, for a constant $c$ independent of $\ell$. We consider a similar question for GENERALIZED T-COLORING, a CSP problem that generalizes CHANNEL ASSIGNMENT. We show that GENERALIZED T-COLORING does not admit a $2^{2^{o\left(\sqrt{n}\right)}} {\rm poly}(r)$-time algorithm, where $r$ is the size of the instance.

  19. Counting thin subgraphs via packings faster than meet-in-the-middle time, with Andreas Björklund and Petteri Kaski,
    ACM Trans. Algorithms. 13(4): 48:1-48:26 (2017)
    [arXiv] [DOI]
    Conference version: ACM-SIAM Symposium on Discrete Algorithms (SODA 2014),

    Abstract: Vassilevska and Williams (STOC 2009) showed how to count simple paths on $k$ vertices and matchings on $k/2$ edges in an $n$-vertex graph in time $n^{k/2+O(1)}$. In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Bj\"orklund \emph{et al.} (ESA 2009), via $n^{st/2+O(1)}$-time algorithms for counting $t$-tuples of pairwise disjoint sets drawn from a given family of $s$-sized subsets of an $n$-element universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have $\Omega(n^{\lfloor st/2\rfloor})$ and $\Omega(n^{\lfloor k/2\rfloor})$ lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the "meet-in-the-middle" exponent $st/2$ can be beaten and give an algorithm that counts in time $n^{0.4547 st + O(1)}$ for $t$ a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on $k$ vertices and pathwidth $p\ll k$ in an $n$-vertex graph in $n^{0.4547 k+2p+O(1)}$ time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound.

  20. Probably Optimal Graph Motifs, with Andreas Björklund and Petteri Kaski
    Proc. 30th Symposium on Theoretical Aspects of Computer Science (STACS 2013),
    LIPIcs, 20-31, 2013.
    [arXiv] [Publisher's version] [BibTeX entry] [slides]
  21. Nonblocker in H-minor free graphs: kernelization meets discharging
    Proc. 7th International Symposium on Parameterized and Exact Computation (IPEC 2012),
    LNCS 7535, 61-72, 2012.
    [arXiv] [Publisher's version] [slides]
  22. A 9k kernel for nonseparating independent set in planar graphs, with Marcin Mucha
    Theoretical Computer Science, Vol. 516, 2013, 86-95. .
    Conference version: Proc. 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2012), LNCS 7551, 160-171, 2012.
    [arXiv] [Publisher's version] [slides]
  23. Towards optimal kernel for connected vertex cover in planar graphs with Marcin Pilipczuk and Karol Suchan.
    Discr. Appl. Math., Vol. 161, 1154-1161, 2013.
    [arXiv] [Publisher's version]
  24. Channel Assignment via Fast Zeta Transform, with Marek Cygan
    Information Processing Letters, Vol. 111, No. 15, 2011, 727-730.
    [arXiv] [Publisher's version]

    Abstract: We show an O*((l+1)^n)-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous O*((l+2)^n)-time algorithm by Kral, as well as algorithms for important special cases, like L(2,1)-labelling. For the latter problem, our algorithm works in O*(3^n) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle.

  25. Improved induced matchings in sparse graphs, with and Rok Erman, Matjaz Krnc, Tomasz Walen
    Discr. Appl. Math., Vol. 158, No. 18, pp 1994-2003, 2010.
    [PDF] [Publisher's version]

    Abstract: An induced matching in graph G is a matching which is an induced subgraph of G. Clearly, among two vertices with the same neighborhood (called twins) at most one is matched in any induced matching, and if one of them is matched then there is another matching of the same size that matches the other vertex. Motivated by this, Kanj, Pelsmajer, Schaefer and Xia [STACS'08] studied induced matchings in twinless graphs. They showed that any twinless planar graph contains an induced matching of size at least n/40 and that there are twinless planar graphs that do not contain an induced matching of size greater than n/27+O(1). We improve both these bounds to n/28+O(1), which is tight up to an additive constant. This implies that the problem of deciding an whether a planar graph has an induced matching of size k has a kernel of size at most 28k. We also show for the first time that this problem is FPT for graphs of bounded arboricity.
    Kanj et al. presented also an algorithm which decides in O(2159√k+n)-time whether an n-vertex planar graph contains an induced matching of size k. Our results improve the time complexity analysis of their algorithm. However, we show also a more efficient, O(225.5√k+n)-time algorithm. Its main ingredient is a new, O*(4w)-time algorithm for finding a maximum induced matching in a graph of branch-width at most w.

    Conference version: Proc. 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009), LNCS 5917, 134-138, 2009.
  26. Exponential-Time Approximation of Weighted Set Cover with Marek Cygan and Mateusz Wykurz
    Information Processing Letters Vol. 109, 2009, 957-961.
    [PDF] [Publisher's version]
    Abstract: The Set Cover problem belongs to a group of hard problems which are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. In recent years, many researchers design exact exponential-time algorithms for problems of that kind. The goal is getting the time complexity still of order O(cn), but with the constant c as small as possible. In this work we extend this line of research and we investigate whether the constant c can be made even smaller when one allows constant factor approximation.
    In fact, we describe a kind of approximation schemes --- trade-offs between approximation factor and the time complexity. We use general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate r, one can transform any O*(cn)-time algorithm for Set Cover into a (1+ln(r))-approximation algorithm running in time O*(cn/r). We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems.

    The above paper contains selected results from the earlier technical report:
    Exponential-Time Approximation of Hard Problems, with Marek Cygan, Marcin Pilipczuk and Mateusz Wykurz
    [arXiv] [slides]
  27. Improved Edge Coloring with Three Colors
    Theoretical Computer Science, Vol. 410, No. 38-40, 2009, 3733-3742.
    [BibTeX entry] [PDF] [Publisher's version]
    Conference version: Proc. 32nd Int. Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2006) , LNCS 4271, 2006, 90-101.
    [BibTeX entry] [Publisher's version] [slides]
    Abstract: We show an O(1.344n)=O(20.427 n) algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous, O(2n/2) algorithm of Beigel and Eppstein [J. Alg., 2005]. We apply a very natural approach of generating inclusion-maximal matchings of the graph. The time complexity of our algorithm is estimated using the "measure and conquer" technique.

    Software: File [quasi-convex.cpp] contains the program used to find optimal values of parameters in measure-and-conquer time complexity proof of the 3-edge-coloring algorithm from the paper. It is a C++ implementation of the quasi-convex programming algorithm from the paper D. Eppstein "Quasiconvex Analysis of Backtracking Algorithms", Proc. SODA'04, pages 781-790, 2004.

Approximation algorithms

  1. Beyond the Shannon's Bound, with Michał Farnik and Arkadiusz Socała
  2. Beyond the Vizing's bound for at most seven colors, with Marcin Kamiński
    SIAM J. Discrete Math., vol. 28, no. 3, 2014, 1334-1362.
    [arXiv] [Publisher's version]
  3. Approximating the maximum 3- and 4-edge-colorable subgraph, with Marcin Kamiński,
    Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), LNCS 6139, 2010, pp. 395-407.
    [BiBTeX entry] [Electronic version] [slides]
  4. Fast Approximation in Subspaces by Doubling Metric Decomposition, with Marek Cygan, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski,
    Proc. 18th Annual European Symposium on Algorithms (ESA 2010), LNCS 6346, 2010, pp. 72-83.
    [arXiv] [Electronic version]
  5. Two approximation algorithms for ATSP with strengthened triangle inequality, with Marcin Mucha,
    Proc. 11th International Workshop on Algorithms and Data Structures (WADS 2009), LNCS 5664, 2009, pp. 471-482.
    [PDF] [BibTeX entry] [Publisher's version]
    Abstract: We study the asymmetric travelling salesman problem (ATSP) with strengthened triangle inequality, i.e. for some γ∈ [0.5,1) the edge weights satisfy w(u,v) ≤ γ (w(u,x) + w(x,v)) for all distinct vertices u,v,x.

    We present two approximation algorithms for this problem. The first one is very simple and has approximation ratio 1/[2(1-γ)], which is better than all previous results for all γ ∈ (0.5,1). The second algorithm is more involved but it also gives a much better approximation ratio: (2-γ)/[3(1-γ)]+O(n-1) when γ > γ0, and ½(1+γ)2 + ε for any ε>0 when γ ≤ γ0, where γ0 ≈ 0.7003.
  6. Deterministic 7/8-approximation for the Metric Maximum TSP, with Marcin Mucha
    Theoretical Computer Science, Vol. 410, 2009, 5000-5009.
    [BibTeX entry] [PDF] [Electronic version]
    Conference version: Proc. APPROX-RANDOM 2008, LNCS 5171, 2008, pp. 132-145.
    [Electronic version]
    Abstract: We present the first 7/8-approximation algorithm for the maximum traveling salesman problem with triangle inequality. Our algorithm is deterministic. This improves over both the randomized algorithm of Hassin and Rubinstein [IPL, 2002] with expected approximation ratio of (7/8-O(n-1/2) and the deterministic (7/8-O(n-1/3)) -approximation algorithm of Chen and Nagoya [ESA, 2005].
    In the new algorithm, we extend the approach of processing local configurations using so-called loose-ends, which we introduced in [WADS, 2007].
  7. 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality, with Marcin Mucha,
    Full version: Algorithmica, Volume 59, No. 2, 2011, pp 240-255.
    [PDF] [Publisher's version]
    Conference version: Proc. 10th International Workshop on Algorithms and Data Structures (WADS 2007), LNCS 4619, 2007, pp. 589-600.
    [BibTeX entry] [PS] [PDF] [Publisher's version]
    Abstract: We describe a new approximation algorithm for the asymmetric maximum traveling salesman problem (ATSP) with triangle inequality. Our algorithm achieves approximation factor 35/44 which improves on the previous 31/40 factor of Blaeser, Ram and Sviridenko [WADS, 2005].
  8. Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
    Proc. 17th International Symposium on Algorithms and Computation (ISAAC 2006), LNCS 4288, 2006, 557-566.
    [BibTeX entry] [PS] [PDF] [Publisher's version] [slides]
    Abstract: We deal with the problem of finding such an orientation of a given graph that the largest number of edges leaving a vertex (called the outdegree of the orientation) is small.
    For any ε∈(0,1) we show an O˜(|E(G)|/ε)- time algorithm which finds an orientation of an input graph G with outdegree at most ⌈(1+ε)d*⌉, where d* is the maximum density of a subgraph of G. It is known that the optimal value of orientation outdegree is ⌈ d* ⌉.
    Our algorithm has applications in constructing labeling schemes, introduced by Kannan et al. and in approximating such graph density measures as arboricity, pseudoarboricity and maximum density.

Planar graphs: algorithms and properties

  1. A Planar Linear Arboricity Conjecture, with Marek Cygan, Jian-Feng Hou, Borut Luzar and Jian-Liang Wu.
    J. Graph Theory, vol. 69, no. 4, 2012, pp. 403-425.
    [Publisher's version]
    Abstract: The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. In 1984, Akiyama et al. stated the Linear Arboricity Conjecture (LAC), that the linear arboricity of any simple graph of maximum degree Δ is either ⌈Δ/2⌉ or ⌈(Δ+1)/2⌉. J. L. Wu. and Y. W. Wu. proved that LAC holds for all planar graphs.
    LAC implies that for Δ odd, la(G)=⌈Δ/2⌉. We conjecture that for planar graphs this equality is true also for any even Δ ≥ 6. (There are examples of graphs with maximum degree 2 and 4 where la(G)>⌈Δ/2⌉.) In this paper we show that it is true for any even Δ ≥ 10, leaving open only the cases Δ=6, 8.
    We present also an O(n log n)-time algorithm for partitioning a planar graph into max{la(G),5} linear forests, which is optimal when Δ ≥ 9.

    Conference version (authors: Marek Cygan, Lukasz Kowalik, Borut Luzar): Proc. 7th International Conference on Algorithms and Complexity (CIAC 2010), LNCS 6078, 2010, pp. 204-216.
    arXiv:0912.5528, 2009.
    [PDF] [Publisher's version]
  2. An improved bound on the largest induced forests for triangle-free planar graphs, with Borut Luzar and Riste Skrekovski
    Discrete Mathematics & Theoretical Computer Science Vol. 12, No. 1, 87-100, 2010.
    [PDF] [BibTeX entry] [Publisher's version]
    Abstract: In 1979 Alberson and Berman raised a conjecture that every n-vertex planar graph has an induced forest of size at least n/2. Clearly, restricting the girth (the length of the shortest cycle) of the graph should result in bigger induced forests. In 1987 Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest of size ≥5/8n. The tight example is the cube Q3 and it seems that this bound can hold even for all planar graph of girth at least 4. Motivated by this, Salavatipour showed that every planar graph of girth at least 4 contains an induced forest of size at least 17/32n + O(1).
    We improve the bound of Salavatipour to 71/128n + O(1). We also pose some questions regarding planar graphs of higher girth.
  3. Total colouring of plane graphs with maximum degree nine, with Jean-Sebastien Sereni and Riste Skrekovski,
    SIAM J. Discrete Math., Vol. 22, No. 4, 2008, 1462--1479.
    [BibTeX entry] [PDF] [Publisher's version]
    Abstract: The central problem of the total-colourings is the Total-Colouring Conjecture, which asserts that every graph of maximum degree Δ admits a (Δ + 2)-total-colouring. Similarly to edge-colourings --- with Vizing's edge-colouring conjecture --- this bound can be decreased by 1 for plane graphs of higher maximum degree. More precisely, it is known that if Δ ≥ 10 then every plane graph of maximum degree Δ is (Δ + 1)-totally-colourable. On the other hand, such a statement does not hold if Δ ≤ 3. We prove that every plane graph of maximum degree 9 can be 10-totally-coloured.
  4. New Linear-Time Algortihms for Edge-Coloring Planar Graphs, with Richard Cole
    Algorithmica, Vol. 50, No. 3, 2008, 351--368 .
    [BibTeX entry] [PS] [PDF] [Publisher's version]
    Abstract: We show efficient algorithms for edge-coloring planar graphs. Our main result is a linear-time algorithm for coloring planar graphs with maximum degree Δ with max{Δ, 9} colors. Thus the coloring is optimal for graphs with maximum degree Δ ≥ 9. Moreover for Δ=4,5,6 we give linear-time algorithms that use Δ+2 colors. These results improve over the algorithms of Chrobak and Yung [J. Alg., 1989] and of Chrobak and Nishizeki [J. Alg., 1990] which color planar graphs using max{Δ, 19} colors in linear time or using max{Δ, 9} colors in O(n log n) time.
  5. A Generalization of Kotzig's Theorem and its Application, with Richard Cole, Riste Skrekovski,
    SIAM J. Discrete Math., Vol. 21, No. 1, 2007, 93--106.
    [BibTeX entry] [PS] [PDF] [Publisher's version]
    Abstract: An edge of a graph is light when the sum of the degrees of its endvertices is at most 13. The well-known Kotzig Theorem states that every 3-connected planar graph contains a light edge. Later, Borodin extended this result to the class of planar graphs of minimum degree at least 3.
    We deal with generalizations of these results for planar graphs of minimum degree 2. Borodin, Kostochka and Woodall [JCTB, 1997] showed that each such graph contains a light edge or a member of two infinite sets of configurations, called 2-alternating cycles and 3-alternators. This implies that planar graphs with maximum degree Δ ≥ 12 are Δ-edge-choosable. We prove a similar result with 2-alternating cycles and 3-alternators replaced by five fixed bounded-sized configurations called crowns. This gives another proof of Δ-edge-choosability of planar graphs with Δ ≥ 12. However, we show efficient choosability, i.e. we describe a linear-time algorithm for max{Δ, 12}-edge-list-coloring planar graphs. This extends the result of Chrobak and Yung [J. Alg., 1989].
  6. Oracles for Bounded Length Shortest Paths in Planar Graphs, with Maciej Kurowski
    ACM Transactions on Algorithms, Vol. 2, No. 3, 2006, 335-363.
    [BibTeX entry] [PS] [PDF] [Publisher's version]
    Abstract: We present a new approach for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G=(V,E) one can build in O(|V|) time a data structure, which allows to check in O(1) time whether two given vertices are at distance at most k in G and if so a shortest path between them is returned. Graph G may be undirected as well as directed.
    Our data structure works in fully dynamic environment. It can be updated in O(1) time after removing an edge or a vertex while updating after an edge insertion takes polylogarithmic amortized time.
    Our results can be easily generalized to other wide classes of graphs -- for instance we can take any minor-closed family of graphs.
  7. Fast 3-Coloring Triangle-Free Planar Graphs,
    Algorithmica, Vol. 58, No. 3, 2010, 770-789.
    [PDF] [Publisher's version]
    Conference version: Proc. 12th Annual European Symposium on Algorithms (ESA 2004), LNCS 3221, 2004, 436-447.
    [BibTeX entry] [Publisher's version]
    Abstract: Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch's theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n^2) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is O(n log n).

    Note: In 2009, Dvorak, Kawarabayashi and Thomas showed a linear-time algorithm (see here).

  8. More on Light Graphs in 3-Connected Plane Graphs Without Triangular or Quadrangular Faces,
    Technical Report no. 275, Institute of Informatics, Warsaw University, 2004.
    [BibTeX entry] [PS] [PDF]
    Abstract: Intuitively, a graph H is light in a class Q of graphs when H is a subgraph of some member of Q and for every G ∈ Q if G contains H as a subgraph, there is also an occurence H' of H in G such that the degrees of vertices of H' in G are bounded by some constant. Characterizing light graphs in various subclasses of plane graphs attracted many researchers in recent years. We focus on the class P(3,5) of 3-connected plane graphs with faces of length at least 5. The class was previously studied by S. Jendrol' and P. J. Owens who showed that every k-cycle, k > 5 and k ≠ 14, is not light in P(3,5). They also proved that every block of any light graph in P(3,5) has at most 18 vertices.
    In this paper we show that every block of a light graph in P(3,5) is a bridge, a cycle C5 or a cycle C14. Very recently, T. Madaras showed that K1,3 is light in P(3,5). This is an immediate corollary from more general result stating that in every planar graph with faces of length ≥5 and vertices of degree ≥3 there exists a vertex of degree at most 3 with neighbors a,b,c such that deg(a)=deg(b)=3 and deg(c) ≤ 4. We give a new, much shorter proof of the latter result.
  9. Short Cycles in Planar Graphs,
    Proc. 29th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2003), LNCS 2880, 2003, 284-296.
    [BibTeX entry] [PS] [PDF] [Publisher's version]
    Abstract: We present new algorithms for finding short cycles (of length at most 6) in planar graphs. Although there is an O(n)-time algorithm for finding any fixed subgraph H in a given n-vertex planar graph (Eppstein, JGAA, 1999), the multiplication constant hidden in "O" notation (which depends on the size of H) is so high, that it rather cannot be used in practice even when |V(H)| = 4. Our approach gives faster "practical algorithms", still of linear time complexity, which are additionally much easier to implement.
    As a side-effect of our approach we show that the maximum number of k-cycles in n-vertex planar graph is Θ(n⌊k/2⌋).
  10. Short Path Queries in Planar Graphs in Constant Time, with M.Kurowski,
    Proc. 35th Symp. Theory of Computing (STOC 2003), 2003, 143-148.
    [BibTeX entry] [PS] [PDF] [Publisher's version]
    Note: This is a preliminary, conference version of the paper "Oracles for Bounded Length Shortest Paths in Planar Graphs", TALG 2006.
    Abstract: We present a new algorithm for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G=(V,E) one can build in O(|V|) time a data structure, which allows to check in O(1) time whether two given vertices are distant by at most k in G and if so a shortest path between them is returned.
  11. A New 3-Color Criterion For Planar Graphs, with K. Diks and M. Kurowski,
    Proc. 28th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2002), LNCS 2573, 2002, 138-149.
    [BibTeX entry] [PS] [PDF] [Publisher's version]
    Abstract: We present a new general 3-color criterion for planar graphs. This criterion easily implies several known sufficent 3-colorability conditions, as well as some new consequences, namely:
    • A near-traingulation (plane graph with at most one non-triangular face) is 3-colorable iff every vertex not incident with the non-triangular face has even degree.
    • A sufficient and necessary 3-colorability condition for triangulations with holes (plane graphs such that each vertex is incident with at most one non-triangular face). Such a graph is 3-colorable iff
      1. every vertex not incident with the non-triangular face has even degree.
      2. for each non-triangular face f, when we paint the edges incident with f in black and white so that the color changes only in odd-degree vertices, then the numbers of black and white edges are congruent modulo 3.

Other areas

  1. Adjacency Queries in Dynamic Sparse Graphs
    Information Processing Letters, Vol. 102, No. 5, 2007, 191--195
    [BibTeX entry] [PS] [PDF] [Publisher's version]
    Abstract: We deal with the problem of maintaining a dynamic graph so that queries of the form is there an edge between u and v? are processed fast.
    We consider graphs of bounded arboricity, i.e., graphs with no dense subgraphs, like for example planar graphs. Brodal and Fagerberg [WADS'99] described a very simple linear-size data structure which processes queries in constant worst-case time and performs insertions and deletions in O(1) and O(log n) amortized time, respectively. We show a complementary result that their data structure can be used to get O(log n) worst-case time for query, O(1) amortized time for insertions and O(1) worst-case time for deletions. Moreover, our analysis shows that by combining the data structure of Brodal and Fagerberg with efficient dictionaries one gets O(logloglog n) worst-case time bound for queries and deletions and O(logloglog n) amortized time for insertions, with size of the data structure still linear. This last result holds even for graphs of arboricity bounded by O(logkn), for any constant k.
  2. A Note on Scheduling Equal-Length Jobs to Maximize Throughput, with M. Chrobak, C. Durr, W. Jawor, M. Kurowski
    Short version: Journal on Scheduling, Vol. 9, No. 1, 2006, 71-73.
    [BibTeX entry] [Publisher's version]
    Extended version: e-Print archive, cs.DS/0410046, 2004.
    [BibTeX entry] [PS] [PDF]
    Abstract: We study the problem of scheduling equal-length jobs with release times and deadlines, where the objective is to maximize the number of completed jobs. Preemptions are not allowed. In Graham's notation, the problem is described as 1|rj; pj = p|ΣUj. We give the following results: (1) We show that the often cited algorithm by Carlier from 1981 is not correct. (2) We give an algorithm for this problem with running time O(n5).

PhD Thesis

Algorytmiczne problemy sciezkowe w grafach planarnych (rozprawa doktorska),
Algorithmic Path Problems in Planar Graphs (PhD Thesis, in Polish)
Warsaw University, 2005.
[BibTeX entry] [PS] [PDF]
(The thesis is based on papers "Oracles for bounded length shortest paths in planar graphs", "Fast 3-coloring triangle-free planar graphs" and "Short cycles in planar graphs")

Popular science

  1. Problem komiwojażera w praktyce, Delta, 2 / 2020. (in Polish) [PDF]
  2. Problem izomorfizmu grafów, Delta, 12 / 2018. (in Polish) [PDF]
  3. Programy liniowe, gry i algorytmy, Delta, 8 / 2013. (in Polish) [PDF]
  4. O notacji asymptotycznej w analizie algorytmów, Delta, 1 / 2008, 4-5. (in Polish) [PDF]
  5. Spacery po mostach i przejażdżki po mieście, Software 2.0, 7 / 2002. (in Polish) [PDF]