Kare, A S and Kalyanasundaram, Subrahmanyam
(2018)
Parameterized Algorithms for Graph
Partitioning Problems.
PhD thesis, Indian institute of technology Hyderabad.
Abstract
In parameterized complexity, a problem instance (I, k) consists of an input I and an
extra parameter k. The parameter k usually a positive integer indicating the size of the
solution or the structure of the input. A computational problem is called fixed-parameter
tractable (FPT) if there is an algorithm for the problem with time complexity O(f(k).nc
),
where f(k) is a function dependent only on the input parameter k, n is the size of the
input and c is a constant. The existence of such an algorithm means that the problem
is tractable for fixed values of the parameter. In this thesis, we provide parameterized
algorithms for the following NP-hard graph partitioning problems:
(i) Matching Cut Problem: In an undirected graph, a matching cut is a partition
of vertices into two non-empty sets such that the edges across the sets induce a matching.
The matching cut problem is the problem of deciding whether a given graph has
a matching cut. The Matching Cut problem is expressible in monadic second-order
logic (MSOL). The MSOL formulation, together with Courcelle’s theorem implies linear
time solvability on graphs with bounded tree-width. However, this approach leads to a
running time of f(||ϕ||, t) · n, where ||ϕ|| is the length of the MSOL formula, t is the
tree-width of the graph and n is the number of vertices of the graph. The dependency of
f(||ϕ||, t) on ||ϕ|| can be as bad as a tower of exponentials.
In this thesis we give a single exponential algorithm for the Matching Cut problem
with tree-width alone as the parameter. The running time of the algorithm is 2O(t)
· n.
This answers an open question posed by Kratsch and Le [Theoretical Computer Science,
2016]. We also show the fixed parameter tractability of the Matching Cut problem
when parameterized by neighborhood diversity or other structural parameters.
(ii) H-Free Coloring Problems: In an undirected graph G for a fixed graph H,
the H-Free q-Coloring problem asks to color the vertices of the graph G using at
most q colors such that none of the color classes contain H as an induced subgraph.
That is every color class is H-free. This is a generalization of the classical q-Coloring
problem, which is to color the vertices of the graph using at most q colors such that no
pair of adjacent vertices are of the same color. The H-Free Chromatic Number is
the minimum number of colors required to H-free color the graph.
For a fixed q, the H-Free q-Coloring problem is expressible in monadic secondorder
logic (MSOL). The MSOL formulation leads to an algorithm with time complexity
f(||ϕ||, t) · n, where ||ϕ|| is the length of the MSOL formula, t is the tree-width of the
graph and n is the number of vertices of the graph.
In this thesis we present the following explicit combinatorial algorithms for H-Free
Coloring problems:
• An O(q
O(t
r
)
· n) time algorithm for the general H-Free q-Coloring problem,
where r = |V (H)|.
• An O(2t+r log t
· n) time algorithm for Kr-Free 2-Coloring problem, where Kr is
a complete graph on r vertices.
The above implies an O(t
O(t
r
)
· n log t) time algorithm to compute the H-Free Chromatic
Number for graphs with tree-width at most t. Therefore H-Free Chromatic
Number is FPT with respect to tree-width.
We also address a variant of H-Free q-Coloring problem which we call H-(Subgraph)Free
q-Coloring problem, which is to color the vertices of the graph such that none of the
color classes contain H as a subgraph (need not be induced).
We present the following algorithms for H-(Subgraph)Free q-Coloring problems.
• An O(q
O(t
r
)
· n) time algorithm for the general H-(Subgraph)Free q-Coloring
problem, which leads to an O(t
O(t
r
)
· n log t) time algorithm to compute the H-
(Subgraph)Free Chromatic Number for graphs with tree-width at most t.
• An O(2O(t
2
)
· n) time algorithm for C4-(Subgraph)Free 2-Coloring, where C4
is a cycle on 4 vertices.
• An O(2O(t
r−2
)
· n) time algorithm for {Kr\e}-(Subgraph)Free 2-Coloring,
where Kr\e is a graph obtained by removing an edge from Kr.
• An O(2O((tr2
)
r−2
)
· n) time algorithm for Cr-(Subgraph)Free 2-Coloring problem,
where Cr is a cycle of length r.
(iii) Happy Coloring Problems: In a vertex-colored graph, an edge is happy if its
endpoints have the same color. Similarly, a vertex is happy if all its incident edges are
happy. we consider the algorithmic aspects of the following Maximum Happy Edges
(k-MHE) problem: given a partially k-colored graph G, find an extended full k-coloring
of G such that the number of happy edges are maximized. When we want to maximize
the number of happy vertices, the problem is known as Maximum Happy Vertices
(k-MHV).
We show that both k-MHE and k-MHV admit polynomial-time algorithms for trees.
We show that k-MHE admits a kernel of size k + `, where ` is the natural parameter,
the number of happy edges. We show the hardness of k-MHE and k-MHV for some
special graphs such as split graphs and bipartite graphs. We show that both k-MHE
and k-MHV are tractable for graphs with bounded tree-width and graphs with bounded
neighborhood diversity.
vii
In the last part of the thesis we present an algorithm for the Replacement Paths
Problem which is defined as follows: Let G (|V (G)| = n and |E(G)| = m) be an undirected
graph with positive edge weights. Let PG(s, t) be a shortest s − t path in G. Let l be the
number of edges in PG(s, t). The Edge Replacement Path problem is to compute a
shortest s − t path in G\{e}, for every edge e in PG(s, t). The Node Replacement
Path problem is to compute a shortest s−t path in G\{v}, for every vertex v in PG(s, t).
We present an O(TSP T (G) + m + l
2
) time and O(m + l
2
) space algorithm for both
the problems, where TSP T (G) is the asymptotic time to compute a single source shortest
path tree in G. The proposed algorithm is simple and easy to implement.
Actions (login required)
 |
View Item |
Altmetric
Altmetric