Name
Abstract | ||
|---|---|---|
We study the computational complexity of graph planarization via edge contraction. The problem Contract asks whether there exists a set S of at most k edges that when contracted produces a planar graph. We give an FPT algorithm in time $\mathcal{O}(n^2 f(k))$ which solves a more general problem P-RestrictedContract in which S has to satisfy in addition a fixed inclusion-closed MSOL formula P. For different formulas P we get different problems. As a specific example, we study the ℓ-subgraph contractability problem in which edges of a set S are required to form disjoint connected subgraphs of size at most ℓ. This problem can be solved in time $\mathcal{O}(n^2 f'(k,l))$ using the general algorithm. We also show that for ℓ≥2 the problem is NP-complete. And it remains NP-complete when generalized for a fixed genus (instead of planar graphs). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2017.02.030 | Theor. Comput. Sci. |
Keywords | Field | DocType |
msol restricted contractibility,fpt algorithm,general algorithm,different formula,subgraph contractability problem,planar graph,problem contract,different problem,general problem p-restrictedcontract,fixed inclusion-closed msol formula,fixed genus | Discrete mathematics,Graph,Combinatorics,Disjoint sets,Existential quantification,General algorithm,Hexagonal tiling,Edge contraction,Mathematics,Planar graph,Computational complexity theory | Conference |
Volume | ISSN | Citations |
676 | 0304-3975 | 1 |
PageRank | References | Authors |
0.38 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| James Abello | 1 | 699 | 62.19 |
| Pavel Klavík | 2 | 95 | 10.63 |
| Jan Kratochvíl | 3 | 1751 | 151.84 |
| tomas vyskocil | 4 | 56 | 5.61 |