Research papers
See elsewhere
[dblp]  [Google scholar]  [University portal]
Jump to area
Exponentialtime and parameterized algorithms  Approximation algorithms  Planar graphs  Other areas
Exponentialtime and parameterized algorithms

FineGrained Complexity of kOPT in BoundedDegree 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] 
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] 
On Directed Feedback Vertex Set parameterized by treewidth, Marthe
Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz
Socala, Marcin Wrochna.
Proc. 44th Workshop on GraphTheoretic Concepts in Computer Science (WG 2018), LNCS 11159, Springer, pp. 6578.
[arXiv] [DOI] 
Improving TSP tours using dynamic programming over tree decomposition, with
Marek Cygan and Arkadiusz Socala.
ACM Transactions on Algorithms, vol. 15(4), pp. 54:154:19, 2019.
[arXiv] [DOI]
Conference version: Proc. 25th Annual European Symposium on Algorithms (ESA 2017). Best paper award.
[DOI] [slides] 
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:113:19
[DOI] [arXiv]
Conference version: Proc. 25th Annual European Symposium on Algorithms (ESA 2017).
[DOI] 
Approximation and Parameterized Complexity of Minimax Approval Voting, with
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
Journal of Artificial Intelligence Research, 63 (2018) 495513
[DOI] [arXiv]
Conference version: Proc. 31st AAAI Conference on Artificial Intelligence (AAAI'17), pp. 459465, AAAI Press, 2017.
[DOI] 
On the finegrained complexity of rainbow coloring, with
Juho Lauri and Arkadiusz Socala
SIAM J. Discrete Math, 32(3), 16721705 (2018)
[arXiv] [DOI]
Conference version: Proc. 24th Annual European Symposium on Algorithms (ESA 2016)
[DOI] 
On finding rainbow and colorful paths, with
Juho Lauri
Theor. Comput. Sci. 628: 110114 (2016)
[Publisher's version] 
Linear kernels for outbranching problems in sparse digraphs, with
Marthe Bonamy, Michal Pilipczuk and Arkadiusz Socala
Algorithmica 79(1): 159188 (2017).
[arXiv] [BibTeX entry] [DOI]
Conference version: Proc IPEC'15, LNCS vol 9134, pp. 199211, 2015.
[BibTeX entry] [DOI] 
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. 687713.
[DOI] [arXiv] [talk]
Conference version: Proc. ICALP 2015, pp. 243255.
[BibTeX entry] [DOI] [slides] 
Constrained Multilinear Detection and Generalized Graph Motifs, with
Andreas Björklund, Petteri Kaski
Algorithmica 74(2): 947967 (2016)
(Extended, generalized version of our STACS 2013 paper)
[PDF] [Publisher's version] 
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. 104118.
[PDF] [Publisher's version] 
A 13kkernel for Planar Feedback Vertex Set via Region Decomposition, with
Marthe Bonamy
Theor. Comput. Sci. 645: 2540 (2016)
[arXiv] [DOI]
Conference version: A 14kkernel for Planar Feedback Vertex Set via Region Decomposition Proc. 9th International Symposium on Parameterized and Exact Computation, IPEC'14, LNCS vol 8894, Springer, 97109, 2014.
[slides] 
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. 149160.
[Publisher's version] [BibTeX entry] [slides] 
Assigning channels via the
meetinthemiddle approach, with Arkadiusz Socala,
Algorithmica 74(4): 14351452 (2016) (open access).
[arXiv] [PDF] [DOI]
Conference version: Proc. 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), LNCS 8503, 2014, pp. 282293.
[Publisher's version]Abstract: We study the complexity of the CHANNEL ASSIGNMENT problem. By applying the meetinthemiddle 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 TCOLORING, a CSP problem that generalizes CHANNEL ASSIGNMENT. We show that GENERALIZED TCOLORING does not admit a $2^{2^{o\left(\sqrt{n}\right)}} {\rm poly}(r)$time algorithm, where $r$ is the size of the instance.

Counting thin
subgraphs via packings faster than meetinthemiddle time, with Andreas Björklund
and Petteri Kaski,
ACM Trans. Algorithms. 13(4): 48:148:26 (2017)
[arXiv] [DOI]
Conference version: ACMSIAM Symposium on Discrete Algorithms (SODA 2014),
[DOI]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 "meetinthemiddle" 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 colorcoding lower bound.
 Probably Optimal Graph Motifs,
with Andreas Björklund and Petteri Kaski
Proc. 30th Symposium on Theoretical Aspects of Computer Science (STACS 2013),
LIPIcs, 2031, 2013.
[arXiv] [Publisher's version] [BibTeX entry] [slides]  Nonblocker in Hminor free graphs: kernelization meets
discharging
Proc. 7th International Symposium on Parameterized and Exact Computation (IPEC 2012),
LNCS 7535, 6172, 2012.
[arXiv] [Publisher's version] [slides]  A 9k kernel for nonseparating independent set in planar graphs,
with Marcin Mucha
Theoretical Computer Science, Vol. 516, 2013, 8695. .
Conference version: Proc. 38th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2012), LNCS 7551, 160171, 2012.
[arXiv] [Publisher's version] [slides]  Towards optimal kernel for connected vertex cover in
planar graphs with Marcin Pilipczuk and Karol Suchan.
Discr. Appl. Math., Vol. 161, 11541161, 2013.
[arXiv] [Publisher's version] 
Channel Assignment via Fast Zeta Transform,
with Marek Cygan
Information Processing Letters, Vol. 111, No. 15, 2011, 727730.
[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 inclusionexclusion principle.

Improved induced matchings in sparse graphs,
with and Rok Erman, Matjaz Krnc, Tomasz Walen
Discr. Appl. Math., Vol. 158, No. 18, pp 19942003, 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(2^{159√k}+n)time whether an nvertex 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(2^{25.5√k}+n)time algorithm. Its main ingredient is a new, O*(4^{w})time algorithm for finding a maximum induced matching in a graph of branchwidth at most w.
Conference version: Proc. 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009), LNCS 5917, 134138, 2009. 
ExponentialTime Approximation of Weighted Set Cover
with Marek Cygan and Mateusz Wykurz
Information Processing Letters Vol. 109, 2009, 957961.
[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 exponentialtime algorithms for problems of that kind. The goal is getting the time complexity still of order O(c^{n}), 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  tradeoffs between approximation factor and the time complexity. We use general transformations from exponentialtime exact algorithms to approximations that are faster but still exponentialtime. For example, we show that for any reduction rate r, one can transform any O*(c^{n})time algorithm for Set Cover into a (1+ln(r))approximation algorithm running in time O*(c^{n/r}). We believe that results of that kind extend the applicability of exact algorithms for NPhard problems.
The above paper contains selected results from the earlier technical report:
ExponentialTime Approximation of Hard Problems, with Marek Cygan, Marcin Pilipczuk and Mateusz Wykurz
[arXiv] [slides]  Improved Edge Coloring with Three Colors
Theoretical Computer Science, Vol. 410, No. 3840, 2009, 37333742.
[BibTeX entry] [PDF] [Publisher's version]
Conference version: Proc. 32nd Int. Workshop GraphTheoretic Concepts in Comp. Sci. (WG 2006) , LNCS 4271, 2006, 90101.
[BibTeX entry] [Publisher's version] [slides]Abstract: We show an O(1.344^{n})=O(2^{0.427 n}) algorithm for edgecoloring an nvertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous, O(2^{n/2}) algorithm of Beigel and Eppstein [J. Alg., 2005]. We apply a very natural approach of generating inclusionmaximal matchings of the graph. The time complexity of our algorithm is estimated using the "measure and conquer" technique.Software: File [quasiconvex.cpp] contains the program used to find optimal values of parameters in measureandconquer time complexity proof of the 3edgecoloring algorithm from the paper. It is a C++ implementation of the quasiconvex programming algorithm from the paper D. Eppstein "Quasiconvex Analysis of Backtracking Algorithms", Proc. SODA'04, pages 781790, 2004.
Approximation algorithms

Beyond the Shannon's Bound, with Michał Farnik and Arkadiusz Socała
[arXiv] 
Beyond the Vizing's bound for at most seven colors, with Marcin Kamiński
SIAM J. Discrete Math., vol. 28, no. 3, 2014, 13341362.
[arXiv] [Publisher's version] 
Approximating the maximum 3 and 4edgecolorable subgraph,
with Marcin Kamiński,
Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), LNCS 6139, 2010, pp. 395407.
[BiBTeX entry] [Electronic version] [slides]  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. 7283.
[arXiv] [Electronic version]  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. 471482.
[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.  Deterministic 7/8approximation for the Metric Maximum TSP, with Marcin
Mucha
Theoretical Computer Science, Vol. 410, 2009, 50005009.
[BibTeX entry] [PDF] [Electronic version]
Conference version: Proc. APPROXRANDOM 2008, LNCS 5171, 2008, pp. 132145.
[Electronic version]Abstract: We present the first 7/8approximation 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/8O(n^{1/2}) and the deterministic (7/8O(n^{1/3})) approximation algorithm of Chen and Nagoya [ESA, 2005].
In the new algorithm, we extend the approach of processing local configurations using socalled looseends, which we introduced in [WADS, 2007].  35/44Approximation for Asymmetric Maximum TSP with Triangle Inequality,
with Marcin Mucha,
Full version: Algorithmica, Volume 59, No. 2, 2011, pp 240255.
[PDF] [Publisher's version]
Conference version: Proc. 10th International Workshop on Algorithms and Data Structures (WADS 2007), LNCS 4619, 2007, pp. 589600.
[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].  Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
Proc. 17th International Symposium on Algorithms and Computation (ISAAC 2006), LNCS 4288, 2006, 557566.
[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
 A Planar Linear Arboricity Conjecture,
with Marek Cygan, JianFeng Hou, Borut Luzar and JianLiang Wu.
J. Graph Theory, vol. 69, no. 4, 2012, pp. 403425.
[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. 204216.
arXiv:0912.5528, 2009.
[PDF] [Publisher's version]  An improved bound on the largest induced forests for trianglefree planar
graphs, with Borut Luzar and Riste Skrekovski
Discrete Mathematics & Theoretical Computer Science Vol. 12, No. 1, 87100, 2010.
[PDF] [BibTeX entry] [Publisher's version]Abstract: In 1979 Alberson and Berman raised a conjecture that every nvertex 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 Q_{3} 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.  Total colouring of plane graphs with maximum degree nine, with JeanSebastien Sereni and Riste
Skrekovski,
SIAM J. Discrete Math., Vol. 22, No. 4, 2008, 14621479.
[BibTeX entry] [PDF] [Publisher's version]Abstract: The central problem of the totalcolourings is the TotalColouring Conjecture, which asserts that every graph of maximum degree Δ admits a (Δ + 2)totalcolouring. Similarly to edgecolourings  with Vizing's edgecolouring 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)totallycolourable. On the other hand, such a statement does not hold if Δ ≤ 3. We prove that every plane graph of maximum degree 9 can be 10totallycoloured.  New LinearTime Algortihms for EdgeColoring Planar Graphs,
with Richard Cole
Algorithmica, Vol. 50, No. 3, 2008, 351368 .
[BibTeX entry] [PS] [PDF] [Publisher's version]Abstract: We show efficient algorithms for edgecoloring planar graphs. Our main result is a lineartime 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 lineartime 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.  A Generalization of Kotzig's Theorem and its Application,
with Richard Cole, Riste Skrekovski,
SIAM J. Discrete Math., Vol. 21, No. 1, 2007, 93106.
[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 wellknown Kotzig Theorem states that every 3connected 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 2alternating cycles and 3alternators. This implies that planar graphs with maximum degree Δ ≥ 12 are Δedgechoosable. We prove a similar result with 2alternating cycles and 3alternators replaced by five fixed boundedsized configurations called crowns. This gives another proof of Δedgechoosability of planar graphs with Δ ≥ 12. However, we show efficient choosability, i.e. we describe a lineartime algorithm for max{Δ, 12}edgelistcoloring planar graphs. This extends the result of Chrobak and Yung [J. Alg., 1989].  Oracles for Bounded Length Shortest Paths in Planar Graphs, with Maciej
Kurowski
ACM Transactions on Algorithms, Vol. 2, No. 3, 2006, 335363.
[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 minorclosed family of graphs.  Fast 3Coloring TriangleFree Planar Graphs,
Algorithmica, Vol. 58, No. 3, 2010, 770789.
[PDF] [Publisher's version]
Conference version: Proc. 12th Annual European Symposium on Algorithms (ESA 2004), LNCS 3221, 2004, 436447.
[BibTeX entry] [Publisher's version]Abstract: Although deciding whether the vertices of a planar graph can be colored with three colors is NPhard, the widely known Grötzsch's theorem states that every trianglefree planar graph is 3colorable. We show the first o(n^2) algorithm for 3coloring vertices of trianglefree planar graphs. The time complexity of the algorithm is O(n log n).Note: In 2009, Dvorak, Kawarabayashi and Thomas showed a lineartime algorithm (see here).
 More on Light Graphs in 3Connected 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 3connected 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 kcycle, 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 C_{5} or a cycle C_{14}. Very recently, T. Madaras showed that K_{1,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.  Short Cycles in Planar Graphs,
Proc. 29th Workshop GraphTheoretic Concepts in Comp. Sci. (WG 2003), LNCS 2880, 2003, 284296.
[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 nvertex 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 sideeffect of our approach we show that the maximum number of kcycles in nvertex planar graph is Θ(n^{⌊k/2⌋}).  Short Path Queries in Planar Graphs in Constant Time,
with M.Kurowski,
Proc. 35th Symp. Theory of Computing (STOC 2003), 2003, 143148.
[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.  A New 3Color Criterion For Planar Graphs, with K. Diks and M.
Kurowski,
Proc. 28th Workshop GraphTheoretic Concepts in Comp. Sci. (WG 2002), LNCS 2573, 2002, 138149.
[BibTeX entry] [PS] [PDF] [Publisher's version]Abstract: We present a new general 3color criterion for planar graphs. This criterion easily implies several known sufficent 3colorability conditions, as well as some new consequences, namely: A neartraingulation (plane graph with at most one nontriangular face) is 3colorable iff every vertex not incident with the nontriangular face has even degree.
 A sufficient and necessary 3colorability condition for triangulations
with holes (plane graphs such that each vertex is incident with at most one
nontriangular face). Such a graph is 3colorable iff
 every vertex not incident with the nontriangular face has even degree.
 for each nontriangular face f, when we paint the edges incident with f in black and white so that the color changes only in odddegree vertices, then the numbers of black and white edges are congruent modulo 3.
Other areas
 Adjacency Queries in Dynamic Sparse Graphs
Information Processing Letters, Vol. 102, No. 5, 2007, 191195
[BibTeX entry] [PS] [PDF] [Publisher's version]Abstract: We deal with the problem of maintaining a dynamic graph so that queries of the formis 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 linearsize data structure which processes queries in constant worstcase 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) worstcase time for query, O(1) amortized time for insertions and O(1) worstcase 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) worstcase 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(log^{k}n), for any constant k.  A Note on Scheduling EqualLength Jobs to Maximize Throughput,
with M. Chrobak, C. Durr, W. Jawor, M. Kurowski
Short version: Journal on Scheduling, Vol. 9, No. 1, 2006, 7173.
[BibTeX entry] [Publisher's version]
Extended version: arXiv.org ePrint archive, cs.DS/0410046, 2004.
[BibTeX entry] [PS] [PDF]Abstract: We study the problem of scheduling equallength 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 1r_{j}; pj = pΣU_{j}. 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(n^{5}).
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 3coloring trianglefree planar graphs" and "Short cycles in planar graphs")
Popular science
 Programy liniowe, gry i algorytmy, Delta, 8 / 2013, 13. (in Polish) [PDF]
 O notacji asymptotycznej w analizie algorytmów, Delta, 1 / 2008, 45. (in Polish) [PS]
 Spacery po mostach i przejażdżki po mieście, Software 2.0, 7 / 2002. (in Polish) [PDF]