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 fixedparameter
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 NPhard graph partitioning problems:
(i) Matching Cut Problem: In an undirected graph, a matching cut is a partition
of vertices into two nonempty 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 secondorder
logic (MSOL). The MSOL formulation, together with Courcelle’s theorem implies linear
time solvability on graphs with bounded treewidth. However, this approach leads to a
running time of f(ϕ, t) · n, where ϕ is the length of the MSOL formula, t is the
treewidth 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 treewidth 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) HFree Coloring Problems: In an undirected graph G for a fixed graph H,
the HFree qColoring 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 Hfree. This is a generalization of the classical qColoring
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 HFree Chromatic Number is
the minimum number of colors required to Hfree color the graph.
For a fixed q, the HFree qColoring 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 treewidth of the
graph and n is the number of vertices of the graph.
In this thesis we present the following explicit combinatorial algorithms for HFree
Coloring problems:
• An O(q
O(t
r
)
· n) time algorithm for the general HFree qColoring problem,
where r = V (H).
• An O(2t+r log t
· n) time algorithm for KrFree 2Coloring 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 HFree Chromatic
Number for graphs with treewidth at most t. Therefore HFree Chromatic
Number is FPT with respect to treewidth.
We also address a variant of HFree qColoring problem which we call H(Subgraph)Free
qColoring 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 qColoring problems.
• An O(q
O(t
r
)
· n) time algorithm for the general H(Subgraph)Free qColoring
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 treewidth at most t.
• An O(2O(t
2
)
· n) time algorithm for C4(Subgraph)Free 2Coloring, where C4
is a cycle on 4 vertices.
• An O(2O(t
r−2
)
· n) time algorithm for {Kr\e}(Subgraph)Free 2Coloring,
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 2Coloring problem,
where Cr is a cycle of length r.
(iii) Happy Coloring Problems: In a vertexcolored 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
(kMHE) problem: given a partially kcolored graph G, find an extended full kcoloring
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
(kMHV).
We show that both kMHE and kMHV admit polynomialtime algorithms for trees.
We show that kMHE admits a kernel of size k + `, where ` is the natural parameter,
the number of happy edges. We show the hardness of kMHE and kMHV for some
special graphs such as split graphs and bipartite graphs. We show that both kMHE
and kMHV are tractable for graphs with bounded treewidth 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.
[error in script]
Actions (login required)

View Item 