AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (587.3 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen

Engineering and IT, Charles Darwin University, Darwin 0909, Northern Territory, Australia.
Show Author Information

Abstract

This short paper highlights some open problems related to the work of Jianer Chen in the area of parameterized/multivariate algorithmics.

Keywords

parameterized complexitymultivariate algorithmicsopen problems

References

[1]
R. G. Downey and M. R. Fellows, Parameterized Complexity. Monographs in Computer Science. Springer-Verlag, New York, 1999.
Crossref
[2]
H. L. Bodlaender, On disjoint cycles, Lecture Notes in Computer Science, vol. 570, pp. 230-238, 1991.
Crossref Google Scholar
[3]
Y. Cao, J. Chen, and Y. Liu, On feedback vertex set new measure and new structures, in SWAT, 2010, pp. 93-104.
Crossref
[4]
J. Chen, I. A. Kanj, and G. Xia, Improved upper bounds for vertex cover, Theor. Comput. Sci., vol. 411, nos. 40-42, pp. 3736-3756, 2010.
Crossref Google Scholar
[5]
R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.
Crossref
[6]
L. Cai, J. Chen, R. G. Downey, and M. R. Fellows, On the parameterized complexity of short computation and factorization, Arch. Math. Log., vol. 36, nos. 4-5, pp. 321-337, 1997.
Crossref Google Scholar
[7]
J. Chen, B. Chor, M. Fellows, X. Huang, D. W. Juedes, I. A. Kanj, and G. Xia, Tight lower bounds for certain parameterized np-hard problems, Inf. Comput., vol. 201, no. 2, pp. 216-231, 2005.
Crossref Google Scholar
[8]
J. Chen, X. Huang, I. A. Kanj, and G. Xia, Strong computational lower bounds via parameterized complexity, J. Comput. Syst. Sci., vol. 72, no. 8, pp. 1346-1367, 2006.
Crossref Google Scholar
[9]
M. Patrascu and R. Williams, On the possibility of faster sat algorithms, in SODA, SIAM, 2010, pp. 1065-1075.
[10]
R. G. Downey, V. Estivill-Castro, M. R. Fellows, E. Prieto, and F. A. Rosamond, Cutting up is hard to do: The parameterized complexity of k-cut and related problems, Electr. Notes Theor. Comput. Sci., vol. 78, pp. 209-222, 2003.
Crossref Google Scholar
[11]
L. Cai and J. Chen, On fixed-parameter tractability and approximability of np optimization problems, J. Comput. Syst. Sci., vol. 54, no. 3, pp. 465-474, 1997.
Crossref Google Scholar
[12]
L. Cai, Fixed parameter tractability and approximation problems, project report, Teras A and M University, USA, 1992.
[13]
C. Bazgan, Schémas d’approximation et complexité paramétrée, dissertation, Méroire at DEA, Université, Paris Sad, 1995.
[14]
J. Chen and I. A. Kanj, Parameterized complexity and subexponential-time computability, in The Multivariate Algorithmic Revolution and Beyond, 2012, pp. 162-195.
Crossref
[15]
L. Cai and J. Chen, On fixed-parameter tractability and approximability of np-hard optimization problems, in ISTCS, 1993, pp. 118-126.
[16]
C. M. R. Kintala and P. C. Fischer, Refining nondeterminism in relativized polynomial-time bounded computations, SIAM J. Comput., vol. 9, no. 1, pp. 46-53, 1980.
Crossref Google Scholar
[17]
J. F. Buss and J. Goldsmith, Nondeterminism within P, SIAM J. Comput., vol. 22, no. 3, pp. 560-572, 1993. .
Crossref Google Scholar
[18]
C. H. Papadimitriou and M. Yannakakis, On limited nondeterminism and the complexity of the v-c dimension, J. Comput. Syst. Sci., vol. 53, no. 2, pp. 161-170, 1996.
Crossref Google Scholar
[19]
R. G. Downey, M. R. Fellows, and U. Stege, Computational tractability: The view from mars, Bulletin of the EATCS, vol. 69, pp. 73-97, 1999
Google Scholar
[20]
M. J. Dinneen, Bounded combinatorial width and forbidden substructures, dissectation, University of victoria, Canada, 1995. (Library version January 1996).
[21]
M. J. Dinneen, Too many minor order obstructions, J. UCS, vol. 3, no. 11, pp. 1199-1206, 1997.
Google Scholar
[22]
K. Cattell, M. J. Dinneen, R. G. Downey, M. R. Fellows, and M. A. Langston, On computing graph minor obstruction sets, Theor. Comput. Sci., vol. 233, nos. 1-2, pp. 107-127, 2000.
Crossref Google Scholar
[23]
H. Buhrman and J. M. Hitchcock, NP-hard sets are exponentially dense unless coNP C NP/poly, in IEEE Conference on Computational Complexity, IEEE Computer Society, 2008, pp. 1-7.
Crossref
[24]
H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems without polynomial kernels, J. Comput. Syst. Sci., vol. 75, no. 8, pp. 423-434, 2009.
Crossref Google Scholar
[25]
L. Fortnow and R. Santhanam, Infeasibility of instance compression and succinct pcps for np, J. Comput. Syst. Sci., vol. 77, no. 1, pp. 91-106, 2011.
Crossref Google Scholar
[26]
H. L. Bodlaender, M. R. Fellows, and M. T. Hallett, Beyond np-completeness for problems of bounded width: Hardness for the w hierarchy, in STOC, ACM, 1994, pp. 449-458.
[27]
M. Hallett, Private communication, 1994.
Tsinghua Science and Technology
Volume 19 Issue 4,
August 2014
Pages 325-328
DOI: 10.1109/TST.2014.6867514
Cite this article:
Fellows MR. Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen. Tsinghua Science and Technology, 2014, 19(4): 325-328. https://doi.org/10.1109/TST.2014.6867514

1120

Views

24

Downloads

1

Crossref

N/A

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 23 July 2014
Accepted: 23 July 2014
Published: 30 July 2014
© The author(s) 2014
Return