Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems
スポンサーリンク
概要
- 論文の詳細を見る
Given a connected graph G = (V,E) on n vertices, the Maximum r-Regular Induced Connected Subgraph (r-MaxRICS) problem asks for a maximum sized subset of vertices S ⊆ V such that the induced subgraph G[S] on S is connected and r-regular. It is known that 2-MaxRICS and 3-MaxRICS are NP-hard. Moreover, 2-MaxRICS cannot be approximated within a factor of n1-ε in polynomial time for any ε > 0 unless P = NP. In this paper, we show that r-MaxRICS are NP-hard for any fixed integer r ≥ 4. Furthermore, we show that for any fixed integer r ≥ 3, r-MaxRICS cannot be approximated within a factor of n1/6-ε in polynomial time for any ε > 0 unless P = NP.
著者
-
Miyano Eiji
Department Of Systems Design And Informatics Kyushu Institute Of Technology
-
ETO Hiroshi
Department of System Design and Informatics, Kyushu Institute of Technology
-
ASAHIRO Yuichi
Department of Information Science, Kyushu Sangyo University
関連論文
- Intussusception of the bladder neck does not promote early restoration to urinary continence after non-nerve-sparing radical retropubi c prostatectomy
- Prediction of potentially insignificant prostate cancer in men undergoing radical prostatectomy for clinically organ-confined disease
- Prognostic significance of vascular invasion in patients with bladder cancer who underwent radical cystectomy
- Preoperative prediction of final pathological features is not improved by the free-to-total prostate-specific antigen ratio in Japanese men with clinically localized prostate cancer
- Clinicopathological features of recurrence after radical surgery for nonmetastatic renal cell carcinoma
- Increased detection of clinically significant prostate cancer by additional sampling from the anterior lateral horns of the peripheral zone in combination with the standard sextant biopsy
- Long-term results of adjuvant hormonal therapy plus radiotherapy following radical prostatectomy for patients with pT3N0 or pT3N1 prostate cancer
- Microscopic venous invasion in renal cell carcinoma as a predictor of recurrence after radical surgery
- Clinical outcome of transrectal ultrasound-guided prostate biopsy, targeting eight cores, for detecting prostate cancer in Japanese men
- Global analysis of gene expression profiles in ileum in a rat bladder augmentation model using cDNA microarrays
- Successful treatment for squamous cell carcinoma of the female urethra with combined radio- and chemotherapy
- Health-related quality of life after chemotherapy for advanced germ cell tumors : A comparison of standard-dose and high-dose chemotherapy
- Significance of renal function in changes in acid-base metabolism after orthotopic bladder replacement : Colon neobladder compared with ileal neobladder
- Limited usefulness of the free-to-total prostate-specific antigen ratio for the diagnosis and staging of prostate cancer in Japanese men
- Pathological findings of radical prostatectomy specimens in Japanese men diagnosed on single core positive prostate biopsy in eight with a Gleason score less than 4
- Prediction of the extent of prostate cancer by the combined use of systematic biopsy and serum level of cathepsin D
- Predictors of prostate cancer on repeat transrectal ultrasound-guided systematic prostate biopsy
- Clinical outcome of conservative therapy for stage T1, grade 3 transitional cell carcinoma of the bladder
- Clinical outcome of bacillus Calmette-Guerin perfusion therapy for carcinoma in situ of the upper urinary tract
- Long-Term results of neoadjuvant treatment with M-VAC (methotrexate, vinblastine, doxorubicin, and cisplatin) for locally invasive transitional cell carcinoma of the urothelium
- Percutaneous Treatment of Transitional Cell Carcinoma of the Upper Urinary Tract
- Rejection of Mouse Renal Cell Carcinoma Elicited by Local Secretion of Interleukin-2
- Computational Complexities of University Interview Timetabling
- The Bump Hunting Method Using the Genetic Algorithm with the Extreme-Value Statistics
- Prognostic Variables in Patients with Upper Urinary Tract Cancers
- Comparison of Hormonal Therapy and Chemohormonal Therapy in Patients wit Newly Diagnosed Clinical Stage D Prostatic Cancer
- Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems