태그 보관물: graph-algorithms

graph-algorithms

하이퍼 그래프의 선 그래프 인식 이있는 경우 하이퍼 그래프입니다 .G

하이퍼 그래프 의 선 그래프 는 비어 있지 않은 교차점이있는 경우 두 모서리가있는 정점이 인접 하므로 모서리를 갖는 (단순) 그래프 입니다. 하이퍼 그래프는 각 모서리에 최대 개의 정점 이있는 경우 하이퍼 그래프입니다 .G H H G r r

H

G

H

H

G

r

r

그래프 주어 다음 문제의 복잡도 란 존재 않는 -hypergraph의 되도록 라인 그래프이다 ?3 H G H

G

3

H

G

H

하이퍼 그래프의 선 그래프를 인식하는 것은 다항식이며, 하이퍼 그래프의 선 그래프를 인식하는 것이 NP 인 것으로 알려져있다 (Poljak 등, Discrete Appl. Math. 3 (1981) 301-312). 고정 대해 -complete . r r 4

2

r

r≥4

참고 : 간단한 하이퍼 그래프의 경우, 즉 모든 하이퍼에지가 뚜렷한 경우 Poljak et al.의 논문에서 입증 된 바와 같이 NP- 완전 문제입니다.



답변

Skums et al.의 사전 인쇄 저널 버전을 찾았습니다. @mhum에 의해 지적; 여기 있습니다 :
이산 수학 309 (2009) 3500–3517 . 거기서 저자는 다음과 같이 인용을 수정했습니다.

대신 취하면 상황이 급격히 변 합니다. Lovasz는 L_3 클래스를 특성화하는 문제를 제기 , 금지 된 유도 서브 그래프의 유한리스트 ( 유한 특성화 )에 의한 특성화가 없음을 지적했다 [9]. 이 입증되었음을 인식 문제 ” “를 ” “[15] ” “에 대한 과의 경계 교차 그래프의 인식의 문제 – 여러 개의 모서리가없는 균일 한 하이퍼 그래프 [15]는 NP가 완전합니다.k = 2 L 3 G L k k 4 G L l 3 k 3 3

k≥3

k=2

L3

G∈Lk

k≥4

G∈L3l

k≥3

3

참고 문헌 15는 전술 한 Poljak et al. (1981).

따라서 하이퍼 그래프 (여러 가장자리가 허용됨) 의 선 그래프를 인식 하는 것이 OPEN PROBLEM 이며 @mhum의 대답이 실제로이 발견에 도움이되었다고 생각합니다. 감사!

3


답변

Poljak et al.에 액세스 할 수 없습니다. 그러나 초록 -hypergraphs의 꺾은 선 그래프를 인식하는 것이 4가 아니라 r 3에 대해 NP- 완료 임을 나타냅니다 . 또한, 선형 3- 균일 하이퍼 그래프의 에지 교차 그래프 에서 인용 , Skums et al. (pdf) 는 다음과 같은 경우를 나타냅니다.

r

r≥3

4

k = 2 대신 취하면 상황이 주로 바뀝니다 . Lovasz는 클래스 L 3 의 특성화 문제를 제기했으며 , 금지 된 유도 서브 그래프의 유한리스트 ( 유한 특성화 )에 의한 특성화가 없음을 지적했다 [10]. k 3 [5]에 대한 인식 문제 ” G L 3 “[17] 및 ” G L l k ” 는 NP- 완전한 것으로 입증 되었습니다.

k=3

k=2

L3

G∈L3

G∈Lkl

k≥3

L3

L3l

답변