Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Parameterized Complexity of the Acyclic Matching Problem
112
0
0.0
(
0
)
Added by
Ramin Javadi
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A matching is a set of edges in a graph with no common endpoint. A matching $M$ is called acyclic if the induced subgraph on the endpoints of the edges in $M$ is acyclic. Given a graph $G$ and an integer $k$, Acyclic Matching Problem seeks for an acyclic matching of size $k$ in $G$. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs with maximum degree three and girth of arbitrary large. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter $k$. On the other hand, the problem is fixed parameter tractable with respect to $k$, for line graphs, $C_4$-free graphs and every proper minor-closed class of graphs (including bounded tree-width and planar graphs).
rate research
Read More
In this paper we study the problem of finding a small safe set $S$ in a graph $G$, i.e. a non-empty set of vertices such that no connected component of $G[S]$ is adjacent to a larger component in $G - S$. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth $pw$ and cannot be solved in time $n^{o(pw)}$ unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number $vc$ unless $mathrm{PH} = Sigma^{mathrm{p}}_{3}$, but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity $nd$, and (4) it can be solved in time $n^{f(cw)}$ for some double exponential function $f$ where $cw$ is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size.
We study the NP-hard textsc{$k$-Sparsest Cut} problem ($k$SC) in which, given an undirected graph $G = (V, E)$ and a parameter $k$, the objective is to partition vertex set into $k$ subsets whose maximum edge expansion is minimized. Herein, the edge expansion of a subset $S subseteq V$ is defined as the sum of the weights of edges exiting $S$ divided by the number of vertices in $S$. Another problem that has been investigated is textsc{$k$-Small-Set Expansion} problem ($k$SSE), which aims to find a subset with minimum edge expansion with a restriction on the size of the subset. We extend previous studies on $k$SC and $k$SSE by inspecting their parameterized complexity. On the positive side, we present two FPT algorithms for both $k$SSE and 2SC problems where in the first algorithm we consider the parameter treewidth of the input graph and uses exponential space, and in the second we consider the parameter vertex cover number of the input graph and uses polynomial space. Moreover, we consider the unweighted version of the $k$SC problem where $k geq 2$ is fixed and proposed two FPT algorithms with parameters treewidth and vertex cover number of the input graph. We also propose a randomized FPT algorithm for $k$SSE when parameterized by $k$ and the maximum degree of the input graph combined. Its derandomization is done efficiently. oindent On the negative side, first we prove that for every fixed integer $k,taugeq 3$, the problem $k$SC is NP-hard for graphs with vertex cover number at most $tau$. We also show that $k$SC is W[1]-hard when parameterized by the treewidth of the input graph and the number~$k$ of components combined using a reduction from textsc{Unary Bin Packing}. Furthermore, we prove that $k$SC remains NP-hard for graphs with maximum degree three and also graphs with degeneracy two. Finally, we prove that the unweighted $k$SSE is W[1]-hard for the parameter $k$.
We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q>1 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q>1, and has been well-studied from the point of view of approximation. Our main focus is the case when q=2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.
The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach requires that the rows of a table are partitioned in clusters of size at least $k$ and that all the rows in a cluster become the same tuple, after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be APX-hard even when the records values are over a binary alphabet and $k=3$, and when the records have length at most 8 and $k=4$ . In this paper we study how the complexity of the problem is influenced by different parameters. In this paper we follow this direction of research, first showing that the problem is W[1]-hard when parameterized by the size of the solution (and the value $k$). Then we exhibit a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns. Finally, we investigate the computational (and approximation) complexity of the $k$-anonymity problem, when restricting the instance to records having length bounded by 3 and $k=3$. We show that such a restriction is APX-hard.
Andreevs Problem states the following: Given an integer $d$ and a subset of $S subseteq mathbb{F}_q times mathbb{F}_q$, is there a polynomial $y = p(x)$ of degree at most $d$ such that for every $a in mathbb{F}_q$, $(a,p(a)) in S$? We show an $text{AC}^0[oplus]$ lower bound for this problem. This problem appears to be similar to the list recovery problem for degree $d$-Reed-Solomon codes over $mathbb{F}_q$ which states the following: Given subsets $A_1,ldots,A_q$ of $mathbb{F}_q$, output all (if any) the Reed-Solomon codewords contained in $A_1times cdots times A_q$. For our purpose, we study this problem when $A_1, ldots, A_q$ are random subsets of a given size, which may be of independent interest.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
