Joint work with Pavel Dvořák, see his
page for details about this problem.
IV-matching
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.
Let $G=(V,E)$ be a bipartite graph with following properties:
Vertices are partitioned into sets $V_1, \dots, V_\ell$ called layers. There
are only edges between two consecutive layers $V_k$ and $V_{k+1}$ for
$k=1,\dots,\ell-1$.
Each layer is further partitioned into clusters.
Edges of $G$ are described by edges on clusters (we call them
macroedges). If there is a macroedge between two clusters, then vertices of
these two clusters induce complete bipartite graph. If there is no macroedge, then these
vertices induce an edge-less graph.
Macroedges between clusters of layers $V_{2k}$ and $V_{2k+1}$ form a matching (not
necessarily maximum matching).
There are arbitrary macroedges between clusters of layers $V_{2k-1}$ and
$V_{2k}$.
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}$.
Key question
What is the complexity of finding IV-matching in a given graph?
References
[1] J. Fiala, P. Klavík, J. Kratochvíl and R. Nedela:
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs.
Conference ICALP 2014. Full version: arXiv:1402.3774 [math.CO]
Results
In the 6^{th} 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.
[W1B] H. Johwari: Efficient Communication Protocols for Deciding Edit
Distance. ESA'12 Proceedings of the 20^{th} 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.
Presentations
First Presentation (Introduction to Network Flows, the
L-bounded cut problem is in Pavel's presentation)