피드백 정점 집합

그래프 이론의 수학 분야에서, 그래프의 피드백 정점 집합(FVS)은 제거가 순환 없이 그래프를 남기는 정점 집합이다. (제거는 정점과 그에 인접한 모든 모서리를 삭제하는 것을 의미한다.)마찬가지로 각 FVS는 그래프 내의 임의의 사이클의 적어도 하나의 정점을 포함한다.그래프의 피드백 정점 집합 번호는 가장 작은 피드백 정점 집합의 크기입니다.최소 피드백 정점 집합 문제는 NP-완전 문제이며, NP-완전인 것으로 나타난 첫 번째 문제 중 하나였습니다.운영체제, 데이터베이스 시스템, VLSI 칩 설계 등에 광범위하게 응용되고 있습니다.

정의.

FVS 결정의 문제는 다음과 같습니다.

인스턴스: (무방향 또는 방향)

G=(V,E)

G

G=(V,E)

(

G=(V,E)

,

G=(V,E)

) {

displaystyle

G = (

V, E)}

및

G=(V,E)

양의

정수

k

{

displaystyle

k

k

질문: X

(\displaystyle

X\

leq

k

)

의

X\subseteq V

X

(\displaystyle

X

\subseteq

V

)

는

X\subseteq V

X

(\displaystyle

X

)

의

X

모든

정점과 인접한 가장자리가

G(\

displaystyle

G

G

에서 삭제되면 나머지는 사이클 프리입니까?

G{\ $displaystyle$ G $}$ 에서 $G$ X {\ $displaystyle$ X $}$ 를 $X$ $X$ 한 후 남는 $G[V\setminus X]$ G $[V\setminus X]$ 는 $G[V\setminus X]$ 유도 포레스트이다(유도 그래프의 경우 유도 유도 유도 비순환 그래프).따라서 그래프에서 최소 FVS를 찾는 것은 최대 유도 포레스트를 찾는 것과 같다(유향 그래프의 경우 최대 유도 비순환 그래프).

NP-경도

Karp(1972)는 유도 그래프의 최소 FVS 문제가 NP-완전임을 보여주었다.이 문제는 최대 도수 및 도수 2인 방향 그래프와 최대 도수 및 도수 ^[1]3인 방향 평면 그래프에서 NP-완전 상태로 남아 있다.

Karp의 감소는 또한 무방향 그래프에서 FVS 문제의 NP-완전성을 의미하며, 여기서 문제는 최대 4도 그래프에서 NP-hard로 유지된다.FVS 문제는 최대 ^[2]3도 그래프에서 다항식 시간으로 해결할 수 있습니다.

정확한 알고리즘

최소 피드백 정점 집합의 크기를 찾는 해당 NP 최적화 문제는 시간 O(1.7347ⁿ)에 해결할 수 있습니다. 여기서 n은 ^[3]그래프 내의 정점 수입니다.이 알고리즘은 실제로 최대 유도 포레스트를 계산하며, 이러한 포레스트를 얻을 때 그 보완은 최소 피드백 정점 집합이다.그래프에서 최소 피드백 정점 집합의 수는 Oⁿ(1.8638)^[4]로 제한됩니다.방향 피드백 정점 집합 문제는 여전히 시간 O*(1ⁿ.9977)로 해결할 수 있습니다. 여기서 n은 주어진 방향 ^[5]그래프에 있는 정점 수입니다.지시된 문제와 지시되지 않은 문제의 매개 변수화된 버전은 모두 고정 매개 변수 추적 가능합니다.^[6]

최대 3도의 무방향 그래프에서 피드백 정점 집합 문제는 선형 매트로이드에 ^[7]대한 매트로이드 패리티 문제의 인스턴스로 변환함으로써 다항 시간 내에 해결할 수 있다.

근사치

방향성이 없는 문제는 APX에서 발생.이것은 다음과 같은 사실에서 비롯된다.

정점 커버 ^[8]문제의 APX 완전성
정점 피복 문제에서 정점 피복 문제까지의 L 감소를 보존하는 근사치의 존재
기존 상수 계수 근사 알고리즘.^[9]

무방향 그래프에서 가장 잘 알려진 근사 알고리즘은 ^[10]2배입니다.

지시된 버전이 일정 비율 내에서 다항식 시간 근사치인지, 따라서 APX-완전인지 여부는 미해결 질문입니다.

경계

Erdss-Posa 정리에 따르면, 최소 피드백 정점 집합의 크기는 주어진 ^[11]그래프에서 최대 정점-분리 주기 수의 로그 인자 내에 있다.

적용들

운영 체제에서 피드백 정점 집합은 교착 상태 복구 연구에 중요한 역할을 합니다.operating system의 wait-for 그래프에서 각 지시 사이클은 교착 상태에 대응합니다.모든 교착 상태를 해결하려면 차단된 일부 프로세스를 중단해야 합니다.이 그래프에서 최소 피드백 정점 집합은 ^[12]중단해야 하는 최소 프로세스 수에 해당합니다.

피드백 정점 집합 문제는 VLSI 칩 ^[13]설계에 적용되어 있습니다.
또 다른 응용 분야는 복잡성 이론입니다.그래프의 일부 계산 문제는 일반적으로 NP-hard이지만, 경계 FVS 번호를 가진 그래프의 경우 다항식 시간으로 해결할 수 있다.예를 들어^[14] 그래프 동형성 및 경로 ^[15]재구성 문제가 있습니다.

메모들

^ 개리와 존슨 때문에 발표되지 않은 결과, cf.Garey & Johnson (1979년): GT7
^ 우에노·카지타니·고토(1988년), 리앤류(1999년)
^ Fomin & Villanger (2010)
^ 포민 등 (2008년).
^ Razgon (2007년).
^ 첸 등 (2008년).
^ 우에노·카지타니·고토(1988년).
^ Dinur & Safra 2005
^ ^a ^b 카르프(1972)
^ Becker & Geiger (1996년).또, 같은 근사비를 가지는 대체 근사 알고리즘에 대해서는, Bafna, Berman, Fujito(1999)를 참조해 주세요.
^ Erdss & Posa(1965).
^ Silverschatz, Galvin & Gagne (2008).
^ Festa, Pardalos & Resende(2000).
^ Kratsch, Stefan; Schweitzer, Pascal (2010). Kaplan, Haim (ed.). "Isomorphism for Graphs of Bounded Feedback Vertex Set Number". Algorithm Theory - SWAT 2010. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6139: 81–92. Bibcode:2010LNCS.6139...81K. doi:10.1007/978-3-642-13731-0_9. ISBN 978-3-642-13731-0.
^ Algorithms and Data Structures SpringerLink (PDF). Lecture Notes in Computer Science. Vol. 11646. 2019. doi:10.1007/978-3-030-24766-9. ISBN 978-3-030-24765-2. S2CID 198996919.

레퍼런스

조사 기사

를 클릭합니다Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro (1999), "A 2-approximation algorithm for the undirected feedback vertex set problem", SIAM Journal on Discrete Mathematics, 12 (3): 289–297 (electronic), doi:10.1137/S0895480196305124, MR 1710236.
Becker, Ann; Bar-Yehuda, Reuven; Geiger, Dan (2000), "Randomized algorithms for the loop cutset problem", Journal of Artificial Intelligence Research, 12: 219–234, arXiv:1106.0225, doi:10.1613/jair.638, MR 1765590, S2CID 10243677
Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.", Artificial Intelligence, 83 (1): 167–188, CiteSeerX 10.1.1.25.1442, doi:10.1016/0004-3702(95)00004-6
Cao, Yixin; Chen, Jianer; Liu, Yang (2010), "On feedback vertex set: new measure and new structures", in Kaplan, Haim (ed.), Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norway, June 21-23, 2010, Lecture Notes in Computer Science, vol. 6139, pp. 93–104, arXiv:1004.1672, Bibcode:2010LNCS.6139...93C, doi:10.1007/978-3-642-13731-0_10, ISBN 978-3-642-13730-3
Chen, Jianer; Fomin, Fedor V.; Liu, Yang; Lu, Songjian; Villanger, Yngve (2008), "Improved algorithms for feedback vertex set problems", Journal of Computer and System Sciences, 74 (7): 1188–1198, doi:10.1016/j.jcss.2008.05.002, MR 2454063
Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM, 55 (5), Art. 21, doi:10.1145/1411509.1411511, MR 2456546, S2CID 1547510
Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics, Second Series, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, MR 2178966, archived from the original (PDF) on 2009-09-20, retrieved 2010-03-29
Erdős, Paul; Pósa, Lajos (1965), "On independent circuits contained in a graph" (PDF), Canadian Journal of Mathematics, 17: 347–352, doi:10.4153/CJM-1965-035-8, S2CID 123981328
Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the minimum feedback vertex set problem: exact and enumeration algorithms.", Algorithmica, 52 (2): 293–307, CiteSeerX 10.1.1.722.8913, doi:10.1007/s00453-007-9152-0, S2CID 731997
Fomin, Fedor V.; Villanger, Yngve (2010), "Finding induced subgraphs via minimal triangulations", Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 383–394, doi:10.4230/LIPIcs.STACS.2010.2470, S2CID 436224
Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103
Li, Deming; Liu, Yanpei (1999), "A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph", Acta Mathematica Scientia, 19 (4): 375–381, doi:10.1016/s0252-9602(17)30520-9, MR 1735603
Razgon, I. (2007), "Computing minimum directed feedback vertex set in O*(1.9977ⁿ)", in Italiano, Giuseppe F.; Moggi, Eugenio; Laura, Luigi (eds.), Proceedings of the 10th Italian Conference on Theoretical Computer Science (PDF), World Scientific, pp. 70–81
Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three", Discrete Mathematics, 72 (1–3): 355–360, doi:10.1016/0012-365X(88)90226-9, MR 0975556

교재 및 조사 기사

Festa, P.; Pardalos, P. M.; Resende, M.G.C. (2000), "Feedback set problems", in Du, D.-Z.; Pardalos, P. M. (eds.), Handbook of Combinatorial Optimization, Supplement vol. A (PDF), Kluwer Academic Publishers, pp. 209–259
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A1.1: GT7, p. 191, ISBN 978-0-7167-1045-5
Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5

[1] 개리와 존슨 때문에 발표되지 않은 결과, cf.Garey & Johnson (1979년): GT7

[2] 우에노·카지타니·고토(1988년), 리앤류(1999년)

[3] Fomin & Villanger (2010)

[FOOTNOTEFominGaspersPyatkinRazgon2008-4] 포민 등 (2008년).

[FOOTNOTERazgon2007-5] Razgon (2007년).

[FOOTNOTEChenLiuLuO'Sullivan2008-6] 첸 등 (2008년).

[FOOTNOTEUenoKajitaniGotoh1988-7] 우에노·카지타니·고토(1988년).

[8] Dinur & Safra 2005

[k72-9] 카르프(1972)

[10] Becker & Geiger (1996년).또, 같은 근사비를 가지는 대체 근사 알고리즘에 대해서는, Bafna, Berman, Fujito(1999)를 참조해 주세요.

[FOOTNOTEErdősPósa1965-11] Erdss & Posa(1965).

[FOOTNOTESilberschatzGalvinGagne2008-12] Silverschatz, Galvin & Gagne (2008).

[FOOTNOTEFestaPardalosResende2000-13] Festa, Pardalos & Resende(2000).

[14] Kratsch, Stefan; Schweitzer, Pascal (2010). Kaplan, Haim (ed.). "Isomorphism for Graphs of Bounded Feedback Vertex Set Number". Algorithm Theory - SWAT 2010. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6139: 81–92. Bibcode:2010LNCS.6139...81K. doi:10.1007/978-3-642-13731-0_9. ISBN 978-3-642-13731-0.

[15] Algorithms and Data Structures SpringerLink (PDF). Lecture Notes in Computer Science. Vol. 11646. 2019. doi:10.1007/978-3-030-24766-9. ISBN 978-3-030-24765-2. S2CID 198996919.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Search