General Information

Student: Lukáš Folwarczný
Office: 444
School: Charles University in Prague
E-mail: lfolwarczny guess_what_is_here gmail.com
  • L-bounded cut
  • IV-matching

L-bounded cut

Joint work with Pavel Dvořák, see his page for details about this problem.


Project Description

The generalization of perfect bipartite matching called IV-matching is formulated in the full version of article by Fiala, Klavík, Kratochvíl and Nedela [1].

Authors study algorithmic aspects of regular graph covers and one of their subproblems reduces to searching IV-matching thus the authors ask the question whether there is an efficient algorithm solving this problem.


Problem definition

Let $G=(V,E)$ be a bipartite graph with following properties:

IV-matching is a subset of edges $M\subseteq E$ such that: Each vertex from an even layer $V_{2k}$ is incident to exactly one vertex from $V_{2k-1}\cup V_{2k+1}$. Each vertex of the layer $V_{2k+1}$ is either incident to exactly two vertices from $V_{2k}$, or exactly one vertex from $V_{2k+2}$ (these two options are exclusive).

It implies that edges between layers $V_{2k+1}$ and $V_{2k+2}$ form a matching (I-shapes) and edges between layers $V_{2k}$ and $V_{2k+1}$ form independent V-shapes with centers in the layer $V_{2k+1}$.

Fig. 1: An example of IV-matching.
Key question

What is the complexity of finding IV-matching in a given graph?



In the 6th week we proved that the problem is NP-complete already for the case when $\ell = 4$. We also made few structural observations and identified some solvable instances. We are trying to find more.

Weekly Log

Week 1 (June 2 ‐ June 6)
  • I was introduced into a variety of problems I could work on and have decided to work on the L-bounded cut problem.
  • I studied basic results from Communication Complexity. [W1A]
  • I was introduced to the problem of embedding edit distance into Hamming distance and studied the article Johwari [W1B] where an open problem regarding this embedding is formulated.
    I have decided not to work on this problem, because it was further from Communication Complexity than I originally thought.
  • I presented the introduction to Network Flows as a prerequisite for Pavel's presentation about our problem of L-bounded cut.
  • [W1A] S. Arora: Chapter on communication complexity. PDF available online
  • [W1B] H. Johwari: Efficient Communication Protocols for Deciding Edit Distance. ESA'12 Proceedings of the 20th Annual European conference on Algorithms. PDF available online
Week 2 (June 9 ‐ June 13)
  • I began the study of the book by J. Flum and M. Grohe [W2A]: Learned about fixed parameter tractability, fpt reductions and the W-hiearchy.
  • I was introduced into the problem of IV-matching and decided to work on it.
  • We made first observations about the IV-matching problem.
  • I studied properties of L-bounded cuts and flows from [W2B] and [W2C].
  • [W2A] J. Flum, M. Grohe: Parameterized Complexity Theory. Springer. 2006.
  • [W2B] J. Adámek, V. Koubek: Remarks on flows in network with short paths. 1971. Commentationes Mathematicae Universitatis Carolinae 12, 4, 661–667.
  • [W2C] G. Baier, T. Erlebach, A. Hall, E. Köhler, P. Kolman, O. Pangrác, H. Schilling, M. Skutella: Length-Bounded Cuts and Flows. PDF available online
Week 3 (June 16 ‐ June 20)
  • Continued the study of the book [W2A] learned about properties of complexity classes para-NP, XP and W[P].
  • L-bounded cut: Capacitated vertex cover appears to be an interesting candidate for reduction. [W3A]
  • L-bounded cut: We were working on the reduction to prove W[1]-hardness.
  • IV-matching: We attempted to solve the problem with network flows and invented something what could be an approximation algorithm for instances of the problem with large clusters.
  • [W3A] M. Dom, D. Lokshtanov, S. Saurabh, Y. Villanger: Capacitated domination and covering: A parameterized perspective. 2008. PDF available online
Week 4 (June 23 ‐ June 27)
  • IV-matching: We invented new observation about sinks
  • IV-matching: We were able to improve the approximation algorithm from last week so that it does not need multicomodity flows neither linear programming, but only plain network flows.
  • I began the study of the book [W4A] by Lovász and Plummer to gather more matching techniques, I went through the first chapter.
  • I prepared a presentation introducing highlights of the Czech republic for the cultural day.
  • [W4A] L. Lovász, M. D. Plummer: Matching Theory. 2006. Annals of Discrete Mathematics.
Week 5 (June 30 ‐ July 4)
  • IV-matching: We proved that we can eliminate all bridges efficiently, thus it is sufficient to solve the problem for 2-edge-connected graphs.
  • IV-matching: I read another chapter of the book Matching Theory [W4A].
  • IV-matching: We were trying to invent an algorithm efficiently enumerating IV-matchings on a cycle.
  • L-bounded cut: Further attempt to reduce from the capacitated vertex cover.
Week 6 (July 7 ‐ July 11)
  • IV-matching: We proved that it is sufficient to solve the problem only for 2-vertex-connected graphs, because we can split the cut-vertices efficiently.
  • IV-matching: We proved that the problem of IV-matching is NP-complete already for the case with $\ell = 4$.
  • IV-matching: We were communicating with Pavel Klavík himself about some extensions of the problem and other ways of the research regarding the article [1].
  • IV-matching: I revisited solvable instances we know and tried to extend them.
Week 7 (July 14 ‐ July 18)
  • I wrote down our most important results in IV-matching into the form of a final report:
    • NP-completeness
    • Only 2-vertex-connected instances are interesting, because cut-vertices can be eliminated efficiently.
  • I organized a movie night. We watched the movie Pelíšky (Cosy Dens). It is a bitter comedy and in my opinion one of the best movies ever. I believe our American colleagues saw many important elements of the Czech culture through this movie.
  • I presented our results about IV-matching.